C++

サイズ m × n の金鉱グリッドが与えられます。各マスにはそのマスに含まれるゴールドの量を表す整数が書かれており、0 は空のマスを意味します。以下の条件のもとで、収集できるゴールドの最大量を求めるのがこの問題の目的です。 問題の条件 マスに到達するたびに、そこにあるすべてのゴールドを回収します。 現在位置からは、上下左右のいずれかに1歩移動できます。 同じマスは一度しか訪問できません。 ゴールドが 0 のマスは絶対に訪れてはいけません。 たとえば、入力が [[0,6,0],[5,8,7],[0,9,0]] の場合、答えは 24 になります。これは「9 → 8 → 7」という経路をたどるこ

問題の概要 サイコロシミュレーターは、1回のロールごとに1から6までのランダムな数値を生成します。ここで、「同じ数字 i を rollMax[i] 回(1-indexed)より多く連続して出してはならない」という制約をジェネレーターに導入することを考えます。整数型の配列 rollMax と整数 n が与えられたとき、ちょうど n 回のロールで得られる異なる出目列(シーケンス)の総数を返してください。2つのシーケンスは、少なくとも1つの要素が異なっていれば別のものとみなされます。 例えば、n = 2、rollMax = [1,1,2,2,2,3] の場合、答えは 34 になります。サイコロを2回

2人の人物それぞれの空き時間スロットのリスト slots1 と slots2、および会議の所要時間 d が与えられたとします。このとき、両者にとって都合がよく、かつ所要時間 d 以上の長さを持つ最も早い時間帯を見つける必要があります。条件を満たす共通の時間帯が存在しない場合は、空の配列を返します。時間スロットは [start, end] という2要素の配列形式で表され、start から end までの範囲を示します。また、同じ人物の空き時間スロット同士は重ならないものと仮定できます。つまり、同じ人物の任意の2つのスロット [s1, e1] と [s2, e2] について、必ず s1 >

この記事では、確率を扱う興味深いアルゴリズム問題「奇妙なコインの投げ方」をC++で解く方法を解説します。動的計画法（DP）を使った効率的な解法を見ていきましょう。 問題の概要 いくつかのコインがあり、i番目のコインは投げたときに表が出る確率が prob[i] であるとします。すべてのコインをちょうど1回ずつ投げたとき、表が target 枚になる確率を求めてください。 例えば、prob 配列が [0.5, 0.5, 0.5, 0.5, 0.5] で target が 0 の場合、出力は 0.03125 となります。これは、5枚すべて裏になる確率 (0.5)^5 を意味しています。 解法のアプロ

問題の概要 フォルダのリストが与えられたとき、その中に含まれるすべてのサブフォルダを取り除き、残ったフォルダを任意の順序で返すことを考えます。ここで、あるフォルダ folder[i] が別のフォルダ folder[j] の内部に位置している場合、folder[i] は folder[j] のサブフォルダとみなされます。パスは「/folder1/subfolder2/…」のような形式で表現されます。 入力例 [/myfolder,/myfolder/secondfolder,/another/document,/another/document/extrafolder,/another/fina

2次元行列 matrix が与えられたとき、左上隅を (row1, col1)、右下隅を (row2, col2) として定義される長方形領域内の要素の合計を求める問題を考えます。問題の例例えば、次のような行列があるとします。3014256321120154101710305上の表で青色に塗られた長方形は (2,1) と (4,3) によって定義されており、この領域内の要素の合計は 8 になります。したがって、sumRegion(2, 1, 4, 3)、sumRegion(1, 1, 2, 2)、sumRegion(1, 2, 2, 4) というクエリを実行すると、それぞれ 8、11、12 が

整数 n が与えられたとき、1 から n までの数を辞書式順序（lexicographic order）で返す問題を考えます。例えば n = 13 が与えられた場合、出力は [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9] となります。これは数値の大小順ではなく、数を文字列として比較したときの順序に従うためです。つまり「1」の次は「2」ではなく「10」が来ます。アルゴリズムの考え方この問題は、次の手順で O(n) の時間計算量で解くことができます。サイズ n の配列 ret を定義する現在の数 curr を 1 で初期化するi を 0 から n - 1 ま

DNA配列について考えてみましょう。ご存知の通り、すべてのDNAはA、C、G、Tという4種類のヌクレオチド(塩基)の連なりで構成されています。例えば「ACGAATTCCG」のような文字列です。DNAを研究する際には、配列内に繰り返し現れるシーケンス(部分列)を特定することが重要になる場合があります。本記事では、DNA分子の中で2回以上出現する10文字長の配列(部分文字列)をすべて見つけるメソッドをC++で実装します。例えば、入力が「AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT」の場合、出力は[AAAAACCCCC, CCCCCAAAAA]となります。解決のアプローチこの問題

0 ≤ m ≤ n ≤ 2147483647 を満たす範囲 [m, n] が与えられたとき、この範囲に含まれるすべての整数のビット単位AND（論理積）を求めることを考えます。たとえば、範囲が [5, 7] の場合、5 AND 6 AND 7 = 4 となるため、答えは 4 になります。アルゴリズムの考え方範囲内のすべての数値を順番にANDしていくのは非効率です。そこで、m と n の2進表現に注目します。連続する整数同士をANDすると、下位のビットは必ずどこかで 0 になるため、結果として残るのは m と n の共通の上位ビット（共通プレフィックス）だけです。この性質を利用すると、次の手順で解

整数型の配列が与えられ、配列内に異なる2つのインデックス i と j が存在するかどうかを判定する問題を考えます。条件は「nums[i] と nums[j] の絶対差が t 以下」かつ「i と j の絶対差が k 以下」であることです。例えば、入力が [1,2,3,1]、k = 3、t = 0 の場合、条件を満たすペアが存在するため true を返します。解法アプローチこの問題は、平衡二分探索木（C++では multiset）を利用することで効率的に解けます。手順は以下の通りです。空の集合 s を用意し、n を nums 配列のサイズとします。i を 0 から n − 1 までループさせます。

2次元平面上に置かれた2つの軸に平行な長方形について、それらが覆う領域の合計面積を求める問題を考えます。各長方形は、左下の頂点と右上の頂点の座標によって定義されます。下図のように、第1の長方形は左下 (A, B)・右上 (C, D)、第2の長方形は左下 (E, F)・右上 (G, H) として表されます。解き方のアプローチこの問題を解くための手順は以下の通りです。まず、2つの長方形が重なっているかどうかを判定します。C ≤ E、A ≥ G、B ≥ H、D ≤ F のいずれかが成り立つ場合、2つの長方形は重ならないため、それぞれの面積の和 (C − A) × (D − B) + (G − E)

問題概要 整数型の配列が与えられたとき、その中から「n/3 の切り捨て値（⌊n/3⌋）よりも多く出現する要素」をすべて見つけることを考えます。ここで n は配列のサイズです。 例えば、入力が [1,1,1,3,3,2,2,2] の場合を考えてみましょう。1 は 3 回、2 は 3 回出現しており、どちらも ⌊8/3⌋ = 2 より大きいため、答えは [1, 2] となります。 ここで重要な性質として、「n/3 を超える回数出現する要素は最大でも 2 種類しか存在しない」ことが挙げられます。もし 3 つの異なる要素がそれぞれ n/3 回より多く現れると、合計出現回数が n を超えてしまい矛盾する

数値と演算子からなる式の文字列が与えられたとき、括弧を挿入して数値と演算子をグループ化するすべての可能なパターンについて計算を行い、得られる結果をすべて求めることを考えましょう。ここで使用できる演算子は「+」「-」「*」の3種類です。 例えば、入力が「2*3-4*5」の場合、出力は [-34, -14, -10, -10, 10] となります。これは次の5通りの括弧の付け方に対応しています。 (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10

問題の概要 整数の配列が与えられ、そのうちちょうど2つの要素だけが一度しか現れず、それ以外の要素はすべて2回現れるものとします。このとき、一度しか現れない2つの数を見つける関数を定義する必要があります。 例えば、配列 [1, 2, 3, 1, 5, 2] が与えられた場合、出力は [3, 5] となります。 解法のアプローチ：XOR（排他的論理和）を活用 この問題は、ビット演算のXORを使うことで効率的に解くことができます。同じ数同士をXORすると0に打ち消し合うという性質を利用します。具体的な手順は以下の通りです。 xor_res を 0 に初期化します。 配列のすべての要素に対してXO

醜い数（Ugly Number）とは？「醜い数」とは、素因数が2、3、5のみで構成される正の整数のことです。例えば、最初のいくつかの醜い数を並べると「1, 2, 3, 4, 5, 6, 8, 9, 10, 12…」となります。このとき、10番目の醜い数は12です。本記事では、n番目の醜い数を動的計画法（DP）を使って効率的に求めるC++の実装方法を解説します。アルゴリズムの考え方醜い数は必ず「それより小さい醜い数」に2、3、または5を掛けた値になります。この性質を利用し、3つのポインタで候補値を管理しながら小さい順に配列へ格納していくのがポイントです。手順は以下の通りです。サイズ n+1 の配

h指数（h-index）とは ある研究者の論文引用回数の配列（引用数は非負の整数）が与えられます。ここで、研究者のh指数を計算する関数を定義しましょう。 h指数は次のように定義されます。 「科学者のh指数とは、N本の論文のうちh本がそれぞれ少なくともh回引用されており、残りの N − h 本の論文がそれぞれh回以下しか引用されていないときのhの値である。」 たとえば、入力が citations = [3, 0, 6, 1, 7] の場合、出力は 3 になります。これは研究者が5本の論文を発表しており、それぞれ3回、0回、6回、1回、7回引用されていることを意味します。3回以上引用された論文が

ある研究者の論文被引用数の配列（非負の整数）が与えられ、その配列は降順ではない順序（非減少順）でソートされているものとします。このとき、研究者のh指数（h-index）を計算する関数を定義するのが本問題の目的です。 h指数とは？ h指数の定義は次のとおりです。 「科学者に指標hが存在するのは、N本の論文のうちh本がそれぞれ少なくともh回引用されており、残りの N − h 本の論文がそれぞれh回以下しか引用されていない場合である。」 具体例 入力が citations = [0,1,4,5,6] の場合、出力は 3 となります。 この研究者は5本の論文を持ち、それぞれ0回、1回、4回、5回、6回

加算数（Additive Number）とは？「0」から「9」までの数字のみで構成された文字列が与えられたとき、その文字列が加算数（Additive Number）であるかどうかを判定する関数を作成することを考えます。加算数とは、文字列の桁をいくつかの数に分割したときに加算列（Additive Sequence）を形成できる文字列のことです。有効な加算列には少なくとも3つの数が含まれ、最初の2つの数を除き、列の中の後続の各数は必ず直前の2つの数の和と一致しなければなりません。たとえば、入力が「112358」の場合、以下のように分解できるため、答えは true になります。2 = 1 + 13

問題概要文字列の配列 words が与えられたとき、互いに共通の文字を1つも持たない2つの単語 word[i] と word[j] を選び、length(word[i]) × length(word[j]) の最大値を求めます。各単語には小文字の英字のみが含まれるものとします。条件を満たすペアが存在しない場合は 0 を返します。例えば、入力が ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] の場合、出力は 16 になります。「a

問題概要出発空港と到着空港のペア [from, to] で表される航空券のリストが与えられたとき、すべての航空券を使い切る形で旅程を正しい順序に再構築します。すべての航空券は JFK 空港から旅を始める一人の旅行者のものであるため、旅程は必ず「JFK」から始まる必要があります。たとえば、入力が [[MUC, LHR], [JFK, MUC], [SFO, SJC], [LHR, SFO]] の場合、出力は [JFK, MUC, LHR, SFO, SJC] となります。解法のアプローチこの問題は、グラフ理論における「オイラー路」を求める問題として捉えることができます。各空港を頂点、航空券を辺と