C++

問題概要n×n の行列を考えます。行列の各セル（マス）には何らかの値が割り当てられています。移動は、i 行目のセルから (i+1) 行目の斜め下のセルにのみ行うことができます。つまり、セル (i, j) から移動できるのは、セル (i+1, j-1) とセル (i+1, j+1) の2か所だけです。この条件に従って最上行から最下行まで移動する経路の中で、通過するセルの値の合計が最大となる経路を求めてください。入力例{ {5, 6, 1, 17}, {-2, 10, 8, -1}, { 3, -7, -9, 4}, {12, -4, 2, 2} }この場合、最大合

問題概要 共通の要素を含みうる2つのソート済み配列が与えられます。このとき、どちらか一方の配列の先頭から出発し、2つの配列のいずれかの末尾に到達するまでの「最大合計パス」の和を求めてください。ただし、ある配列からもう一方の配列へ移動できるのは共通要素の位置のみです。なお、共通要素が同じインデックスに存在する必要はない点に注意してください。 期待される計算量は O(m+n) です。ここで m は arr1[] の要素数、n は arr2[] の要素数を表します。 具体例 入力: arr1[] = {2, 3, 7, 10, 12} arr2[] = {1, 5, 7, 8} 出力: 35

問題の概要 この問題では、整数の配列と合計値（上限）が与えられます。求めるのは、「要素の合計が指定された値以下となる部分配列（連続する要素の並び）」のうち、合計が最大になるものです。 配列の長さを n とするとき、長さが n 以下の任意の部分配列を対象に、合計が指定値を超えない範囲で最大の合計を見つけなければなりません。 入力と出力の例 入力： array = {3, 5, 1, 8, 2, 9}, sum = 25 出力： 25 解説： 合計が25以下となる部分配列のうち最大なのは {5, 1, 8, 2, 9} で、その合計はちょうど25です。配列全体の合計は28なので上限を超え、これが

問題の概要この問題では、整数の配列が与えられます。私たちのタスクは、最大で1つの要素を削除したときに得られる最大合計サブ配列を求めるプログラムをC++で作成することです。つまり、配列から1つの要素を取り除いたときに、残りの要素の合計が最大になるような要素を見つける必要があります。具体例で問題を理解する入力: array = {5, 1, 9, 2, -1, 7}出力: 24解説: 配列から -1 を削除すると、考えられるすべての組み合わせの中で最大の合計 24 が得られます。解法のアプローチこの問題に対する単純な解決策の1つは、配列の最小要素を見つけて、残りのすべての要素の合計を計算する方法で

問題の概要整数のコレクションが与えられたとき、そのすべての順列（並べ替えのパターン）を求めることを考えます。ただし、配列に重複した要素が含まれている場合は、見た目が同じ順列は結果から除外する必要があります。例えば、配列が [1, 1, 3] の場合、期待される出力は次のようになります。[[1,1,3], [1,3,1], [3,1,1]]解法のアプローチ：バックトラッキング（再帰）この問題は、再帰的なバックトラッキングを使うことで効率的に解くことができます。基本的な手順は以下の通りです。リストとインデックス idx を引数に取る再帰関数を用意します。最初は idx = 0 から開始します。id

スパイラルマトリックスとは行列（マトリックス）の要素を螺旋状に出力する問題を考えてみましょう。まず最初の行全体を左から右へ出力し、次に最終列を上から下へ、続いて最終行を右から左へ、さらに最初の列を下から上へと出力します。この一連の流れを内側へ向かって繰り返すことで、行列の要素を螺旋状に表示できます。例として、次のような3行6列の行列を用意しました。123456789101112131415161718この行列を螺旋状に出力すると、結果は次のようになります。1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11アルゴリズムの手順この問題は、以下の手順で解くことが

問題の概要連結リストと値 x が与えられたとき、リストを2つのグループに分割することを考えます。具体的には、「x 未満のノード」がすべて「x 以上のノード」よりも前に来るように並べ替えます。ただし、各グループ内ではノードの元の相対的な順序を保持しなければなりません。例えば、リストが [1,4,3,2,5,2]、x = 3 の場合、出力は [1,2,2,4,3,5] となります。3未満のノード（1, 2, 2）が先頭に集まり、3以上のノード（4, 3, 5）がその後に続きます。解法のアプローチこの問題は、ダミーノードを2つ使うことでシンプルに解決できます。手順は以下の通りです。初期値 -1 を持

グレイコード（Gray Code）とは、隣り合う2つの値が必ず1ビットだけ異なるという性質を持つ二進数体系のことです。本記事では、コードのビット数を表す非負整数 n が与えられたときに、グレイコードの列を出力する方法を解説します。グレイコードの列は必ず 0 から始まる必要があります。例えば、入力が 2 の場合、出力は [0, 1, 3, 2] となります。これは、0 のグレイコードが 00、1 が 01、2 が 11、3 が 10 であるためです。隣接する値同士を比較すると、それぞれ1ビットしか変わっていないことが確認できます。解法のアプローチこの問題は、以下の手順で解くことができます。結果を

二分木が与えられたとき、それをレベル順トラバーサル（Level Order Traversal）、いわゆる幅優先探索（BFS）の手法で走査することを考えます。例えば、次のような二分木があるとします。この木に対してレベル順トラバーサルを行うと、ノードは上の階層から左から右へと順番に訪問され、結果は以下のようになります。[10, 5, 16, 8, 15, 20, 23]アルゴリズムの手順この問題を解くためには、キュー（queue）を利用します。手順は以下の通りです。ノードを格納するためのキュー que を定義しますルートノードをキューに挿入しますキューが空になるまで、以下の処理を繰り返しますキュ

三角形が与えられたとき、頂点から底辺までの最小パス合計を求める問題を考えてみましょう。各ステップでは、下の行にある隣接する数字のいずれかに移動することができます。 例えば、次のような三角形があるとします。 [ [2], [3,4], [6,5,7], [4,1,8,3] ] この場合、上から下への最小パス合計は 11 となります（2 + 3 + 5 + 1 = 11）。 アルゴリズムの手順 この問題は、動的計画法（Dynamic Programming）を使うことで効率的に解くことができます。手順は以下の通りです。 動的計画法で使用するためのテーブル（配列

回文分割とは 入力として与えられた文字列を、分割後のすべての部分文字列が回文になるように分割することを「回文分割（Palindrome Partitioning）」と呼びます。この記事では、与えられた文字列を回文に分割するために必要な最小のカット数を求めるアルゴリズムを解説します。 例として、文字列「ababbbabbababa」を考えてみましょう。この場合、3回のカットで次のように回文へ分割できます。 a | babbbab | b | ababa アルゴリズムの考え方（動的計画法） この問題は動的計画法（DP）を用いて効率的に解くことができます。まず、n × n の2次元テーブルを2つ用

問題概要円周上に n 個のガソリンスタンド（給油所）があるとします。各給油所について、次の2種類のデータが与えられます。各給油所が保有している燃料の量ある給油所から次の給油所までの距離このとき、車が円周を一周できる最初の出発地点を求めるのが目的です。ただし、車は「1単位の燃料で1単位の距離」を走行できるものと仮定します。例として、4つの給油所があり、燃料量と次の給油所までの距離が [(4, 6), (6, 5), (7, 3), (4, 5)] と与えられている場合を考えてみましょう。この場合、車が一周を完走できる最初の出発地点は「2番目の給油所」です。したがって、出力は start = 1（

本記事では、逆ポーランド記法（Reverse Polish Notation／後置記法）で書かれた数式をC++で評価する方法を解説します。逆ポーランド記法は、演算子をオペランドの後に置く記法で、括弧が不要になるためコンパイラや電卓プログラムなどで広く使われています。この種の式（後置式）を評価する際には、スタックというデータ構造を利用するのが定番のアプローチです。 評価の基本的な考え方 後置式を左から右へ読み進めながら、次のように処理を行います。 オペランド（数値）が現れたら、スタックにプッシュする。 演算子が現れたら、スタックから2つの要素をポップし、正しい順序で演算を実行する。その結果を再

プログラミングにおいて、式の中に含まれる括弧が正しく対応しているか（バランスしているか）を判定することは、構文解析などでよく使われる基本的な処理です。対象となる括弧は ()、{}、[] の3種類です。 例えば、()[(){()}] はすべての括弧が正しく入れ子になっているため有効な文字列ですが、{[}] は閉じ括弧の順序が対応していないため無効です。 アルゴリズムの考え方 この問題はスタック（stack）を使うことで効率的に解決できます。手順は以下の通りです。 式の文字列を先頭から順に走査します。 現在の文字が開き括弧（(、{、[）であれば、スタックにプッシュします。 現在の文字が閉じ括弧（

問題概要 候補となる数値の集合(すべての要素は一意)とターゲットの数値が与えられたとき、候補の数値の合計がターゲットと一致するすべての一意な組み合わせを求めます。ただし、同じ数値を候補から複数回選ぶことはできません。 例えば、要素が [2,3,6,7,8] でターゲットが 8 の場合、出力は [[2,6],[8]] となります。 解法のアプローチ:バックトラッキング この問題は再帰的なバックトラッキングを用いて解くのが一般的です。再帰関数 solve() を定義し、引数として現在のインデックス、配列 a、残りのターゲット値 b、現在の組み合わせを保持する配列 temp を渡します。 アルゴリズ

問題の概要 集合 [1, 2, 3, ..., n] には、合計 n! 通りの異なる順列が存在します。すべての順列を辞書順に並べてラベルを付けると、n = 3 の場合は次のシーケンスが得られます。 [123, 132, 213, 231, 312, 321] このとき、n と k が与えられた場合、k 番目の順列シーケンスを返すのが本問題の目的です。制約として、n は 1 以上 9 以下、k は 1 以上 n! 以下の範囲にあります。 アルゴリズムの考え方 すべての順列を生成して k 番目を探す方法は非効率です。そこで、階乗の性質を利用したアプローチを用います。 先頭の桁にどの数字を置くかを決

連結リスト(リンクリスト)が与えられたとき、そのリストを右にk回転させることを考えます。ここでkは非負の整数とします。例えば、リストが [1,2,3,4,5,NULL] で k = 2 の場合、出力は [4,5,1,2,3,NULL] となります。この問題は、リストを一度環状(循環リスト)につなぎ変え、適切な位置で環を切断することで効率的に解けます。計算量はO(n)、追加のメモリはO(1)で済むのがポイントです。アルゴリズムの手順リストが空の場合はNULLを返すlen := 1 とする(リストの長さを数える)tail := head というノードを作成するtail の next がNULLでな

ユニークパス（Unique Paths）問題とはn行m列のグリッドの左上のマスにロボットが配置されているとします。ロボットは任意の時点で「下」または「右」のどちらかにのみ移動でき、グリッドの右下のマス（下の図では「END」と表示）を目指します。このとき、始点から終点まで到達できる経路が何通り存在するかを求めるのが、この「ユニークパス」問題です。例として、m = 3、n = 2 の場合、グリッドは次のようになります。RoboENDこの場合の出力は 3 です。つまり、開始位置から終了位置まで到達する方法は全部で3通りあります。それぞれの経路は以下の通りです。右 → 右 → 下右 → 下 → 右下

あるロボットが n × m のグリッド（n行・m列）の左上の角に配置されているとします。ロボットは任意の時点で下方向または右方向にしか移動できません。そして、グリッドの右下の角（下図では「END」と表示）を目指して移動します。ただし、グリッドの中には障害物としてマークされたセルが存在する場合があります。このとき、「スタート地点からゴール地点まで到達できる一意な経路は何通りあるか」を求めるのがこの問題です。例えば、グリッドが [[0,0,0],[0,1,0],[0,0,0]] である場合、盤面は次のようになります（1が障害物を表します）。RoboObsENDこの場合の出力は 2 となります。つま

最小経路和（Minimum Path Sum）とは？ 非負整数が格納された m × n の行列 が与えられたとき、左上の角から右下の角へ移動する経路の中で、通過する数値の合計が最小となるもの を求めるのが「最小経路和」問題です。 ただし、移動できる方向は任意の時点で下または右のみに制限されています。 たとえば、次のような行列が与えられた場合を考えてみましょう。 131151421 この場合の出力は 7 となります。最適な経路は 1 → 3 → 1 → 1 → 1 であり、これが通過する数値の合計を最小化します。 アルゴリズムの考え方（動的計画法） この問題は、動的計画法（DP）を使って効率的