C++

問題の概要N個の正の整数からなる配列と、変数Kが与えられたとします。この中から、任意の2つの要素の差がKで割り切れるような、ちょうどm個の要素のセットを見つける必要があります。例えば、配列 A = [4, 7, 10, 6, 9]、k = 3、m = 3 の場合、出力は「Yes」になります。4、7、10 という3つの要素が条件を満たすからです。解法のアプローチこの問題を効率的に解く鍵となるのは、各要素を k で割った余り（剰余）に注目することです。同じ余りを持つ2つの要素の差は、必ず k で割り切れるという性質を利用します。具体的な手順は以下のとおりです。サイズ k の2次元配列 rem[][

2次元平面上に点 P と直線の方程式が与えられているとき、点 P からその直線へ下ろした垂線の足（交点）の座標を求めるのが本記事のテーマです。幾何学やコンピュータグラフィックスの分野でよく使われる基本的な計算なので、数式的な背景と合わせてC++での実装方法を解説します。 数学的な背景 直線の方程式は ax + by + c = 0 と表されます。点 P を通ってこの直線に垂直な直線の方程式は、ay − bx + d = 0 の形になります。ここで、点 P の座標を (x₁, y₁)、垂線の足となる点を Q(x₂, y₂) とします。 点 P の座標を垂直な直線の方程式に代入すると、ay₁ −

2進文字列 bin があるとします。この文字列に対して n 回の変換を繰り返し適用します。各変換では、文字「0」は「01」に、「1」は「10」に置き換えられます。そして、n 回の変換が完了した後の文字列における i 番目の文字を求めるのが、この問題の目的です。具体例を見てみましょう。2進文字列が「101」、n = 2、i = 3 の場合、1回目の変換後は「100110」になり、2回目の変換後は「100101101001」になります。したがって、i 番目（インデックス3）の文字は「1」ということになります。解法のアプローチこの問題は、以下の手順に従って解くことができます。外側のループを n 回実

問題の概要正の整数 k が与えられたとき、n XOR (n+1) の計算結果が k と等しくなるような正の整数 n を求めることを考えます。例えば、k = 7(2進数で 111)の場合、答えは 3 になります。3 は 2進数で 011、3 + 1 = 4 は 100 と表され、011 XOR 100 = 111(10進数で 7)となるためです。アルゴリズムの考え方この問題は、n の偶奇によって2つの場合に分けて考えることができます。n が偶数の場合n が偶数であれば、n の最下位ビットは 0、n + 1 の最下位ビットは 1 となり、それ以外の上位ビットはすべて同一です。したがって、XOR の

括弧を含む数式を扱う際、特定の開き括弧「(」に対応する閉じ括弧「)」の位置を求めたいケースがあります。例えば、次のような式を考えてみましょう。(25*6+(88-32+(50/10)+20))この式において、インデックス6の位置にある開き括弧に対応する閉じ括弧は、インデックス23の位置に存在します。スタックを使った解法の考え方この問題は、スタック（Stack）というデータ構造を使うことで効率的に解決できます。アルゴリズムの流れは以下の通りです。指定されたインデックスから式の走査を開始します。開き括弧「(」を見つけるたびに、スタックにプッシュします。閉じ括弧「)」を見つけたら、スタックから要素を

整数 n が与えられたとき、二項係数のうち偶数番目（インデックス 0, 2, 4, …）の項だけを取り出して、その合計を求める問題を考えます。数式で表すと次のようになります。$$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\binom{n}{6}+\cdots$$例として n = 4 の場合を計算してみましょう。$$\binom{4}{0}+\binom{4}{2}+\binom{4}{4}=1+6+1=8$$知っておくと便利な数学的性質実は、偶数番目の二項係数の合計は常に 2n-1 と等しくなることが二項定理から導けます。(1+1)n = 2n はすべての二

初期状態が「0」であるバイナリ文字列 s を考えます。各反復処理では、現在の文字列をビット反転（0と1を入れ替え）し、その結果を元の文字列の末尾に追加していきます。この操作を n 回繰り返した後の文字列から、k 番目のビットを求めるのが本記事のテーマです。例として、反復回数が 4 回、k = 7 の場合を考えてみましょう。文字列は以下のように変化していきます。反復回数文字列（初期値は「0」）1012011030110100140110100110010110この場合、7 番目のビットは「1」となります。アルゴリズムの考え方手順は非常にシンプルです。1. 現在の文字列の補数（0 を 1 に、1

問題の概要いくつかの要素を含む配列 A があるとします。この配列から、すべての一意な（重複しない）要素の合計を求める必要があります。例えば、配列が A = [5, 12, 63, 5, 33, 47, 12, 63] の場合を考えてみましょう。このとき、一意な要素は「5, 12, 63, 33, 47」であり、その合計は 160 になります。重複している要素は、一度合計に加算された後は単純に無視されます。解決のアプローチこの問題は、C++の unordered_set（ハッシュセット）を使うことで効率的に解決できます。基本的な考え方は以下のとおりです。forループを1回だけ実行して配列を走査す

循環節の長さとはある数 n が与えられたとき、1/n の小数展開における循環節（繰り返し部分）の長さを求めることを考えます。例えば、n = 7 の場合を見てみましょう。1/7 = 0.142857142857…太字で示した「142857」の部分が無限に繰り返されています。この場合、循環節の長さは 6 となります。アルゴリズムの考え方割り算の筆算を手で行うことを思い出してください。各ステップで現れる「余り」に注目すると、次のことが分かります。数 n で割ったときの余りは、0 から n-1 までの最大 n 種類しか存在しません。しかし、循環節は必ずしも最初の余りから始まるとは限りません。小数点以下

n個の要素からなる配列が与えられたとします。このとき、すべての要素を同じ値にした状態での、要素の合計の最大値を求めることを考えます。ただし、許されている操作は「任意の2つの要素を選び、大きい方の値を2つの差（絶対値）で置き換える」というものだけです。例として、配列が [9, 12, 3, 6] の場合を考えてみましょう。この場合の出力は 12 になります。手順の例A[1] を A[1] − A[3] = 12 − 6 = 6 に置き換えます。→ 配列は [9, 6, 3, 6]A[3] を A[3] − A[2] = 6 − 3 = 3 に置き換えます。→ 配列は [9, 6, 3, 3]A[

問題の概要n 個の整数からなる配列が与えられたとき、その中に存在する「厳密に増加する（strictly increasing）部分配列」の中で、要素の合計が最大となるものを求めます。例として、次のような配列を考えてみましょう。[1, 2, 3, 2, 5, 1, 7]この配列には、厳密に増加している部分配列が3つ存在します。{1, 2, 3}{2, 5}{1, 7}それぞれの合計は 6、7、8 となり、この中で最大となるのは {1, 7} の合計 8 です。解き方の考え方この問題は、現在の部分配列の合計（current_sum）とこれまでの最大合計（max_sum）を追跡しながら配列を一度だけ

直線上にN個のステーションが並んでおり、それぞれが非負の放射出力を持っていると仮定します。各ステーションは、一定のルールに従って隣接するステーションの放射強度を高めます。例えば、ステーションiの放射強度がRであるとき、このステーションは左側では(i-1)番目のステーションの放射強度を「R-1」だけ、(i-2)番目のステーションを「R-2」だけ増やします。同様に右側でも、(i+1)番目のステーションに「R-1」、(i+2)番目のステーションに「R-2」を加えます。距離が1つ離れるごとに寄与は1ずつ減少し、その値が0以下になった時点で影響は及ばないものとします。具体例配列 Arr = [1, 2,

はじめに周囲長 P と表面積 A が与えられたとき、その条件を満たす直方体の中で体積が最大になるものを求める問題を考えてみましょう。例えば、周囲長 P が 24、表面積 A が 24 の場合、最大体積は 8 になります。直方体の各辺の長さを length(長さ)、breadth(幅)、depth(高さ)とすると、次の関係式が成り立ちます。周囲長:P = 4 × (length + breadth + depth)表面積:A = 2 × (length × breadth + breadth × depth + length × depth)体積:V = length × breadth × d

問題の概要 無限に続く数直線(−∞ から +∞)上で、位置 0 からスタートして指定されたターゲットに到達することを考えます。i 回目の移動では、左または右にちょうど i ステップ進むことができます。このとき、ターゲットに到達するために必要な最小の移動回数を求めます。 例えば、ターゲットが 2 の場合、最小ステップ数は 3 になります。移動の流れは「0 → 1 → -1 → 2」となります。 解法のアプローチ この問題を解くためには、以下の重要なポイントを押さえておく必要があります。 ターゲットが負の数であっても、数直線は原点を中心に対称であるため、正の数として扱って問題ありません。 基本

対数には log(x*y) = log(x) + log(y) という重要な性質があります。この性質を利用すると、「1からNまでのすべての対数値を計算するために、最低いくつの対数値を直接求めればよいか」という興味深い問題を考えることができます。 例として、Nが6の場合を考えてみましょう。このとき答えは 3 になります。 まず log(1) は常に0であるため、計算対象から除外します。 log(2) と log(3) は素数なので、独立に計算する必要があります。（ここまで2つ） log(4) は log(2) + log(2) で表せるため、既知の値を再利用すれば新たな計算は不要です。 log

問題の概要円周上に n 個のガソリンスタンドがあるとします。各スタンドについては、次の2種類のデータが与えられます。各ガソリンスタンドが保有している燃料の量あるガソリンスタンドから次のガソリンスタンドまでの距離このとき、トラックが円を一周しきれる出発地点のうち、最初の地点を求めるのが本問題の目的です。ただし、1リットルの燃料で1単位の距離を走行できるものと仮定します。具体例たとえば、4つのガソリンスタンドがあり、それぞれの「燃料量」と「次のスタンドまでの距離」が以下のように与えられているとします。[(4, 6), (6, 5), (7, 3), (4, 5)]この場合、トラックが一周できる最初

ある数 N が与えられたとき、N を割り算することで完全平方数（平方数）にできる最小の数を求める問題を考えてみましょう。たとえば N = 50 の場合、答えは 2 です。50 ÷ 2 = 25 となり、25 は 5 × 5 で表される完全平方数だからです。 考え方 完全平方数とは、素因数分解したときにすべての素因数の指数が偶数になる数のことです。この性質を利用すると、次の手順で問題を解くことができます。 N を素因数分解し、それぞれの素因数の指数（べき乗）を調べる。 指数が奇数になっている素因数をすべて見つけ、それらを掛け合わせる。 こうして得られた積こそが、N を完全平方数にするための最

はじめにn個の要素からなる配列が与えられたとき、その中から最小の要素(第1最小値)、2番目に小さい要素(第2最小値)、3番目に小さい要素(第3最小値)を見つける方法を解説します。ここで「2番目に小さい要素」とは、最小値より大きい値の中で最も小さいものを指し、「3番目に小さい要素」は2番目に小さい値より大きい値の中で最も小さいものを指します。アルゴリズムの考え方配列の各要素を先頭から順に走査し、それぞれの要素について以下の3つの条件を順番にチェックすることで、この問題を解くことができます。要素が現在の最小値(first)より小さい場合:3番目の値に2番目の値を、2番目の値に最小値を順にずらし、そ

問題の概要いくつかの点と整数 k が与えられたとき、中心が原点 (0, 0) にある円で少なくとも k 個の点を覆うための最小半径を求めます。例えば、点が (1, 1)、(-1, -1)、(1, -1) の3つで k = 3 の場合、すべての点を含むのに必要な半径は 2 となります。解き方のアプローチこの問題は、次の手順で効率よく解くことができます。各点と原点 (0, 0) とのユークリッド距離を計算します。比較だけが目的であれば、平方根の計算を省略できるため、距離の二乗(x² + y²)をそのまま使うと計算コストを抑えられます。求めた距離(の二乗)を昇順にソートします。ソート後のリストの k

問題の概要正の整数で構成された2次元マトリックス（行列）が与えられたとします。このとき、左上のセル (0, 0) から右下のセル (n-1, n-1) まで移動するために必要な最小ステップ数を求めるのが目的です。移動のルールは以下のとおりです。現在いるセルを (i, j) とすると、次のいずれかのセルに移動できます。(i, j + mat[i][j]) … 現在のセルの値の分だけ右へ移動(i + mat[i][j], j) … 現在のセルの値の分だけ下へ移動ただし、マトリックスの範囲を超えて移動することはできません。入力例例として、次のようなマトリックスを考えてみましょう。212111111こ