パターン認識トレーニング — 「問題文→解法」の変換を鍛える - コーディングテスト突破ドリル

Part 4は実戦演習編です。ここまでに道具は揃いました。残る課題はただ1つ——初見の問題文から、どの道具を使うかを見抜くことです。

上級者と初心者の差は、知識量よりも変換の速さにあります。上級者は問題文を読みながら「制約10^5、"連続する部分列"、"最長"…尺取り法だな」と、キーワードが解法に直結しています。この章はその回路を作るための訓練です。

シグナル→解法早見表20選

各章末で提示してきた「見分け方」の総集編です。問題文に現れる言葉から引けるように並べ直しました。

#	問題文のシグナル	第一候補	章
1	N ≤ 20 +「選ぶ/選ばない」	bit全探索	7
2	N ≤ 10 +「並べ方・順序」	順列全列挙	7
3	制約が小さい（10^6回で全部試せる）	素直に全探索	7
4	「ペアが存在するか」「重複」「過去に出たか」	Set存在判定	4
5	「回数」「最頻」「グループ分け」	Mapカウント/キー設計	4
6	「アナグラム」「並べ替えると同じ」	ソート文字列をキーに	4
7	ソート済み +「合計がXのペア」	二つのポインタ	3
8	「連続する部分配列の最長/最短/個数」	尺取り法	3
9	「区間の合計」を何度も	累積和	3
10	「括弧の対応」「直近と消し合う」	スタック	5
11	「迷路」「最小手数」（重みなし）	BFS	6
12	「グループはいくつ」「到達できるか」	DFS/BFS連結成分	6
13	「x以上の個数」（ソート可能）	lowerBound	8
14	「〇〇できる最大のL」「最大値の最小化」	答えで二分探索	8
15	「重ならないよう最大数選ぶ」	区間スケジューリング貪欲	9
16	「何通りあるか」	数え上げDP	10
17	「容量W以下で価値最大」	ナップサックDP	10
18	「最長増加/共通部分列」	系列DP	10
19	「最短」+ 辺の重みがバラバラ	ダイクストラ	11
20	「つなぐ」「合併」+「同じグループ？」	Union-Find	11

学習者

20個かぁ。これ、暗記するもの？それとも使ってるうちに覚えるもの？

暗記しようとしなくて大丈夫です。使い方は「問題を解く→詰まったらこの表を上から眺める→当てはまりそうな行の章を復習」。この表を「引く」行為そのものが訓練で、10問も解けば頻出行は勝手に頭に入ります。

初見の問題を分解する5ステップ

表に直接ヒットしない問題のために、汎用の思考手順も持っておきましょう。

Step 1  制約を見る
        → 許される計算量が決まる（第2章の表）。これで解法の半分は絞れる

Step 2  問題文を「入力→出力」に要約する
        → 物語を剥がす。「N個の整数から条件を満たす〇〇の最大値」のように1行化

Step 3  全探索ならどう書くか考える
        → 「何を全部試せば答えが出るか」。これが解法の原型（第7章）

Step 4  間に合わないなら、どの道具で削るか
        → 探索が重い→ハッシュ/二分探索、選択の重複→DP、1本道でよさそう→貪欲

Step 5  小さい例で手を動かして検算する
        → 要素3個の入力で自分の解法をシミュレート。反例が出たらStep 4へ戻る

ケーススタディ: 5ステップを実演する

実際の出題風の問題文で、頭の中を実況します。

問題: あるお店にN人の客が来る。i番目の客の来店時刻はT_i、滞在時間はS_iである。座席は1つしかない。座席が空いていれば客は座り、空いていなければ帰ってしまう。座れる客の数を最大化…ではなく、客が全員座れるように座席をK個用意したい。必要な最小のKを求めよ。（N ≤ 10^5、時刻 ≤ 10^9）

Step 1 制約: N ≤ 10^5 → O(N log N)まで。時刻が10^9 → 時刻を配列添字にはできない（座標圧縮か、しない工夫を)。

Step 2 要約: 「N個の区間 [T_i, T_i + S_i) が与えられる。同時に重なる区間の最大数を求めよ」——物語を剥がすとこうなります。

Step 3 全探索: すべての時刻について重なり数を数える → 時刻が10^9通りで不可能。

Step 4 削る: 重なり数が変化するのは「誰かの来店/退店の瞬間」だけ。イベント（+1/-1）を時刻順にソートして走査すれば O(N log N)。——「区間の重なり」をイベントのソートに変換する、いもす法/イベントソートと呼ばれる考え方です（累積和の親戚です）。

Step 5 検算: 客2人が同時刻に来店したら？来店イベントを退店イベントより先に処理する順序づけが必要——と、端のケースに気づけます。

function minSeats(customers: [number, number][]): number {
  const events: [number, number][] = [];   // [時刻, +1/-1]
  for (const [t, s] of customers) {
    events.push([t, +1], [t + s, -1]);
  }
  // 時刻順。同時刻は退店(-1)を先に処理（退店と同時の来店は座れる、という仕様なら）
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
 
  let current = 0, best = 0;
  for (const [, delta] of events) {
    current += delta;
    best = Math.max(best, current);
  }
  return best;
}