C++

問題の概要2つの数値が文字列として与えられているとします。これらを乗算し、その結果も文字列として返す必要があります。例えば、入力が「28」と「25」であれば、出力は「700」になります。数値が非常に大きい場合、通常の int 型や long long 型では扱えないことがあります。そこで、文字列のまま筆算のように計算することで、どんなに大きな数でもオーバーフローせずに正確な積を求められるのが、この手法の大きな利点です。解決のための手順num1 の桁数を n、num2 の桁数を m とします。2数の積は最大 n + m 桁になるため、長さ n + m の文字列 ans を「0」で初期化します。n

問題概要 2つの文字列 S と T が与えられ、「S は T の部分列（サブシーケンス）であるか」を判定する問題です。部分列とは、元の文字列からいくつかの文字を削除して得られる文字列で、残った文字の並び順は元のまま保たれているものを指します。 例えば、S = abc、T = adbrcyxd の場合、a、b、c がそれぞれ T の中に順番どおり現れるため、出力は True になります。 解き方（アルゴリズム） この問題は、2つのポインタを使った貪欲法（グリーディ法）で効率よく解くことができます。手順は以下の通りです。 s と t が完全に一致する場合は、true を返します。 n := s

ここでは、一部のマスのみが埋められた数独グリッドをC++で解く方法を解説します。数独とは9×9の数字グリッドであり、全体はさらに3×3のボックスに分割されています。数独を解くためには、以下のルールを守る必要があります。使用する数字は1から9までです。同じ行・同じ列・同じ3×3ボックス内に、同じ数字を重複して配置することはできません。バックトラッキングによる解法の考え方本記事ではバックトラッキング(バックトラック)アルゴリズムを使用して数独を解きます。空きマスに数字を仮に置いた後、その配置がルール上妥当かどうかを検証します。もし配置が不正であれば別の数字を試し、1〜9のすべての数字を試しても有効

二分木が与えられたとき、その木に含まれるすべての「右葉（右側につながった葉ノード）」の値の合計を求める問題を考えてみましょう。 例えば、次のような二分木が入力として与えられた場合を考えます。 この場合の出力は 17 になります。この二分木には値が 7 と 10 の2つの右葉が存在するためです。 解決のためのアプローチ この問題は、DFS（深さ優先探索）を利用することで効率的に解くことができます。手順は以下の通りです。 dfs() 関数を定義します。引数としてノード（node）とブール値のフラグ（add）を受け取ります。 node が null の場合は、何もせずに処理を終了して戻ります。

はじめに二分木（バイナリツリー）が与えられたとき、その中で最も深い位置にある葉ノード（deepest leaves）の値の合計を求めることを考えます。例えば、次のような二分木があるとします。この場合、最も深い葉ノードは 7 と 4 であり、出力は 11 になります。解法のアプローチこの問題は、深さ優先探索（DFS）を用いて各レベルごとのノードの値の合計を記録し、最後に最大深度に対応する合計を取得することで解けます。具体的には、以下の手順に従います。レベルごとの合計を保持するマップ m と、最大深度を記録する変数 maxDepth を定義するノードとレベルを受け取る再帰メソッド solve()

正の整数が与えられたとき、その数値に対応するスプレッドシート（Excelなど）の列タイトルを求める問題を考えます。対応関係は、1→A、2→B、26→Z、27→AA、28→AB のようになっています。例えば、入力が29の場合、出力は「AC」になります。解決のアプローチこの問題は、26進法の考え方を使って次の手順で解くことができます。n が0でない間、以下を繰り返します。n を n − 1 に更新するres に (n mod 26) + A のASCII文字を追加するn を n / 26 に更新するres を反転させるres を返すここで n を事前に1減らしているのは、列番号が1始まりである一方

スプレッドシートの列は、A、B、Cというようにアルファベット順にラベル付けされています。Zの次はAA、AB、…、ZZへと進み、その後はAAA、AAB、…と続いていきます。つまり、列番号1が「A」、列番号26が「Z」、列番号27が「AA」に対応します。本記事では、列番号が与えられたときに、対応する列名（アルファベット表記）を求める方法をC++で解説します。例えば、列番号が80なら「CB」、30なら「AD」が出力されます。考え方：26進法として扱う一見すると単純な26進数への変換のように思えますが、注意が必要です。この体系には「0」に相当する文字が存在しないからです。A〜Zはそれぞれ1〜26に対応

問題の概要 ここでは、各ノードの値が「0」または「1」のいずれかである二分木を扱います。求めるのは、値「1」を一切含まないすべての部分木を削除した後の木です。たとえば、次のような木が与えられた場合を考えてみましょう。 剪定後の木では、子孫のどこにも「1」を持たない部分木が丸ごと取り除かれます。重要なのは、葉ノードだけでなく、内部ノードであっても、その下の部分木全体に1が存在しなければ削除対象になるという点です。 解決のためのアプローチ この問題は、再帰を用いることで簡潔に解けます。ノードを受け取る再帰メソッド solve()（実装例では pruneTree()）を定義し、以下の手順で処理を進

整数の配列が与えられたとき、その中から3つの要素を選び、それらを三角形の3辺とした場合に実際に三角形を形成できる三つ組(トリプレット)の個数を求める問題を考えます。 例えば、入力が [2,2,3,4] の場合、答えは 3 となります。これは、1番目の 2 を使った [2,3,4]、2番目の 2 を使った [2,3,4]、そして [2,2,3] の3通りが有効であるためです。 解き方のアプローチ 三角形が成立する条件は「任意の2辺の和が、残りの1辺よりも大きい」ことです。配列をあらかじめソートしておけば、最大の辺だけを基準に判定すればよいことになり、Two Pointers(双方向ポインタ)技法

整数のみで構成される長さ n の整数型配列 Arr[] と、ある数 M が与えられます。この問題の目的は、要素の積が M と等しくなる Arr[] の三つ組（トリプレット）の個数を数えることです。 これには 3 重の for ループを使用します。arr[x] * arr[y] * arr[z] == M かつ x ≠ y ≠ z を満たす組み合わせが見つかるたびに、カウントを増やしていきます（0 ≦ x, y, z ＜ n）。 具体的な例で確認してみましょう。 入力 arr[]= { 1,2,3,0,2,4 }, M=24 出力 積が M となるトリプレットの数: 2 説明 arr[x] *

2つの整数 START と END が与えられ、この2つで数値の範囲を定義します。この記事のゴールは、範囲 [START, END] 内に存在する「素因数が2と3だけ」の数、すなわち 2a × 3b（a, b は 0 以上の整数）の形で表せる数を見つけ出し、その個数を求めることです。 調べ方はシンプルです。START から END まで順に各数値を走査し、それぞれの数が2と3だけで割り切れるかを確認します。割り切れる場合は実際に割って数を小さくしていき、どちらでも割れなくなった時点でループを抜けます。最終的にその数が1にまで約分されていれば、素因数は2と3のみであると判定できます。 それでは、

整数 N が与えられたとき、[1, N] の範囲内に存在する「桁に 0 を含む数」を見つけることが目標です。この問題は、10 から N までの数を順番に走査することで解決できます(1〜9 は一桁の数なのでチェックする必要がありません)。各数値に対して while ループを使い、一桁ずつ確認していきます。もし 0 の桁が見つかればカウントを増やして次の数へ進み、見つからなければ数を 10 で割りながら次の桁を調べます。これを数値が 0 より大きい間繰り返します。具体例で理解しよう例1入力N = 11出力1 から N までの範囲で 0 を桁に持つ数: 1解説i = 10 から i <= 11

本記事では、2つの整数 START と END で定義される範囲、および正の整数からなる配列 Arr[] が与えられたとき、範囲 [START, END] 内に存在し、配列のすべての要素で割り切れる数値を求める方法を解説します。 入出力例 入力例1 START=1 END=20 Arr[]= { 2, 4, 8 } 出力 配列の全要素で割り切れる数値の個数: 2 解説： 範囲 [1, 20] の中で、配列の全要素（2・4・8）すべてで割り切れるのは 8 と 16 の2つです。 入力例2 START=100 END=200 Arr[]= { 230, 321, 490, 521 } 出力 配列の

はじめに整数 N が与えられたとき、1 から N までの範囲に含まれる数のうち、「X で割り切れるが Y では割り切れない」数の個数を求めるのが本記事の目的です。具体例を見てみましょう。例1入力:N=20 X=5 Y=20出力:1からNまでのうちXで割り切れYでは割り切れない数: 2解説:5と15のみが5で割り切れ、10では割り切れません。例2入力:N=20 X=4 Y=7出力:1からNまでのうちXで割り切れYでは割り切れない数: 5解説:4、8、12、16、20 の5つの数は4で割り切れますが、7では割り切れません。プログラムのアプローチ整数 N を入力として受け取ります。関数 divisi

この記事では、2つの整数 START と END が与えられ、これらによって数値の範囲が定義されます。ゴールは、範囲 [START, END] 内に含まれる数値のうち、「その数値自身の0以外のすべての桁」で割り切れるものをすべて見つけ出すことです。 実装では、STARTからENDまで順番に数値を走査し、各数値についてwhileループを用いて「0以外のすべての桁で割り切れるか」を判定します。条件を満たした場合はカウントを1つ増やします。 それでは、具体例を使って理解を深めましょう。 例1 入力： START=10 END=20 出力： 0以外のすべての桁で割り切れる数値の個数: 5 説明： 1

本記事では、2つの整数N（探索範囲 [1, N] を定義）とD（差のしきい値）が与えられたとき、「数値 − その桁の合計 > D」という条件を満たす数が範囲内にいくつあるかを求める方法を解説します。解き方はシンプルです。1からNまでの数を順番に走査し、それぞれの数についてwhileループを使って桁の合計を計算します。その後、元の数と桁の合計の差がDより大きいかどうかを判定し、条件を満たしていればカウントを増やします。具体例で理解しよう例1入力：N=15 D=5出力：数値と桁の合計の差がDより大きい数: 6説明：10, 11, 12, 13, 14, 15 が条件を満たします。（10−1,

問題概要2つの整数 A と B、および数値の範囲を定義する START と END が与えられます。A 番目のタイルには白いペンキが、B 番目のタイルには黒いペンキが塗られています。そして、白と黒の両方のペンキが塗られたタイルは灰色（グレー）になるとします。このとき、START から END の範囲内に存在する「グレーのタイル」、つまり A と B の両方の公倍数となっている数の総数を求めることがゴールです。解き方は非常にシンプルです。START から END までの数値を順番に走査し、それぞれの数が A と B の両方の倍数であるかを判定します。条件を満たしていればカウントを1ずつ増やしてい

2つの整数START（開始）とEND（終了）が与えられ、これらによって数値の範囲が定義されます。この記事のゴールは、範囲[START, END]内に含まれる数値のうち、各桁の合計が指定された値Yと一致するものをすべて見つけ出すことです。解法はシンプルです。STARTからENDまでの数値を1つずつ走査し、それぞれの数値に対してwhileループを使って桁の合計を計算します。その合計がYと一致していればカウントを1増やし、すべての数値を調べ終えたときのカウントが答えとなります。具体例を見てみましょう。入力START=10 END=20 Y=4出力桁の合計がYと等しい数値の個数: 1説明数値13の各桁

問題の概要 2つの整数 START と END が与えられ、この間に数値の範囲が定義されます。この記事の目的は、範囲 [START, END] 内にある数のうち、次の3つの条件をすべて満たすものを見つけることです。 どの桁にも「0」が含まれていないこと 各桁の合計(桁和)が指定された数 N と一致すること 指定された数 M で割り切れること 解き方はシンプルです。START から END まで順に数を走査し、while ループを使って各数の桁和を計算します(すべての桁が 0 以外である場合のみ)。その桁和が N と一致し、かつ M で割り切れる場合にカウントを1増やします。 それでは、具体

ソート済みの整数配列が与えられたとき、「指定した値 K 以下の要素がいくつあるか」を求めるのがこの問題の目的です。ここでは、線形探索による素朴な方法と、二分探索を使った効率的な方法の2通りを解説します。 問題の例 入力 Arr[]= { 1, 2, 3, 14, 50, 69, 90 }　K = 12 出力 K以下の要素数: 3 説明 1, 2, 3 の3つが 12 以下です。 入力 Arr[]= { 12, 13, 13, 13, 14, 50, 54, 100 }　K = 14 出力 K以下の要素数: 5 説明 12, 13, 13, 13, 14 の5つが 14 以下です。 方法