C++

正の整数 n が与えられたとき、それを少なくとも2つ以上の正の整数の和に分割し、それらの整数の積が最大になるようにします。求めたいのは、そのとき得られる最大の積です。 例として n = 10 の場合を考えてみましょう。10 = 3 + 3 + 4 と分割すると、3 × 3 × 4 = 36 となり、これが最大値となります。したがって答えは 36 です。 解法のアプローチ この問題は、メモ化再帰（トップダウンDP）を使うことで効率的に解けます。手順は以下の通りです。 solve() メソッドを定義する。引数は n、配列 dp、フラグ flag n が 0 の場合は 1 を返す dp[n] が

負でない整数 n が与えられたとき、0 以上 10n 未満の範囲に存在する「すべての桁が一意（重複なし）」である数 x の個数を求める問題を考えてみましょう。例えば n = 2 の場合、0 から 100 未満までの数のうち、11、22、33、44、55、66、77、88、99 のように同じ数字が重複している数を除外した個数、つまり 91 が答えとなります。解法のアプローチこの問題は、桁ごとに選べる数字の組み合わせを順番にかけていくことで効率的に解くことができます。手順は以下の通りです。n が 0 の場合は 1 を返します（0 のみが該当するため）。n は最大でも 10 桁しか考慮できないため、

容量がそれぞれ x リットルと y リットルの2つの容器（ジョッキ）があるとします。水は無限に供給されており、この2つの容器だけを使ってちょうど z リットルの水を計量できるかどうかを判定するのが、この問題の目的です。z リットルが計量可能であるためには、操作の終了時点で、どちらか一方または両方の容器内の水の合計が正確に z リットルになっている必要があります。許容される操作この問題では、次の3種類の操作のみが許可されています。どちらかの容器に水を満杯まで注ぐ。どちらかの容器の水をすべて捨てて空にする。片方の容器からもう片方の容器へ水を移す。ただし、移し先が満杯になるか、移し元が空になるまで続

問題の概要 相異なる正整数からなる集合が与えられたとき、次の条件を満たす最大の部分集合(要素数が最も多い部分集合)を見つける問題を考えます。 部分集合内の任意の2つの要素のペア (Si, Sj) について、Si % Sj == 0 または Sj % Si == 0 が常に成り立つ 例えば、入力が [1, 2, 3] の場合、[1, 2] または [1, 3] が答えになります(どちらも条件を満たす大きさ2の部分集合です)。 アプローチ：ソート+動的計画法(DP) この問題は、最長増加部分列(LIS)と同じ発想の動的計画法で効率よく解けます。まず配列を昇順にソートするのがポイントです。ソー

問題概要 正整数 a と、桁ごとの配列形式で与えられる非常に大きな正整数 b があるとき、ab mod 1337 を計算する問題を考えます。たとえば、a = 2、b = [1,0] の場合、210 = 1024 となるため、出力は 1024 になります。 アルゴリズムの流れ この問題は、繰り返し二乗法（バイナリ法）と再帰的な処理を組み合わせることで効率的に解くことができます。具体的な手順は以下のとおりです。 powerMod() メソッドの定義： 底（base）と指数（power）を受け取ります。 m := 1337、ret := 1 で初期化します。 power が 0 でない間、次の処理

ウィグルシーケンスとは隣り合う数値の差が正と負で厳密に交互に現れる数列を「ウィグルシーケンス」と呼びます。最初の差は正でも負でも構いません。また、要素が2つ未満の数列は自明にウィグルシーケンスとみなされます。例えば [1,7,4,9,2,5] はウィグルシーケンスです。隣接する数値の差が (6, -3, 5, -7, 3) となり、正と負が交互に現れているためです。一方、[1,4,7,2,5] は最初の2つの差がどちらも正であるため、[1,7,4,5,5] は最後の差が0になってしまうため、それぞれウィグルシーケンスではありません。問題の概要整数列が与えられたとき、ウィグルシーケンスとなってい

問題概要単方向連結リストが与えられたとき、その中からランダムに1つのノードを選び、その値を返す getRandom() メソッドを実装することを考えます。重要な条件は、リスト内のすべてのノードが同じ確率で選ばれるという点です。たとえば、リストが [1, 2, 3] である場合、getRandom() は 1、2、3 のいずれかをそれぞれ 1/3 の確率で返します。アルゴリズム（リザーバーサンプリング）リストの長さが事前にわからなくても対応できるよう、ここでは「リザーバーサンプリング」と呼ばれる手法を使用します。getRandom() メソッド内での手順は次のとおりです。ret := -1、le

問題の概要1からnまでの整数が昇順に並んだリストを考えます。まず左から右へ向かって、先頭の数値とその後1つおきの数値を削除し、リストの末尾まで進みます。次に同じ操作を今度は右から左へ向かって行い、残った数値の中から右端の数値とその後1つおきの数値を削除します。この左右交互の削除操作を、数値が1つだけ残るまで繰り返します。長さnのリストから始めたとき、最後に残る数値を求めるのがこの問題です。具体例：n = 9 の場合入力が n = 9 のとき、削除の手順は以下のようになります（取り除かれる数値には下線を付けています）。1, 2, 3, 4, 5, 6, 7, 8, 92, 4, 6, 82, 6

本記事では、整数のリストとして与えられたデータが、有効なUTF-8エンコーディングであるかどうかを判定するアルゴリズムについて解説します。1つのUTF-8文字は1バイトから4バイトの長さになり、それぞれのバイト長に応じて特定のビットパターンを持つという特徴があります。 UTF-8エンコーディングの基本ルール UTF-8には以下のような性質があります。 1バイト文字：先頭ビットが0で、その後にUnicodeコードポイントが続きます。 nバイト文字：先頭のnビットがすべて1であり、n+1番目のビットが0。その後ろに続くn-1個のバイトは、いずれも上位2ビットが「10」で始まります。 これらのル

問題の概要 長さ n の整数配列 A が与えられます。Bk を「配列 A を時計回りに k 個分回転させた配列」とするとき、回転関数 F(k) は次のように定義されます。 F(k) = 0 × Bk[0] + 1 × Bk[1] + … + (n−1) × Bk[n−1] このとき、F(0)、F(1)、…、F(n−1) の中から最大値を求めるのが本問題の目的です。 具体例：A = [4, 3, 2, 6] の場合 回転ごとの値は以下のように計算できます。 F(0) = (0×4) + (1×3) + (2×2) + (3×6) = 0 + 3 + 4 + 18 = 25 F(1) = (0×

正の整数 n が与えられ、これに対して次の操作を繰り返し適用できるものとします。n が偶数の場合：n を n / 2 に置き換えるn が奇数の場合：n を n + 1 または n - 1 のいずれかに置き換えるこのとき、n を 1 にするまでに必要な最小の操作回数を求めるのが本問題です。問題の例たとえば n = 7 の場合、答えは 4 になります。次のような操作列が存在するからです。7 → 8 → 4 → 2 → 17 → 6 → 3 → 2 → 1解法のアプローチ（貪欲法）この問題は、以下の手順で貪欲に解くことができます。ret := 0、n := x と初期化するn > 1 の間、次

問題概要 重複する要素を含む整数型配列が与えられたとき、指定したターゲット値が出現するインデックスの中から1つをランダムに選択して返すことを考えます。ターゲット値は必ず配列内に存在すると仮定できます。 例えば、配列が [1, 2, 3, 3, 3] の場合、pick(3) を呼び出すと、インデックス 2、3、4 のいずれかが等確率で返されます。 アルゴリズムの考え方 この問題は「リザバーサンプリング（Reservoir Sampling）」と呼ばれる手法を使うことで、配列を1回走査するだけで各候補を等確率で選択できます。手順は以下の通りです。 結果を格納する変数 ret を -1、カウンタ

問題概要 空でない整数の配列 a0, a1, a2, …, an-1(0 ≤ ai < 231)が与えられます。このとき、ai XOR aj の最大値(0 ≤ i, j < n)を求める必要があります。 例えば、入力が [3,10,5,25,2,8] の場合、出力は 28 になります。これは 5 XOR 25 = 28 となるためです。 解法のアプローチ この問題は、各数値を2進数のビット列として扱い、二分トライ(バイナリトライ)と呼ばれるデータ構造を用いることで効率的に解くことができます。各ノードは 0 と 1 の2つの子を持ち、数値を最上位ビットから順に挿入していきます。そし

問題の概要2つの空でない連結リストが与えられ、それぞれが非負の整数を表しているとします。最上位の桁がリストの先頭に配置されており、各ノードには1桁の数字が格納されています。この2つの数を加算し、その結果を連結リストとして返す必要があります。例えば、リスト [7, 2, 4, 3] と [5, 6, 4] を加算すると、結果は [7, 8, 0, 7] になります。解法のアプローチ最上位の桁が先頭にあるため、下位の桁から順に足し算を行う必要があります。しかし、連結リストは後方のノードへ直接アクセスするのが苦手です。そこで、スタックのLIFO(後入れ先出し)の性質を活用します。各リストのノードをあ

問題の概要 シングルスレッドのCPU上でいくつかの関数を実行する状況を考えてみましょう。各関数には 0 から N-1 までの一意な ID が割り振られており、関数の開始・終了のタイミングを記録したログがタイムスタンプ順に与えられます。 各ログは「{function_id}:{start | end}:{timestamp}」という形式の文字列です。たとえば「0:start:3」は ID 0 の関数がタイムスタンプ 3 の始まりの時点で実行を開始したことを、「1:end:2」は ID 1 の関数がタイムスタンプ 2 の終わりの時点で完了したことを意味します。ここでいう排他時間（exclusiv

ある店では複数の商品が販売されており、それぞれの商品には価格が設定されています。しかし、この店には「特別オファー（スペシャルオファー）」と呼ばれる割引セットも存在します。1つの特別オファーは、1種類以上の異なる商品の組み合わせを、まとまった販売価格で提供するものです。ここで、商品ごとの価格リスト、利用可能な特別オファーの集合、そして各商品について購入する必要のある個数が与えられます。求めるのは、これらの商品をちょうど必要な個数だけ購入するときに支払うべき最低金額です。特別オファーを最適に活用することで、合計額を抑えられる可能性があります。問題の形式各特別オファーは配列として表現されます。配列の

Dota2の世界には、Radiant（ラディアント）とDire（ダイア）という2つの勢力が存在するとします。Dota2の上院は、この2つの勢力から選ばれた議員で構成されており、上院はゲーム内の変更について決議を行おうとしています。投票はラウンド制で進行し、各ラウンドで各議員は次の2つの権利のうちいずれか1つを行使できます。 他の議員の権利を禁止（Ban）する：ある議員は、別の議員の権利を今回および今後のすべてのラウンドで失わせることができます。 勝利を宣言する：まだ投票権を持っている議員がすべて同じ勢力に属している場合、その議員は勝利を宣言し、ゲーム内の変更に関する決定を下すことができます。

問題の概要整数の配列 asteroids が与えられ、一列に並んだ小惑星を表しているとします。各小惑星において、絶対値はそのサイズを、符号は移動方向を表します(正の値は右方向、負の値は左方向)。すべての小惑星は同じ速度で移動します。この問題の目的は、すべての衝突が発生し終わった後の小惑星の状態を求めることです。2つの小惑星が出会うと、サイズが小さい方が爆発します。サイズが同じ場合は両方が爆発します。また、同じ方向に移動している2つの小惑星は、速度が等しいため決して出会うことはありません。例えば、入力が [5, 10, -5] の場合、出力は [5, 10] になります。これは、10 と -5

問題の概要整数型の配列 nums が与えられ、この配列に対して複数回の操作を行うことを考えます。各操作では、任意の nums[i] を 1 つ選んで削除し、その値に等しいポイント nums[i] を獲得できます。ただし重要なルールとして、nums[i] - 1 または nums[i] + 1 に等しい要素はすべて同時に削除しなければなりません。初期時点のポイントは 0 です。これらの操作を適用したときに獲得できるポイントの最大値を求めるのがこの問題です。たとえば、入力が [3, 4, 2] の場合、出力は 6 になります。理由は次のとおりです。まず 4 を削除すると 4 ポイントを獲得でき、同

問題の概要本記事では、「ドミノ」と「トロミノ」という2種類の形状を使ったタイル敷き詰め（タイリング）問題をC++で解く方法を解説します。これらのピースは、以下のように回転させて使用することができます。タイリングでは、盤面上のすべてのマスを必ずタイルで覆わなければなりません。また、2つのタイリング方法は、盤上の4方向に隣接する2つのセルにおいて、片方のタイリングだけがその両方のマスを同じタイルで占有している場合に限り「異なる」とみなされます。入力と出力の例整数Nが与えられたとき、2×Nのボードを敷き詰める方法が何通りあるかを求めます。例えば、入力が3の場合、出力は5となります。敷き詰め方は以下の