C++

2つの整数 N と P が与えられているとします。P は N 個の未知の整数の積であり、そのときそれらの整数の最大公約数（GCD）としてあり得る最大値を求めるのが課題です。 例として、N = 3、P = 24 の場合を考えてみましょう。3つの整数の組み合わせとしては {1, 1, 24}、{1, 2, 12}、{1, 3, 8}、{1, 4, 6}、{2, 2, 6}、{2, 3, 4} などが考えられます。それぞれのGCDは 1, 1, 1, 1, 2, 1 となるため、この場合の答えは 2 です。 解法のアプローチ まず P のすべての素因数を求め、ハッシュマップに格納します。各素因数が

問題概要配列 A が与えられたとき、「その部分配列の最小公倍数（LCM）」と「部分配列内の要素の積」が一致するような部分配列の中で、最も長いものの長さを求めます。条件を満たす部分配列が存在しない場合は -1 を返します。例として、配列が {6, 10, 21} である場合を考えてみましょう。部分配列 {10, 21} に注目すると、その最小公倍数は 210、要素の積も 210 となり、両者が一致します。このため、答えは 2 となります。解き方のアプローチこの問題へのアプローチは非常にシンプルです。長さ 2 以上のすべての部分配列を網羅的にチェックし、条件を満たすものが見つかるたびに、これまでの

問題の概要今回は興味深いプログラミング問題を取り上げます。3つの整数 A、B、C が与えられたとき、「X mod C = 0」を満たし、かつ X が範囲 [A, B] に含まれない最小の正の整数 X を求めることを考えます。例えば、A = 5、B = 10、C = 4 の場合、答えとなる X の値は 4 です。これは、4 が C で割り切れ(4 ÷ 4 = 1)、かつ範囲 [5, 10] の外側に存在するためです。解法のアプローチこの問題は、以下のシンプルな手順で解くことができます。C が範囲 [A, B] に含まれない場合： C をそのまま結果として返します。C 自身が「C で割り切れ、範囲

正と負の値が混在するデータのリストがあるとします。ここで求めるのは、要素が連続している部分配列（サブアレイ）の中で、合計が最大となるものです。例えば、リストが {-2, -5, 6, -2, -3, 1, 5, -6} の場合、最大部分配列和は 7 となり、これは {6, -2, -3, 1, 5} の合計に相当します。 この問題は、分割統治法（Divide and Conquer）を用いることで効率的に解くことができます。基本的な考え方は以下の通りです。 アルゴリズムの手順 配列を左右の2つの部分に分割する 次の3つの値のうち最大のものを答えとする 左側の部分配列における最大部分配列和

メタ文字列とは？この記事では、2つの文字列が「メタ文字列」であるかどうかを判定する方法を解説します。メタ文字列とは、互いに非常によく似た文字列のことで、片方の文字列内で2つの文字を入れ替えるともう片方の文字列と完全に一致するような関係を指します。例えば、「HELLO」と「OELLH」という2つの文字列は、HとOを入れ替えることで一致するため、メタ文字列です。判定の手順2つの文字列がメタ文字列かどうかを確認するには、以下の手順に従います。両方の文字列の長さが異なる場合は、false を返す。長さが同じ場合は、一致しない文字の数を数え、その位置（インデックス）も記録する。不一致の文字数が2より大き

問題の概要 N個の要素を持つ配列が与えられます。この配列から、以下のルールに従って要素を削除していきます。 操作の内容は次のとおりです。まず配列から任意の2つの数を選び、そのうち大きい方を削除します。このとき発生するコストは、小さい方の数と等しくなります。この操作を繰り返し、一度に1つの要素だけを削除しながら、全体のコストを最小化することが目標です。 例として、配列 {4, 2, 5} を考えてみましょう。まず 4 と 2 を選び、コスト 2 を支払って 4 を削除します。続いて残った 5 を、再びコスト 2 で削除します。 解法のアプローチ この問題の解き方は非常にシンプルです。操作のコスト

サイズNの正の整数からなる配列 arr が与えられたとき、考えられるすべての部分配列の中で最小のLCM(最小公倍数)とGCD(最大公約数)を求める問題を考えてみましょう。例えば、配列が {2, 66, 14, 521} である場合、最小のLCMは 2、最小のGCDは 1 となります。解き方のアプローチこの問題は貪欲法(グリーディーアプローチ)を用いて効率的に解くことができます。ポイントは次の2点です。部分配列に含まれる要素数を減らすほど、LCMは小さくなる傾向があります。逆に、部分配列のサイズを大きくするほど、GCDは小さくなります。したがって、求めるべき最小のLCMは「配列内の最小の要素」(

問題の概要同じ長さを持つ2つの文字列が与えられたとき、文字を一切削除せずに、この2つの文字列をアナグラムにするために必要な最小の変更（置き換え）回数を求めることを考えます。アナグラムとは、使用されている文字の集合が完全に一致する2つの文字列のことです。例えば、「HELLO」と「WORLD」という2つの文字列を見てみましょう。この場合、3つの文字が互いに異なるため、必要な変更回数は3回となります。アルゴリズムの考え方この問題の解法は非常にシンプルです。以下の手順で進めます。最初の文字列に含まれる各文字の出現頻度を、サイズ26の配列に記録します。2番目の文字列を先頭から順に走査し、各文字に対応する

問題の概要配列 arr と整数 k が与えられたとき、配列全体の GCD(最大公約数)を k の倍数に一致させるために必要な最小の操作回数を求めます。ここでいう「操作」とは、任意の要素の値を 1 増やす、または 1 減らすことを指します。例として、配列が {4, 5, 6}、k = 5 の場合を考えてみます。4 を 1 増やして 5 にし、6 を 1 減らして 5 にすれば、すべての要素が 5 の倍数になり、GCD も 5 となります。このとき必要な操作回数は 2 回です。アルゴリズムの手順配列の GCD を k の倍数にするには、すべての要素を k の倍数に揃える必要があります。以下の手順に

問題の概要3つの整数 A、B、C が与えられたとき、次の条件を両方満たす最小の整数 X を求めます。X は C で割り切れる(X mod C = 0)X は範囲 [A, B] に含まれない例として、A = 5、B = 10、C = 4 の場合を考えてみましょう。このとき答えは X = 4 となります。4 は 4 で割り切れ、かつ範囲 [5, 10] の外側にあるためです。解法のアプローチこの問題は定数時間 O(1) で解くことができます。考え方の手順は以下の通りです。ステップ1: C が範囲 [A, B] に含まれていない場合(C < A または C > B)、C 自身が条件を満た

N個の要素を持つ配列Aが与えられたとき、配列内のすべての要素の階乗の最大公約数（GCD）を求めることを考えます。例えば、配列の要素が {3, 4, 8, 6} の場合、各要素の階乗は 3! = 6、4! = 24、8! = 40320、6! = 720 となり、これらのGCDは 6 になります。解法のポイントここで重要な数学的な性質があります。2つの数のGCDとは、両方の数を割り切る最大の数のことです。階乗の場合、小さい数の階乗は必ず大きい数の階乗を割り切ることができます。つまり、2つの階乗のGCDは、小さい方の数の階乗そのものになります。例えば、3! と 5! のGCDを考えると、3! =

最大公約数（HCF、GCDとも呼ばれます）は、通常「ユークリッドの互除法」を使えば簡単に計算できます。しかし、この記事では、ユークリッドの互除法や再帰的なアルゴリズムに頼らずに、GCD（HCF）を求める方法を紹介します。例として、16と24という2つの数を考えます。この2つの数の最大公約数は8です。アルゴリズムの考え方ここでのアプローチは非常にシンプルです。手順は以下のとおりです。1. まず、2つの数のうち小さい方の値を取得します。2. 大きい方の数が小さい方の数で割り切れる場合、その小さい方の数がそのままHCFとなります。3. 割り切れない場合は、小さい方の数の半分（min / 2）から2ま

円の中心座標と半径、そして1つの点が与えられたとき、その点が円の内側にあるかどうかを判定する問題です。この問題は、点から円の中心までの距離を計算すれば解決できます。その距離が半径以下であれば点は円の内側(または円周上)にあり、そうでなければ外側にあると判断できます。 判定の考え方 点 (x, y) と円の中心 (cx, cy) の間の距離 d は、次の式で求められます。 d = √((x − cx)² + (y − cy)²) この距離 d が半径 r 以下であれば点は円の内側、r より大きければ外側です。実際のプログラムでは、平方根の計算を省いて「距離の2乗」と「半径の2乗」を直接比較すると

3つの変数 N、R、P があるとします。N と R から二項係数 NCR を求め、P は素数とします。このとき、NCR が P で割り切れるかどうかを判定するのが本記事の目的です。例えば、N = 7、R = 2、P = 3 の場合、7C2 = 21 となり、21 は 3 で割り切れるため、結果は true となります。二項係数は一般的に次の式で表されます。NCR = N! / (R! × (N − R)!)ここでルジャンドルの定理(Legendres Formula)を活用します。この定理を使うと、N!、R!、(N − R)! のそれぞれを割り切る素数 P の最大のべき乗(指数)を求めることが

本記事では、有理数（分数）の最小公倍数（LCM）を求める方法を解説します。例えば、{2/7, 3/14, 5/3} という有理数のリストが与えられた場合、そのLCMは 30/1 となります。 有理数のLCMを求める公式 この問題を解くには、まずすべての分子のLCM（最小公倍数）を計算し、次にすべての分母のGCD（最大公約数）を計算します。有理数のLCMは、次の式で表されます。 $$LCM = \frac{すべての分子のLCM}{すべての分母のGCD}$$ 各分数の倍数となる有理数は、分子がすべての分子の公倍数であり、かつ分母がすべての分母の公約数である必要があります。その中で最小のものが「分子

この記事では、ドラゴン曲線(Dragon Curve)シーケンスのn番目の項を求めるC++プログラムを紹介します。ドラゴン曲線シーケンスとは、無限に続く二進列(0と1のみで構成される数列)のことで、「1」から始まり、各ステップで前の項の各要素に対して「1」と「0」を交互に追加していくことで次の項を形成していきます。 第1項: 1 第2項: 110 第3項: 1101100 第4項: 110110011100100 まず「1」から始め、前の項の各要素の後に「1」と「0」を交互に付け加えていきます。新しい項が得られたら、それを現在の項として同じ手順をn回繰り返すことで、目的の項を生成できます

ある配列Aが与えられたとき、各要素の「サーパッサー（surpasser）」の数を求める問題を考えてみましょう。サーパッサーとは、現在注目している要素よりも右側に存在する、その要素より大きい値のことです。 例えば、A = {2, 7, 5, 3, 0, 8, 1} という配列の場合、サーパッサーの数は {4, 1, 1, 1, 2, 0, 0} となります。これは、先頭の「2」の右側には「7・5・3・8」という4つの大きな値が存在するためです。その他の要素についても同じルールで数えていきます。 アルゴリズムの考え方 解法は非常にシンプルです。2重のループを使用し、外側のループで各要素を順に取り上

ある数Aと、その最小公倍数（LCM）および最大公約数（HCF/GCD）の値が与えられているとき、もう一方の数Bを求める問題を考えます。例えば、A = 5、LCM = 25、HCF = 4が与えられた場合、もう一方の数は20になります。この問題を解く鍵となるのは、任意の2つの数AとBの間に常に成り立つ次の重要な数学的性質です。$$𝐴∗𝐵=𝐿𝐶𝑀∗𝐻𝐶𝐹$$つまり、「2つの数の積」は「最小公倍数と最大公約数の積」と等しくなります。この式をBについて変形すると、次のようになります。$$𝐵= \frac{LCM*HCF}{A}$$アルゴリズム数A、LCM、

プログラミングの問題の中には、与えられたルールに従って文字列を順番に処理し、最終的な結果を導き出すものがあります。本記事では、3つの色(G・B・Y)からなる文字列が与えられたとき、以下の関係式に基づいて最終的に得られる色をC++で求める方法を解説します。 問題の定義 色と色を組み合わせたときの結果は、次のルールで決まります。 B × G = Y Y × B = G G × Y = B 例えば、文字列が「GBYGB」であれば結果は B になり、「BYB」であれば結果は Y になります。 アルゴリズムの考え方 アプローチは非常にシンプルです。 文字列の先頭の文字を初期の結果色として設定します

この記事では、2つの数 a と b の合計（sum）と最大公約数（GCD）が与えられたときに、元の2つの数を復元する方法を解説します。条件を満たす組み合わせが存在しない場合は -1 を返します。 例えば、合計が 6、GCDが 2 とすると、答えは 4 と 2 になります（4 + 2 = 6、gcd(4, 2) = 2 を満たすため）。 考え方（アプローチ） GCDが分かっているということは、2つの数がどちらもGCDの倍数であることが確定します。この性質を利用すると、次の手順で答えを導き出せます。 候補の生成： 片方の数をGCDそのものと仮定すると、もう片方は「合計 − GCD」となります。