模擬テスト — paiza B〜S・AtCoder ABC相当の実戦10問 - コーディングテスト突破ドリル

いよいよ卒業試験です。この章には模擬問題を10問用意しました。前半5問がpaiza B〜Sランク相当、後半5問がAtCoder ABC C〜D相当です。

取り組み方

環境構築がまだの人は付録Aを先に済ませてください。

学習者

10問か…。よし、時間計ってやってみる！

N行のログが与えられる。各行は「学籍番号出席/欠席」の形式。3回以上欠席した学生の学籍番号を、初めて3回目の欠席をした順に出力せよ。（N ≤ 10^5）

ヒント: 第4章方針: Mapで学籍番号→欠席回数をカウント。3に達した瞬間に結果へpush。「達した順」という条件が、後からのソートではなくその場で記録を要求している——仕様の読み落としを誘う、paizaらしい設計。

店にN人の客が来る。i番目の客の入店時刻と退店時刻が与えられる。同時に店内にいた人数の最大値を求めよ。（N ≤ 10^5、時刻 ≤ 10^9）

ヒント: 第12章のケーススタディ方針: 入店+1/退店-1のイベントソート。第12章で実演した問題の骨格そのまま。初見でも「区間の重なり最大」に要約できたかがポイント。

N個の商品の価格が与えられる。2個セットにして売るとき、セットの合計価格がすべてK円以下になるように最大何セット作れるか。（N ≤ 10^5）

ヒント: 第3章・第9章方針: ソートして両端から二つのポインタ。「最小と最大を組ませ、無理なら最大を諦める」貪欲。正当性は交換論法で確認（最大の商品と組めるのは最小の商品が一番有利）。

N件の会議予約（開始・終了時刻）から、時間が重ならないように最大何件受け入れられるか。（N ≤ 10^5）

ヒント: 第9章方針: 区間スケジューリングそのもの。終了時刻ソート→1周。「開始時刻順に選ぶ」と書いてWAになるのが定番の罠。

N個の商品（価格P_i、満足度V_i）から、合計W円以内で満足度の合計を最大化せよ。（N ≤ 100、W ≤ 10^5）

ヒント: 第10章方針: ナップサックDP。O(NW) = 10^7。paiza Sランクの代表的な出題形式で、「DPを知っているか」がランクの分水嶺になる。

N枚のカードに数が書かれている。何枚か選んで合計をちょうどXにできるか判定せよ。（N ≤ 20）

ヒント: 第7章方針: N ≤ 20が合図のbit全探索。2^20 × 20 ≈ 2×10^7で間に合う。Nが100ならDP（部分和）に切り替える——制約で解法が変わる好例。

N個の部屋とN-1本の廊下からなる建物（木構造）。部屋1から各部屋への最短の廊下数を求めよ。（N ≤ 10^5）

ヒント: 第6章方針: 重みなし最短距離=BFS一択。隣接リスト化→添字方式キュー→dist配列。テンプレートを写経レベルで再現できるかの確認問題。

N本の丸太からK本の同じ長さの棒を切り出す。切り出せる棒の最大の長さを求めよ（小数点以下切り捨て）。（N, K ≤ 10^5、長さ ≤ 10^9）

ヒント: 第8章方針: 第8章で解説した「答えで二分探索」。判定問題「長さLでK本作れるか」+ 単調性。10^9という制約が「答えの空間を二分探索せよ」のサイン。

N個の島に順番にQ本の橋がかかっていく。各橋がかかった**直後の「島のグループ数」**を毎回出力せよ。（N, Q ≤ 10^5）

ヒント: 第11章方針: Union-Find。グループ数はN から開始し、unionで実際に合併が起きたときだけ-1する（同じグループ同士の橋では減らない——ここが罠）。

1日目に1個、以降毎日「前日と同じ個数」か「前日+1個」のどちらかを配る。N日目までの配り方の総数を10^9+7で割った余りを求めよ。（N ≤ 10^3、個数の上限 M ≤ 10^3）

ヒント: 第10章方針: 数え上げDP。dp[日][その日の個数] = パターン数、遷移は「同じ」と「+1」の2本。「総数を10^9+7で割った余り」はAtCoder数え上げ問題の合図で、加算のたびに % MOD する。

模擬テストの価値は答え合わせの後にあります。各問について、次の3行メモを残してください。

問8: ✗
シグナル: 「最大の長さ」+ 答えの範囲が10^9 → 答えで二分探索
見落とし: 判定問題に変換する発想が出なかった → 第8章を再読

このメモが溜まると、第12章の20選があなた専用の弱点リストに進化します。

メンター

本番のpaizaやAtCoderは、ここまでやったあなたにとって「初見の問題」ではなく「見たことのある型の変装」です。あとは場数。paizaならスキルチェックを週1問、AtCoderなら毎週のABCに参加する習慣をつけましょう。

これで本編は修了です。付録には環境構築、スニペット集、緑→水色へのロードマップを用意しました。実戦のお供にどうぞ。