C++

問題概要 1本の木、1匹のリス、そして複数のナッツがフィールド上にあります。それぞれの位置は2次元グリッドのセルで表現されます。この問題の目的は、リスがすべてのナッツを集めて木の下に1個ずつ運ぶときの最小移動距離を求めることです。 リスの行動には次の制約があります。 一度に持てるナッツは最大1個 移動は上下左右の4方向で、隣接するセルへのみ可能 距離は移動回数(ステップ数)で表される たとえば、入力が「高さ: 5 / 幅: 7 / 木の位置: [2,2] / リスの位置: [4,4] / ナッツ: [[3,0], [2,5]]」の場合、出力は 12 となります。 解法のポイント まず、

n個のプロセスがあると仮定します。各プロセスには、PID（プロセスID）と呼ばれる一意の識別子が割り当てられており、さらにPPID（親プロセスID）も持っています。各プロセスが持てる親プロセスは1つだけですが、子プロセスは1つでも複数でも構いません。これはまさに木構造と同じ形です。PPIDが0になるプロセスは1つだけであり、それはそのプロセスに親が存在しないことを意味します。また、すべてのPIDは一意な正の整数です。問題の概要ここでは、2つの整数リストを使ってプロセスの一覧を表現します。1つ目のリストには各プロセスのPIDが含まれ、2つ目のリストにはそれに対応するPPIDが含まれます。このとき

問題概要 文字列 s と文字列のリスト dict が与えられたとします。s の中に dict に含まれる部分文字列が存在する場合、その部分を太字タグ <b> と </b> のペアで囲みます。ただし、次のルールに従う必要があります。 2つの部分文字列が重なり合っている場合は、1組の太字タグでまとめて囲む。 太字タグで囲まれた2つの部分文字列が連続している場合も、それらを結合して1組のタグで囲む。 例えば、入力が s = abcxyz123、dict = [abc, 123] の場合、出力は <b>abc</b>xyz<b>123&l

問題概要正の整数 x が与えられたとき、各桁の数字を掛け合わせると x と等しくなるような、最も小さい正の整数 b を求めます。そのような答えが存在しない場合は 0 を返します。例えば、入力が 48 の場合、出力は 68 となります。これは 6 × 8 = 48 を満たす整数の中で最も小さいものだからです。解法のアプローチこの問題は、次の手順で解くことができます。ret := 0、mul := 1 として初期化するa < 2 の場合は、a をそのまま返すi を 9 から 2 まで 1 ずつ減らしながらループするa mod i が 0 である間、以下を繰り返すret := i * mul

1からnまでの数字が昇順に並んだ長さnの配列があるとします。この配列から生成できる「完全順列（derangement：撹乱順列）」の総数を求めるのが本記事のテーマです。 組合せ数学において、完全順列とは、集合の要素を並べ替えた順列のうち、どの要素も元の位置に現れないようなものを指します。答えは非常に大きな数になる可能性があるため、109 + 7で割った余りを返すこととします。 例えば、入力が3の場合、出力は2になります。元の配列が [1, 2, 3] であるとき、条件を満たす完全順列は [2, 3, 1] と [3, 1, 2] の2通りだけだからです。 解法のアプローチ この問題は動的計画法

キーボードで文字「A」を入力する状況を想像してみてください。ここでの目標は、わずか4種類のキー操作だけを使って、テキストフィールドにできるだけ多くの「A」を表示することです。使用できるキーは「A」「Ctrl」「C」「V」の4つです。「A」の数を最大化するには、次のショートカット操作を組み合わせます。Ctrl + A … すべてを選択Ctrl + C … コピーCtrl + V … 貼り付け問題の例たとえば、キーストローク数が7回だとすると、出力は9になります。具体的な操作手順は次のとおりです。「A」を3回入力(この時点で3文字)Ctrl + A(3文字をすべて選択)Ctrl + C(コピー)C

問題概要n 個のノードを持つ二分木が与えられたとき、元の木からちょうど1本の辺を削除することで、その木を「ノード値の合計が等しい2つの木」に分割できるかどうかを判定するのがこの問題です。例えば、次のような入力が与えられたとします。この場合、出力は true になります。解法のアプローチこの問題は、各部分木の合計値を事前にすべて計算しておき、その中に「木全体の合計の半分」と一致する値が存在するかを確認することで解けます。手順は以下の通りです。部分木の合計値を格納するためのスタック st を用意します。solve() 関数を定義します。引数としてノードを受け取ります。ノードが null の場合は

問題の概要深さが5より小さい二分木を、3桁の整数のリストで表すことを考えます。木の深さが5未満であれば、この木は3桁の整数のリストとして完全に表現できます。リスト内の各整数は、次のような意味を持っています。百の位：そのノードの深さ D（1 ≤ D ≤ 4）を表します。十の位：そのノードが属するレベル内での位置 P（1〜8）を表します。位置の付け方は完全二分木の場合と同じです。一の位：そのノードの値 V（0 ≤ V ≤ 9）を表します。求めたいのは、根（ルート）から葉までのすべての経路における値の合計です。たとえば入力が [113, 215, 221] の場合、出力は 12 になります。このリス

問題概要 「HH:MM」形式で表された時刻が与えられます。このとき、現在の時刻に含まれている数字だけを再利用して、次に近い時刻を生成するのが課題です。各数字は何度でも繰り返し使用できます。 例えば、入力が「19:34」の場合、出力は「19:39」になります。数字 1・9・3・4 のみを使って作れる時刻の中で、最も近い未来の時刻が 19:39 だからです。「19:33」も同じ数字で作れますが、これは翌日の 19:33 を意味するため、実際には 23時間59分後の時刻になってしまいます。 解法のアプローチ この問題は、あり得る時刻をすべて試す総当たり(ブルートフォース)法で効率よく解けます。手順

問題の概要2次元のバイナリ配列（グリッド）が与えられます。ここでいう「島」とは、1（陸地）が上下左右方向（水平または垂直）に連結されたグループのことです。グリッドの四方の端はすべて水に囲まれているものと仮定できます。このとき、異なる島の数を数えることが課題です。2つの島が「同じ」であるとみなされるのは、片方を平行移動（回転や反転は含まない）することでもう片方と一致させられる場合です。たとえば、次のような入力が与えられたとします。11011100000000111011この場合の出力は 3 となります。解法のアプローチこの問題は、DFS（深さ優先探索）を使って各島の形状を「移動経路の文字列」とし

昇順にソートされた配列があるとします。この配列の中からターゲットとなる値を検索し、見つかった場合はそのインデックスを、存在しない場合は -1 を返す関数を定義する必要があります。ここでのポイントは、配列のサイズが不明であるという点です。配列には ArrayReader インターフェースを通じてしかアクセスできず、ArrayReader.get(k) のように呼び出すことで、インデックス k の位置にある要素を取得できます。例えば、入力が array = [-1,0,3,5,9,12]、target = 9 の場合、9 は配列内に存在し、そのインデックスは 4 なので、出力は 4 となります。解

ここでは、昇順にソートされた循環リンクリストのノードが1つ与えられたとき、値 insertVal を適切な位置に挿入し、挿入後もソートされた状態を保つ関数を実装する方法を解説します。問題の概要引数として渡されるノードは、リスト内の任意の1ノードへの参照であり、必ずしも先頭ノードとは限りません。挿入に適した位置が複数存在する場合は、どこに挿入しても構いません。また、以下のようなケースにも対応する必要があります。リストが空の場合：新しい単一ノードからなる循環リンクリストを作成し、そのノードへの参照を返すリストが空でない場合：元のノードをそのまま返す例として、head = [3,4,1]、inser

問題の概要2つの配列 words1 と words2 が与えられ、それぞれを1つの文とみなします。さらに、類似した単語ペアのリスト pairs も与えられるので、この2つの文が類似しているかどうかを判定するのが本問題です。例えば、words1 = [great, acting, skills]、words2 = [fine, drama, talent] という入力に対して、類似ペアが [[great, good], [fine, good], [acting, drama], [skills, talent]] であれば、この2つの文は類似していると判断できます。類似関係の性質この問題におけ

整数のキューが与えられたとき、その中で重複していない（一意な）整数のうち最初に現れるものを取り出したい場面を考えてみましょう。この問題は、FirstUniqueというクラスを実装することで解決できます。 FirstUniqueクラスは次の2つの操作を提供します。 コンストラクタ：初期状態のキューとなる整数の配列を受け取って初期化します。 showFirstUnique()：キューの中で最初に現れる一意な整数の値を返します。一意な整数が存在しない場合は -1 を返します。 add(value)：指定した値をキューに追加します。 動作例 例えば、[2, 3, 5] で初期化し、以下の順にメソッ

問題概要二分木が与えられ、ルートから任意の葉ノードへ至る各パスが一つのシーケンスを形成するとします。このとき、与えられた整数配列（文字列）が、その二分木における有効なシーケンスであるかどうかを判定するのが本記事のテーマです。判定対象の文字列は、整数配列 arr の各要素を連結したものとして得られ、パス上のすべてのノードの値を連結した結果がシーケンスとなります。例として、次のような二分木を考えてみましょう。ここで arr = [0,1,0,1] が与えられた場合、出力は True になります。これは、パス 0 → 1 → 0 → 1（緑色で示された経路）が有効なシーケンスだからです。その他の有効

問題概要 数字のみで構成された文字列が与えられます。この文字列をもとに、考えられるすべての有効なIPアドレスの組み合わせを復元して返すことが求められます。有効なIPアドレスとは、0から255までの範囲の整数4つをドット（.）で区切って並べた形式のものです。 たとえば、入力が「25525511135」であれば、出力は「255.255.11.135」と「255.255.111.35」の2通りになります。 解決のアプローチ この問題はバックトラッキング（深さ優先探索）を使うことで効率よく解けます。文字列を4つのセグメントに分割しながら、各セグメントが0～255の範囲に収まる有効な数値かどうかを順に

二分木と値 v、深さ d が与えられたとき、指定された深さ d の位置に値 v を持つノードからなる新しい行を追加する必要があります。ここで、ルートノードは深さ 1 とします。この操作を行う際には、以下のルールに従います。操作のルール深さ d-1 に存在するすべての有効なツリーノード N に対して、値 v を持つ 2 つの新しいノードを作成し、それぞれ N の左部分木のルートおよび右部分木のルートとして配置します。その際、N の元の左部分木は新しい左側ノードの左部分木へ、元の右部分木は新しい右側ノードの右部分木へと移動します。また、深さ d が 1 の場合、つまり深さ d-1 が存在しないとき

問題概要まず、根のない木（unrooted tree）について考えてみましょう。これは閉路（サイクル）を持たない無向グラフのことです。入力として与えられるのは、もともと N 個のノードを持つ木（ノードの値は 1 から N までの重複しない整数）に、余分な辺を 1 本追加したグラフです。追加された辺は 1 ～ N の中から選ばれた 2 つの異なる頂点を結び、既存の辺とは重複しません。最終的なグラフは 2 次元配列 edges として渡されます。edges の各要素はペア [u, v]（u < v）であり、ノード u と ノード v を結ぶ無向辺を表します。求めるのは、その辺を取り除けば残り

n個の都市がm本のフライト（路線）で結ばれている状況を考えてみましょう。各フライトは出発地 u から到着地 v へ、料金 w で移動できるものとします。すべての都市とフライトの情報に加え、出発都市 src と目的地 dst が与えられたとき、「最大k回の乗り継ぎ（ストップ）以内で src から dst まで移動するときの最安料金」を求めるのがこの問題の目的です。条件を満たす経路が存在しない場合は -1 を返します。問題の例たとえば、入力が次のようになっている場合を考えます。n = 3edges = [[0,1,100], [1,2,100], [0,2,500]]src = 0、dst = 2

問題概要 二分木・ターゲットノード・値Kが与えられたとき、ターゲットノードから距離Kにあるすべてのノードの値をリストとして返す問題を考えます。 たとえば、入力が root = [3,5,1,6,2,0,8,null,null,7,4]、target = 5、K = 2 の場合、出力は [7,4,1] となります。これは、ターゲットノードから距離2の位置にあるノードの値が 7、4、1 だからです。 解法の考え方 この問題を解くには、まずDFS(深さ優先探索)で各ノードの親へのポインタを記録し、その後ターゲットノードを起点としてBFS(幅優先探索)を行います。二分木は通常、子から親へ辿れないた