C++

3つの整数 A、B、N が与えられたとき、AとBの間に挿入されるN個の幾何平均（等比中項）を求めることを考えます。例として、A = 2、B = 32、N = 3 の場合、出力は 4、8、16 となります。考え方：等比数列の性質を利用するこの問題は非常にシンプルです。AとBをそれぞれ初項・末項とする等比数列の中間に、N個の要素を挿入すればよいのです。G1、G2、…、Gn をn個の幾何平均とすると、数列は次のようになります。A、G1、G2、…、Gn、Bこのとき、Bは数列の (N + 2) 番目の項に相当します。そこで、等比数列の一般項の公式から、以下の式が成り立ちます。$$B=A*R^{N+1}$

2つの文字列 str1 と str2 が与えられたとき、長さLの「魔法のペア」の数を求める問題を考えてみましょう。すべてのインデックス i について str1[i] < str2[i] が成り立つとき、この2つの文字列は魔法のペアであると定義されます。ペアの総数は非常に大きな値になる可能性があるため、答えは 109 を法とした剰余として返します。なお、文字列には小文字の英字のみが含まれるものとします。 考え方 この問題のアプローチはシンプルです。まず長さ L = 1 の場合を考えてみます。インデックス i = 1 の位置にある str1 の文字が a であるとき、対応する str2 の文

n個の要素を含む配列が与えられたとき、XOR(排他的論理和)の計算結果が0になるペアの数を求めることを考えます。ペア(x, y)のXORが0になるのは、x = y が成り立つ場合、すなわち2つの値が等しいときだけです。これは「同じ数値同士のXORは必ず0になる」というビット演算の基本的な性質によるものです。解法のアプローチこの問題は、次の手順で解くことができます。まず、配列を昇順にソートします。ソート後は同じ値どうしが隣り合って並ぶため、連続する2つの要素を比較し、等しければカウントを1つ増やします。すべての要素が同じ値である場合、末尾側のペアがカウントから漏れる可能性があります。そこで、配列

長さが n の文字列 S と、長さが n + 1 の文字列 T があるとします。文字列 T には S に含まれるすべての文字が含まれており、さらに余分な文字が1つだけ追加されています。この記事では、効率的なアルゴリズムを使って、その余分な文字を見つける方法を解説します。アプローチ：ハッシュマップを活用するこの問題を解くためには、ハッシュマップ（連想配列）を利用するのが効果的です。手順は以下のとおりです。まず空のハッシュマップを用意し、文字列 T のすべての文字の出現回数をカウントして登録します。次に、文字列 S の各文字についてカウントを1ずつ減らしていきます。すべての処理が終わった時点で、カ

整数の配列が与えられ、この配列が「暗号化された配列」であるとします。例えば、暗号化配列が A = [10, 14, 12, 13, 11] で、元の配列が B = [5, 1, 3, 2, 4] だったとしましょう。このとき、配列 A の各要素 A[i] は次の規則に従っています。A[i] = 元の配列 B における、自分自身（B[i]）を除くすべての要素の合計この記事では、このような暗号化された配列から、元の配列を効率的に復元する方法を解説します。解法の考え方：算術的な観察この問題は、シンプルな算術的な性質に基づいて解くことができます。まず、配列のサイズを 4 と仮定し、元の配列を B =

この記事では、C++を使用して、ある数値の偶数の素因数の合計を効率的に求める方法を解説します。まず具体例として、n = 480という数値を考えてみましょう。480の素因数は 2, 2, 2, 2, 2, 3, 5 です。ここで偶数となる素因数は2のみなので、その合計は 2+2+2+2+2 = 10 となります。 なお、素数の中で偶数なのは「2」だけであるため、この問題は実質的に「数値が2で何回割り切れるかを数え、その回数×2を求める」ことと同じです。この性質を利用すると、非常にシンプルなアルゴリズムで解くことができます。 解法のポイント 数値が2で割り切れる間は、その都度合計に2を加算し、数

この記事では、ある数の奇数の素因数すべての合計を、効率的に求める方法を解説します。例として n = 1092 という数を考えてみましょう。1092 を素因数分解すると 2 × 2 × 3 × 7 × 13 となり、このうち奇数の素因数は 3、7、13 です。したがって、奇数の素因数の合計は 3 + 7 + 13 = 23 となります。この問題を解くためには、以下のルールに従います。数が 2 で割り切れる間は、その因数を無視して、数を 2 で繰り返し割ります。この時点で数は必ず奇数になっています。3 から数の平方根までの範囲で、現在の値 i で割り切れる場合は、その因数を合計に加算し、数を i

この記事では、PL/SQLを使用して数値の階乗を求める方法について解説します。PL/SQLでは、関連する宣言文のブロック内に一連のコマンドをまとめて記述するのが基本的なスタイルです。ある数値の階乗とは、1からnまでのすべての整数を掛け合わせた値のことです(nは与えられた数値)。数式で表すと、n! = n × (n−1) × (n−2) × … × 2 × 1 となります。例えば、5の階乗(5!)は、5 × 4 × 3 × 2 × 1 = 120 と計算されます。PL/SQLのサンプルコードDECLARE    fact number := 1; 

文字列が与えられたとき、その中で最初に繰り返されて出現する文字を見つけたいことがあります。例えば、文字列が「Hello Friends」である場合、「l」という文字が2回連続して現れるため、最初に繰り返される文字は「l」となります。 この問題を効率的に解決するには、ハッシュ（ハッシュセット）を利用した手法が有効です。具体的には、ハッシュセットを1つ用意し、文字列の各文字を先頭から順に走査していきます。走査中の文字がまだセットに存在しない場合はセットに挿入し、すでに存在している場合はその時点の文字が「最初に繰り返される文字」となるため、それを返します。 このアルゴリズムの計算量は、文字列の長さを

本記事では、C++を用いて、ある数値の中に特定の桁（数字）が何回出現するかを求める方法を解説します。 例として、数値が 12452321 であり、調べたい桁 D = 2 である場合を考えてみましょう。このとき、2は数値の中に3回現れるため、出現頻度は 3 となります。 解決のアプローチ この問題は、次の手順でシンプルに解くことができます。 数値の最下位の桁（1の位）を剰余演算（% 10）によって取り出します。 取り出した桁が目的の数字 d と一致していれば、カウンタを1増やします。 数値を10で割ることで、処理済みの桁を取り除きます。 数値が0になるまで、上記の手順を繰り返します。 この方

配列に n 個の異なる要素が格納されているとします。この配列の中から、特定の要素が何回出現するか（頻度）を調べたい場合があります。例えば、配列 A = [5, 12, 26, 5, 3, 4, 15, 5, 8, 4] の中で「5」の頻度を調べると、答えは 3 になります。アルゴリズムの考え方この問題は、次の手順で解くことができます。1. 配列を左端から順に走査します。2. 現在の要素が調べたい数値と一致したら、カウンターを1つ増やします。3. 一致しない場合は、そのまま次の要素へ進みます。4. 配列の最後まで走査したら、カウンターの値が頻度となります。このアルゴリズムの計算量は O(n) で

この記事では、C++を使って「1! + 2! + ... + N!」という階乗の合計の下一桁（一の位）を求める方法を解説します。例えばN = 3の場合、1! + 2! + 3! = 9 となるため答えは9、N = 4の場合は 1! + 2! + 3! + 4! = 33 となり、下一桁は3になります。階乗の下一桁の重要な性質この問題を解く鍵となるのは、5以上の数の階乗の下一桁が必ず0になるという性質です。5! = 120、6! = 720、7! = 5040 のように、5!以降はすべて一の位が0になります。これは、5以上の階乗には必ず因数2と5のペアが含まれ、10の倍数になるためです。したがっ

はじめに数値Nが与えられたとき、再帰（リカージョン）を用いてln(N!)の値を求める方法を解説します。ここでいうln()とは、自然対数、すなわち底がe（ネイピア数）の対数のことです。解法の考え方この問題は、対数の基本的な性質を利用することでシンプルに解くことができます。階乗の対数は、積の対数を対数の和に変換できる性質により、次のように展開できます。$$\ln\lgroup N!\rgroup=\ln\lgroup N*\lgroup N-1\rgroup *\lgroup N-2\rgroup *\dotsm*2*1\rgroup=\ln\lgroup N\rgroup+\ln\lgroup

メルセンヌ素数とは数学におけるメルセンヌ素数とは、「2の冪乗から1を引いた値」に該当する素数のことです。すなわち、ある整数 n に対して Mn = 2n − 1 の形で表される素数を指します。本記事では、入力された正の整数 n 未満のメルセンヌ素数をすべて出力するC++プログラムの実装方法を解説します。メルセンヌ素数となる指数 n は 2, 3, 5, 7, … と続きます。これらに対応するメルセンヌ素数は、それぞれ 3, 7, 31, 127 です。アルゴリズムメルセンヌ素数を求める基本的な手順は以下のとおりです。1. 与えられた数 n 以下のすべての素数を生成する（エラトステネスの篩を利用

概要ミッドスクエア法（平方採中法）とは、擬似乱数を生成するための古典的な手法の一つです。この方法は数学者のジョン・フォン・ノイマンによって考案され、1949年に開催された学会で発表されました。この手法の基本的な流れは次のとおりです。まず初期シード値（種となる値）を選び、その2乗を計算します。次に、2乗した結果の中央部分からいくつかの桁を取り出し、その数字を新しいシード値として採用します。具体例例として、3456を初期シード値とした場合を見てみましょう。3456の2乗は11943936です。中央の4桁「9439」を新しいシード値とします。9439の2乗は89094721です。さらに中央の4桁「0

問題の概要本記事では、2つのソートされていない（未ソート）配列を受け取り、それらを1つの新しい配列にマージしたうえで、昇順にソートされた結果を返す関数をC++で実装する方法を解説します。具体的な入力と期待される出力は以下の通りです。arr1[] = {10, 5, 7, 2} arr2[] = {4, 17, 9, 3} result[] = {2, 3, 4, 5, 7, 9, 10, 17}アルゴリズム実装のアプローチは非常にシンプルで、次の2ステップで構成されます。2つの未ソート配列を1つの新しい配列へマージ（連結）する。新しく作成した配列全体をソートする。C++では、STL（標準テンプ

問題概要2つの配列が与えられたとき、それらを組み合わせて、第1の配列と第2の配列の要素が交互に並んだ新しい配列（結果配列）を作成します。片方の配列に余分な要素がある場合は、その残りの要素を結果配列の末尾に追加します。arr1[] = {10, 20, 30, 40} arr2[] = {-10, -20, -30, -40} result[] = {10, -10, 20, -20, 30, -30, 40, -40}この例では、両方の配列の長さが同じため、要素が完全に交互に配置されています。もし arr1 の方が長ければ、余った要素は result の最後にそのまま追加されます。アルゴリズム

問題の概要ソート済みの単方向連結リストが2つ与えられます。この2つのリストを1つのソート済みリストに統合（マージ）する関数を作成してください。List1: 10->15->17->20 List2: 5->9->13->19 Result: 5->9->10->13->15->17->19->20アルゴリズム基本的な考え方は、両方のリストを先頭から順に走査し、常に値の小さい方のノードを結果リストにつなげていくというものです。1. 両方のリストを走査する     1.1. lis

問題の概要ソート済みの2つの配列が与えられたとき、それらを1つのソート済み配列へマージ(統合)する関数を作成します。これはマージソートの中核となる処理であり、技術面接や競技プログラミングでも頻出のテーマです。Arr1[] = {10, 15, 17, 20} Arr2[] = {5, 9, 13, 19} Result[] = {5, 9, 10, 13, 15, 17, 19, 20}アプローチのポイント単純に2つの配列を連結してから再ソートすることも可能ですが、それぞれがすでにソート済みであるという性質を活かせば、ツーポインタ(2つのインデックス)手法によって O(n1 + n2) の計算

問題の概要配列形式で表された2つのバイナリ最大ヒープ（Max Heap）が与えられたとき、それらを1つの最大ヒープへと統合（マージ）します。Heap1[] = {20, 17, 15, 10} Heap2[] = {19, 13, 7} Result[] = {20, 19, 15, 13, 17, 7, 10}アルゴリズムアプローチは非常にシンプルです。以下の手順で処理を行います。1. 結果を格納するための新しい配列を作成する2. 与えられた2つの配列を順番に結果用の配列へコピーする3. ヒープ構築（Build Heap）を実行し、マージ後の完全な最大ヒープを構成するポイントは、2つのヒープ