C++

問題の概要 整数型の配列 arr が与えられ、最初はインデックス 0 にいるものとします。1ステップごとに、次のいずれかの方法でジャンプが可能です。 インデックス i から i + x へ移動（条件：i + x < n） インデックス i から i - x へ移動（条件：i - x >= 0） arr[i] と arr[j] が同じ値で、i と j が異なる場合、i から j へ移動 ここで n は配列のサイズです。この問題の目的は、配列の最後のインデックスに到達するために必要な最小ジャンプ回数を求めることです。 入力例と出力 たとえば、入力が次のとおりだったとします。 {20

整数型の配列 target が与えられているとします。ここで、すべての要素が 1 である初期配列 A から出発し、次の手順を実行することができます。現在配列に含まれる全要素の合計を x とします。0 以上 n 以下の範囲(n は配列のサイズ)からインデックス i を選択し、A の i 番目の要素の値を x に置き換えます。この手順は必要な回数だけ何度でも繰り返せます。このとき、初期配列 A からターゲット配列を作成することが可能かどうかを判定してください。不可能な場合は false を返します。例えば、入力が [3,9,5] の場合、答えは true になります。手順は以下の通りです。初期状態

問題の概要 n件の注文からなるリストがあるとします。各注文には「集荷（P）」と「配達（D）」の2つのサービスが含まれています。ここでの目的は、配達[i]が必ず集荷[i]よりも後に行われるという制約を満たす、すべての有効な集荷・配達の順列を数えることです。 答えは非常に大きな値になる可能性があるため、結果は 10^9 + 7 で割った余りを返します。 入力例と出力例 たとえば、入力が 2 の場合、出力は 6 になります。考えられるすべての有効な順序は次のとおりです。 (P1, P2, D1, D2) (P1, P2, D2, D1) (P1, D1, P2, D2) (P2, P1, D1,

数字の配列が与えられたとき、その中から任意の個数の数字を選び、好きな順序で連結して作ることができる「3の倍数」の最大値を求めます。答えは非常に大きな数になる可能性があるため、文字列として返します。条件を満たす組み合わせが存在しない場合は、空文字列を返します。 たとえば、入力が [7, 2, 8] の場合、出力は 87 になります。 解法のポイント この問題を解く鍵となるのは、「ある整数が3の倍数であること」と「その各位の数字の総和が3の倍数であること」が同値であるという有名な性質です。これを利用すると、次のような戦略が立てられます。 3行からなる2次元配列 d を定義する(d[x mod 3

問題概要 二分木のルートが与えられたとき、二分探索木（BST）でもある部分木の中から、ノード値の合計が最大となるものを見つけることを考えます。 例えば、次のような入力が与えられた場合を考えてみましょう。 この場合の出力は 20 になります。これは選択されたBSTに含まれるすべてのノードの値の合計です。 解法のアプローチ この問題は、木を後順トラバーサル（子→親の順）で処理し、各ノードを根とする部分木に関する情報をボトムアップに集約することで効率的に解けます。具体的な手順は以下の通りです。 Data という構造体を作成します。sz（部分木のノード数）、maxVal（最大値）、minVal（最

n個の頂点からなる無向木(ツリー)があるとします。頂点には1からnまでの番号が付けられており、カエルは頂点1からジャンプを開始します。カエルは、現在いる頂点に隣接している「未訪問」の頂点へ、1秒でジャンプすることができますが、一度訪れた頂点へ戻ることはできません。ジャンプ先の候補が複数ある場合は、いずれも等しい確率でランダムに1つを選んで移動します。逆に、行ける未訪問の頂点がなくなったカエルは、その場で永遠に跳ね続けることになります。 木は辺の配列として与えられます。ここで求めたいのは、「t秒後にカエルが頂点targetの上にいる確率」です。 問題の例 たとえば、入力が n = 7、t = 2

問題の概要 n人のエンジニアがいるとします。彼らには1からnまでの番号が振られており、2つの配列 speed と efficiency が与えられます。speed[i] と efficiency[i] は、それぞれi番目のエンジニアの作業速度と効率を表します。 このとき、最大k人のエンジニアで構成されるチームの最大パフォーマンスを求める必要があります。答えは非常に大きな値になる可能性があるため、109 + 7 で割った余りを返してください。 チームのパフォーマンスの定義 チームのパフォーマンスは、「チームメンバーの速度の合計」に「メンバーの中で最も低い効率」を掛けた値として定義されます。 入

問題の概要 大きさがまちまちの 3n 個のスライスからなるピザがあるとします。私と友人2人は、次のルールに従ってピザを取っていきます。 私が任意のスライスを1枚選びます。 友人のAmalは、私が選んだスライスの反時計回り方向に隣接するスライスを取ります。 友人のBimalは、私が選んだスライスの時計回り方向に隣接するスライスを取ります。 ピザのスライスがなくなるまで、この手順を繰り返します。 各スライスの大きさは、時計回りの順に並べた環状配列 slices として与えられます。求めるのは、私が手にできるスライスの大きさの合計の最大値です。 入出力例 入力が [9, 8, 6, 1, 1,

問題の概要 文字列 s が与えられたとき、その最長ハッピープレフィックス（happy prefix）を求める問題です。ハッピープレフィックスとは、「文字列自身を除いた空でない接頭辞であり、かつ同時に接尾辞でもある文字列」のことです。該当するものが存在しない場合は、単に空文字列を返します。 たとえば入力が madam の場合、出力は m になります。madam 自身を除くと、接頭辞は m、ma、mad、mada の4つ、接尾辞も m、am、dam、adam の4つ存在します。このうち「接頭辞でもあり接尾辞でもある」最長の文字列が m というわけです。 解決アプローチ：KMPアルゴリズムのLPS

この記事では、動的計画法(DP)を使って「良い文字列(good strings)」の総数を効率的に求めるC++の手法を解説します。問題の定義長さnの2つの文字列s1とs2、そしてもう1つの文字列evilが与えられます。ここで「良い文字列」とは、以下の条件をすべて満たす文字列のことです。長さがnである辞書順でs1以上である辞書順でs2以下である部分文字列としてevilを含まない答えは非常に大きな数になる可能性があるため、109 + 7で割った余りを返します。入出力例例として、n = 2、s1 = bb、s2 = db、evil = a の場合を考えてみましょう。このときの出力は51になります。内

問題の概要あるシェフがいて、n個の料理それぞれについて満足度のデータを収集したとします。シェフはどの料理も1単位時間で調理できるものとします。ここで、料理のライクタイム係数（Like-time coefficient）とは、その料理を調理するまでにかかった時間（それ以前の料理の調理時間を含む）に、その料理の満足度を掛けた値、すなわち time[i] * satisfaction[i] として定義されます。求めたいのは、料理の準備を終えた後にシェフが得られるライクタイム係数の合計の最大値です。料理は任意の順序で調理でき、最大値を得るために一部の料理をあえて作らない（捨てる）ことも許されています。

問題の概要AmalとBimalが石を使ったゲームを行います。複数の石が一列に並んでおり、それぞれの石には配列 stoneValue で与えられる数値が割り当てられています。二人は交互に手番を持ち、Amalが先攻です。各プレイヤーの手番では、列の先頭に残っている石から1個・2個・3個のいずれかを取ることができます。各プレイヤーのスコアは「取った石の値の合計」で、初期値は0です。ゲームの目的は最も高いスコアで終えることで、スコアの高い方が勝者となります。同点になる場合もあります。ゲームはすべての石がなくなるまで続きます。ここでは、両者が常に最適な手を選ぶものと仮定します。Amalが勝てば Amal

問題概要n × 3 のサイズのグリッドを考えます。各セルは赤・黄・緑の3色のうち、ちょうど1色で塗る必要があります。ただし、「隣接するセル同士は同じ色にできない」という制約があります。ここで言う隣接とは、上下または左右で直接接触しているセルのことです。グリッドの行数 n が与えられるので、このグリッドを条件を満たすように塗り分ける方法が全部で何通りあるかを求めます。答えは非常に大きな値になる可能性があるため、109 + 7 で割った余りを返してください。例えば、入力が n = 1 の場合、出力は 12 になります。解法のポイント：行のパターンを2種類に分類するこの問題を効率的に解く鍵は、1行ご

あるプログラムが配列 A の要素を出力することを考えてみましょう。しかし、このプログラムには小さなミスがあり、各要素の後に空白（スペース）が出力されていませんでした。そこで、出力された一つの文字列だけが残っている場合、元の配列を復元できるでしょうか？ここでは、配列の各要素は 1 以上 k 以下の範囲に含まれることが分かっているものとします。 つまり、文字列 s と整数 k が与えられたとき、元の配列を復元できる方法が何通りあるかを求めるのがこの問題です。答えは非常に大きな値になる可能性があるため、109 + 7 で割った余りを返します。 例えば、入力が S = 1318、k = 2000 の場

問題の概要 整数型の配列 nums と整数 k が与えられたとき、次の条件を満たす空でない部分列の合計の最大値を求めます。すなわち、部分列の中で隣り合う任意の2つの数 nums[i] と nums[j](i < j)について、常に j - i <= k が成り立つことです。 ここでいう部分列とは、元の配列からいくつかの要素を削除し、残った要素を元の順序のまま保ったものを指します。 入力例 入力が [10, 2, -9, 5, 19]、k = 2 の場合を考えてみましょう。このとき最適な部分列は [10, 2, 5, 19] となり、その合計は 36 になります。 解き方のポイント

問題概要n人の人がおり、1から40までの番号が付けられた40種類の異なる帽子があります。ここで「hats」という2次元リストが与えられ、hats[i] は i 番目の人が好む帽子の番号のリストを表します。このとき、n人全員が互いに異なる帽子をかぶるような組み合わせの総数を求めてください。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返します。例えば、入力が [[4,6,2],[4,6]] の場合、出力は 4 になります。これは [4,6]、[6,4]、[2,4]、[2,6] の4通りの選び方が存在するためです。解法のアプローチこの問題は、ビットマスク動的計画法（B

問題概要 m × n の行列 mat と整数 k が与えられます。mat の各行は非減少順(昇順)にソートされているものとします。各行からちょうど1つの要素を選んで配列を構成するとき、考えられるすべての組み合わせの中から、K番目に小さい配列の合計を求めるのが目的です。 たとえば、次のような行列が入力されたとしましょう。 1311246 ここで k = 5 のとき、出力は 7 になります。各行から1要素ずつ選んだとき、合計が小さい順に並べると [1,2]、[1,4]、[3,2]、[3,4]、[1,6] となり、5番目の合計値が 7 だからです。 解法の考え方 すべての組み合わせを総当たりで生成

この記事では、2つの文字列 S と T が与えられたとき、S の部分列のうち T と一致するものが何通りあるかを数える問題を、C++と動的計画法（DP）を使って解く方法を解説します。 部分列（サブシーケンス）とは？ 部分列とは、元の文字列から一部の文字（0個でも可）を削除して作られる新しい文字列のことであり、残った文字の相対的な順序は崩れません。例えば、「ACE」は「ABCDE」の部分列ですが、「AEC」は順序が入れ替わっているため部分列にはなりません。 問題の例 入力として「baalllloonnn」と「balloon」が与えられた場合、T に一致する S の部分列は 36通り 存在します。

二分木の後順走査（ポストオーダートラバーサル）とは？ 二分木の後順走査（ポストオーダートラバーサル）は、「左の子 → 右の子 → 親ノード」の順ですべてのノードを訪問する探索手法です。再帰を使えば簡潔に書けますが、本記事では再帰を使わない反復処理（イテレーティブ）による実装方法を詳しく解説します。 例として、次のような二分木を考えてみましょう。 この木を後順走査すると、出力は次のようになります。 [9, 15, 7, 10, -10] 後順走査は、木のメモリ解放や数式表現木の評価など、「子ノードを先に処理してから親を処理したい」という場面で活躍する、基本的かつ重要なアルゴリズムです。 反復処

C++には、データを効率的に格納・検索するための連想コンテナとして「set」と「multiset」が用意されています。どちらも標準テンプレートライブラリ(STL)に属するコンテナであり、要素への高速なアクセスや挿入を可能にするデータ構造です。しかし、両者には重複要素の扱いをはじめとする重要な違いがあります。本記事では、setとmultisetの相違点を比較表で整理し、実際のコード例と実行結果を通じて、それぞれの動作の違いをわかりやすく解説します。 setとmultisetの主な違い 項目setmultiset 定義連想コンテナの一種で、キーと値のペアを格納します。各要素の値がそのまま