C++

問題概要数値のリスト jobs と整数 k が与えられます。すべての仕事をちょうど k 日間で完了させたいと考えています。ただし、仕事は必ず与えられた順序どおりに実行する必要があり、各日には少なくとも1つのタスクを割り当てなければなりません。仕事 i の難易度は jobs[i] で表され、ある日の作業全体の難易度は、その日に実行した仕事の中で最も高い難易度となります。つまり、その日の最大値がコストとして加算されます。このとき、k 日間で仕事をすべて完了させるために必要な難易度の合計の最小値を求めてください。入力例jobs = [2, 3, 4, 6, 3], k = 2出力例8この場合、1日目

問題の概要 単語のリストと行幅 k が与えられたとします。このとき、各行がちょうど k 文字になるようにテキストを配置し、全体を「完全な両端揃え」に整形する必要があります。各行にはできるだけ多くの単語を詰め込み、必要に応じて余分な半角スペース「 」を補って、行幅を正確に k 文字に合わせます。 単語間の余分なスペースは、できるだけ均等に分散させるのがルールです。スペースの総数が単語の間隔数で割り切れない場合は、左側の空きスロットに右側よりも多くのスペースを割り当てます。ただし、テキストの最終行だけは左揃えとし、単語間に余分なスペースを挿入しません。 たとえば、入力が [The, grumpy,

問題概要 数値のリスト nums と整数 k が与えられたとき、互いに重なり合わない空でない部分リストをちょうど k 個選び、それらの合計値の総和が最大となるようにします。なお、k は nums の要素数以下であると仮定して構いません。 たとえば、入力が nums = [11, -1, 2, 1, 6, -24, 11, -9, 6]、k = 3 である場合、出力は 36 になります。これは、部分リストとして [11, -1, 2, 1, 6]、[11]、[6] を選ぶと、その合計はそれぞれ 19、11、6 となり、総和が 19 + 11 + 6 = 36 になるためです。 アルゴリズムの考

問題の概要 数値のリスト nums と整数 k が与えられたとき、nums を「各部分集合の合計がすべて等しくなる」ような k 個の部分集合に分割できるかどうかを判定する問題です。 例えば、nums = [4, 2, 6, 5, 1, 6, 3]、k = 3 の場合、出力は True になります。[6, 3]、[6, 2, 1]、[4, 5] のように分割すると、それぞれの合計がすべて 9 で等しくなるためです。 解決のアプローチ この問題は、深さ優先探索（DFS）によって各要素をどの部分集合に割り当てるかを全て試すことで解けます。手順は以下の通りです。 関数 check() を定義する。配

問題概要 数値のリスト nums が与えられます。このリストの要素を振り分けて合計が等しくなる2つの集合を作成し、そのときの合計値の最大を求めます。 たとえば、入力が nums = [2, 5, 4, 6] の場合、出力は 6 になります。[2, 4] と [6] という2つの集合を作れば、どちらも合計が 6 となり、これより大きい等しい合計は実現できないためです。 解決アプローチ(動的計画法) 各要素には「集合Aに入れる」「集合Bに入れる」「どちらにも入れない」という3つの選択肢があります。素朴な全探索では O(3^n) の計算量が必要になりますが、2つの集合の合計の差分を状態として管理する

問題概要文字列 s が与えられたとき、s 自身を除いた上で、同時に接尾辞（サフィックス）にもなる最長の接頭辞（プレフィックス）を見つけることを考えます。該当する接頭辞が存在しない場合は、空文字列を返します。具体例たとえば、入力が madam の場合、出力は m になります。自身を除く接頭辞は「m」「ma」「mad」「mada」の4つ、接尾辞は「m」「am」「dam」「adam」の4つ存在します。このうち接頭辞でもあり接尾辞でもある最大の文字列は「m」です。解法のアプローチこの問題は、KMP文字列検索アルゴリズムで使われる LPS配列を利用すると効率的に解けます。LPS配列の各要素には、「その位

問題の概要 互いに重なり合う可能性のある閉区間のリストが与えられます。ここで、「区間を1つ削除し、残りの区間をマージしたうえで、残った区間の数を数える」という操作を考えます。本記事のテーマは、この操作を行ったときに残れる区間数の最大値を求めることです。 たとえば、入力が intervals = [[5, 8], [6, 7], [7, 10], [9, 11]] の場合、出力は 2 になります。それぞれの区間を削除した結果を比較してみましょう。 [5, 8] を削除した場合 → マージ結果は [6, 11] の1つ [6, 7] を削除した場合 → マージ結果は [5, 11] の1つ [7

数値 n が与えられたとき、その桁を並び替えてできる「次に大きい順列」を求めます。n がすでに最大の順列（桁が降順に並んでいる状態）である場合は、最小の順列（昇順）へと折り返します。 例えば、入力が n = 319 の場合、出力は 391 になります。 解法のアプローチ この問題は、C++ の標準ライブラリにある next_permutation と同じ考え方で解くことができます。右端から見て初めて昇順が崩れる位置（ピボット）を探し、ピボットより大きい数字のうち最小のものと交換した後、ピボットより右側を昇順に並べ替えることで、全体として「次に大きい」並びを実現します。具体的には、以下のステップ

問題の概要ある整数 n が与えられます。この n を 0 に減らすために、次の3種類の操作を任意の順序・回数で実行できます。操作1：n を 1 減らす操作2：n が偶数の場合、n を n / 2 減らす（結果として n は半分になる）操作3：n が 3 の倍数の場合、n を 2 × (n / 3) 減らす（結果として n は 1/3 になる）求めたいのは、n を 0 にするまでに必要な操作回数の最小値です。入出力の例入力が n = 16 の場合、出力は 5 になります。手順は以下の通りです。16 は偶数なので、「n / 2 減らす」操作を4回繰り返すと 16 → 8 → 4 → 2 → 1 と

2つのリスト「sales（販売情報）」と「buyers（購入者情報）」が与えられているとします。sales の各要素は [day, price] という形式で、そのパッケージが指定された日に指定された価格でのみ販売されることを表します。一方、buyers の各要素は [payday, amount] という形式で、その購入者が給料日（payday）以降に使える金額 amount を持っていることを意味します。 ここで、各購入者が購入できるパッケージは最大1つまで、また各パッケージは1人の購入者にしか販売できないという条件のもとで、売却できるパッケージの最大数を求めます。 たとえば、入力が s

パターン p と文字列 str が与えられたとき、str がそのパターンと同じ規則に従っているかどうかを判定する問題です。ここで「従っている」とは、パターン中の各文字と str 中の空でない単語との間に全単射（一対一対応）が成り立つことを意味します。 たとえば pattern = "cbbc"、str = "word pattern pattern word" の場合、文字 c が単語 word に、文字 b が単語 pattern に対応しているため、結果は True（1）となります。 解法のアプローチ この問題は、パターンと単語列をそれぞれ「初出順

問題の概要この問題では、N個の整数からなる配列 arr[] と整数 m が与えられます。求めるのは、「最大値にアクセスするたびにその値が1減少する」という条件下で、配列から取り出せる最大値の合計です。問題の説明配列の最大要素を取り出して合計（maxSum）に加算し、取り出した最大値を1減らす――この操作をm回繰り返したときの最終的なmaxSumを求めます。具体的な例で理解しよう入力例arr[] = {3, 6, 7, 8, 8}, m = 3出力例23処理の流れ1回目: 処理前 {3, 6, 7, 8, 8} → 最大値 = 8、合計 = 8、処理後 {3, 6, 7, 7, 8} 2回目:

問題概要n 個のノードが円形に配置されていると仮定します。すべてのノードがちょうど 1 本の辺で接続され、かつどの 2 つの辺も互いに交差しないように、n / 2 本の辺を配置する方法の数を求める必要があります。答えが非常に大きくなる可能性があるため、その場合は結果を 10^9 + 7 で割った余りを返します。たとえば、入力が n = 4 の場合、出力は 2 になります。これは、4 つのノードを交差なくペアにする方法が 2 通り存在するためです。解決のためのアプローチこの問題は動的計画法(DP)を用いることで効率的に解けます。実は、この問題の答えはカタラン数(Catalan Number)と深

この記事では、配列 arr[]（要素数 n の整数値）と、それぞれ整数 k を含む Q 個のクエリが与えられたとき、「接尾辞内に存在する異なる整数の個数」を効率的に求める C++ プログラムを紹介します。 問題の概要 各クエリに対して、インデックス k から n までの範囲、すなわち arr[k] から arr[n] までに含まれる一意な要素の数を求める必要があります。 ※ 配列は 1 インデックス（1 起点）とします。 入出力例 入力 arr[] = {5, 1, 2, 1, 6, 5}, n = 6, Q = 3, query = {1, 3, 4} 出力 4 4 3 解説 クエリ

問題概要この問題では、n 個の区間 (L, R) を格納した2次元配列 arr[][2] と、整数値からなる Q 個のクエリが与えられます。各クエリで指定された数値が、いずれかの区間内に存在するかどうかを判定するプログラムを作成するのが課題です。問題の詳細： 各クエリについて、その数値が与えられた区間のいずれかに含まれるかを確認し、結果を出力します。なお、区間同士が重複（オーバーラップ）することはないものとします。入力例arr[n][2] = { {5, 7}, {1, 3}, {9, 12} } n = 3 Q = 2 query = {10, 4}出力例Yes No解説クエリ1の「10」は

この問題では、円周上に配置された n 個のボックスが与えられます。さらに、2つの整数 a と b のペアからなる Q 個のクエリが与えられ、各クエリについてボックス同士を接続できるかどうかを判定するプログラムを作成します。 問題の概要 各クエリを処理する際には、直前のクエリで引いた棒（ロッド）との交差を妨げないように、ボックス a と ボックス b を棒で結べるかどうかを確認する必要があります。判定結果に応じて「Possible（可能）」または「Not Possible（不可能）」を出力します。 入出力例で理解しよう 入力 n = 6Q = 3Queries = {{1, 3}, {2, 5}

問題の概要 2次元のバイナリ行列（各要素が0または1の行列）が与えられたとき、すべての要素が1で構成されている部分行列の総数を求めることを考えます。 たとえば、次のような入力が与えられた場合を考えてみましょう。 110 110 001 この場合の出力は10になります。これは、1×1の行列が5個、2×1の行列が2個、1×2の行列が2個、さらに2×2の行列が1個存在するためです。 解決アプローチ この問題は、各行をヒストグラムとして捉え、単調スタック（monotonic stack）を利用することで効率的に解くことができます。具体的には、各行までの「連続する1の高さ」を記録した配列を作成し

この記事では、文字列 str と、それぞれ2つの値 L と R から構成される Q 個のクエリが与えられたとき、各クエリに対して部分文字列 [L…R] が回文（前から読んでも後ろから読んでも同じ文字列）であるかどうかを判定するプログラムを C++ で作成する方法を解説します。問題の概要各クエリを処理する際には、指定された範囲 L から R までで切り出した部分文字列が回文であるかどうかを確認する必要があります。具体例で問題を理解しよう入力str = abccbeba , Q = 3 Query[][] = {{1, 4}, {0, 6}, {4, 6}}出力Palindrome Not Pal

この問題では、サイズ n の配列 arr[] と、それぞれ2つの値 L と R からなる Q 個のクエリが与えられます。各クエリに対して、L番目に小さい数値と R番目に小さい数値の絶対差を返すプログラムを作成するのが課題です。 問題の概要 各クエリを解くためには、L番目に小さい要素と R番目に小さい要素が元の配列のどのインデックスに位置するかを特定し、そのインデックス同士の差（絶対値）を求める必要があります。 例を使って問題を理解しましょう。 入力 arr[] = {8, 4, 1, 5, 2} Q = 2 Queries[][] = {{2, 4}, {1, 5}} 出力 1 2 説明 {2

数値のリスト nums が与えられます。ここで、「リスト内の連続した部分リスト(サブリスト)のうち、回文になっているものを削除する」という操作を考えます。この操作を繰り返してリストを空にするとき、必要となる最小の操作回数を求めるのが本問題です。 例えば、入力が nums = [6, 2, 4, 4, 2, 10, 6] の場合、答えは 2 になります。まず部分リスト [2, 4, 4, 2](回文)を削除すると、残りのリストは [6, 10, 6] となり、これも回文なので削除できます。合計 2 回の操作でリストを空にできるためです。 解法のアプローチ この問題は、区間を対象としたメモ化再帰(