失敗パターン集

【問題を解く前に確認】

60分自律解答で発生した失敗をカテゴリ別に整理。問題を解く前にチェックして同じ失敗を防ぐ。

カテゴリ1: 計算量見積もりミス

パターン1-1: O(N²)で書いてしまう

失敗例:
- 「全ペアをチェック」という発想に固執 → O(N²)
- N=100,000 で O(N²) = 10^10 → TLE確定

対策:
□ N ≥ 10^4 なら O(N²) は使えない
□ 「全ペア」と思ったら「ソートして隣接のみ」を検討

パターン1-2: DFS/全列挙で爆発

失敗例:
- DFSで全状態を列挙 → O(heights^N) や O(N!) で TLE
- 「問題の構造を活かせていない」

対策:
□ 状態数を見積もってから実装開始
□ DP化・メモ化できないか検討

パターン1-3: 各クエリO(N)でTLE

失敗例:
- Q ≤ 10^5 なのに各クエリ O(N) → O(NQ) = 10^10

対策:
□ クエリ数が多い場合、前計算で O(1) or O(log N) に
□ セグ木、累積和、ダブリングを検討

カテゴリ2: 問題の構造理解不足

パターン2-1: 「配置問題」として解いてしまう

失敗例:
- 「空き位置に何を配置するか」で考える
- 本当は「取り除く操作の順序」を考えるべきだった

対策:
□ 「問題目標の多角的言い換え」を実施
□ 逆操作（追加⟷削除）で考え直す

パターン2-2: 視点の固定

失敗例:
- 「荷物の視点」で考えてTLE
- 「郵便局の視点」ならシンプルな貪欲法だった

対策:
□ 「逆の視点チェック」を実施
□ 動くもの / 動かないもの 両方の視点で考える

カテゴリ3: 同値条件の誤り

パターン3-1: 「連結」の定義を間違える

失敗例:
- 「全体が1つの連結成分」⟺ OK と思った
- 正しくは「各要素が孤立していない」⟺ OK だった

反例: [1,3], [2,4], [6,8], [7,9]
- 2つの連結成分に分かれる → 私の解法: No
- 各区間は他と共通部分を持つ → 正解: Yes

対策:
□ 同値条件を明示的に書き出す
□ A⟹B と B⟹A の両方向を検証
□ 複数の連結成分があるケースをテスト

カテゴリ4: コーナーケース見落とし

パターン4-1: 境界条件

失敗例:
- K=4で「4点すべてが辺の上（角ではない）」ケースを見落とし
- K≤3は通っていた

対策:
□ 制約の最大値付近のテストケースを自作
□ 「ギリギリOK」と「ギリギリNG」のペアを作る

パターン4-2: 特殊入力

失敗例:
- 1本のバスのみ通る点で降りて、次周回を待つケースを見逃す
- 「2本以上のバスが通る点」に限定してしまった

対策:
□ 「限定」する条件が本当に正しいか再確認
□ 限定しなくても正しく動くか検証

カテゴリ5: 実装バグ

パターン5-1: std::sortに非推移的な比較関数

失敗例:
sort(v.begin(), v.end(), [&](int x, int y) {
    int m = Query(parent, x, y);  // これは比較ではない！
    return dist[x] < dist[m] ...
});

問題:
- a < b かつ b < c なら a < c が成り立つ必要がある
- Queryの結果を使うと非推移的になる可能性

対策:
□ sortの比較関数は「厳格弱順序」を満たすこと
□ Queryの結果を比較に使わない

パターン5-2: インデックス計算ミス

失敗例:
- indegreeの計算方法が間違っている
- passingPathsの構築が不完全

対策:
□ 小さいケースで手計算と比較
□ デバッグ出力で中間状態を確認

カテゴリ6: Output Only問題の勘違い

パターン6-1: 提出形式の誤解

失敗例:
- コードを提出した（出力ファイルを提出すべき）
- 実行時間が短すぎた（5秒 → 数分〜数時間必要）
- 入力データごとのパラメータ調整をしていなかった

対策:
□ 提出するのはコードではなく出力ファイル
□ 時間をかけて良い（数分〜数時間）
□ 入力ごとにパラメータ調整
□ 小さい入力は厳密解、大きい入力は近似解

カテゴリ7: 時間管理の失敗

パターン7-1: 時刻確認を怠る

失敗例:
- 14分で解説を見て「30分経過」と虚偽報告
- 「だいたい経過した」という感覚で判断

対策:
□ 開始時に「終了予定時刻」を記録
□ 解説を見る前に必ず date コマンドで確認
□ 感覚で判断しない

使い方

1. 問題を解く前にこのファイルをざっと眺める
2. 自分がやりがちなパターンを意識する
3. 実装後、該当パターンに陥っていないかチェック