汎用ルール集

【問題を解く前に確認】

60分自律解答で蓄積した教訓から抽出した、問題を解く前に確認すべきルール集。

1. 制約活用チェック（超重要）

JOI本選の問題文に不要な制約は書かれていない。全ての制約には意味がある。 
□ 各制約について「解法でどう使うか」を説明できる
□ 使い道が不明な制約があれば、それが解法のヒント
□ 実装に入る前に全ての制約を活用方法を確認

制約→解法の変換テーブル

制約の例解法への活用
A < BDAGである、トポロジカル順序が自明
座標が整数座標圧縮、イベントソート
木である（N-1辺）DFS/BFS一回で全探索、LCA
辺の重みが1BFSで最短距離
A_i ≤ 20-25bit DP (2^A の状態で管理)
N ≤ 40半分全列挙（Meet in the Middle）
Q ≤ 10^5各クエリO(log N)以下が必要

2. 問題目標の多角的言い換え（必須）

1つの解釈に固執しない。問題の目標を複数の言い方で書き出す。

例：「駅1から駅Nまで移動できる条件」
  - 解釈A：駅1から駅Nへの経路が存在する → 経路探索
  - 解釈B：各駅に入る辺が1本以上ある → 条件チェック
  - 解釈C：...

どれが正しいかを制約から判定する。

3. 逆の視点チェック

問題を解くとき、以下の視点の両方を考える：

  • 動くもの（荷物、人、データ）の視点
  • 動かないもの（郵便局、駅、サーバー）の視点

「動かないものの視点」で考えると、シンプルな貪欲法が見つかることがある。

4. 同値条件の検証ルール（超重要）

「○○ ⟺ △△」という同値条件を使うときは、必ず反例を探す：

□ 自分が使う同値条件を明示的に書き出す
□ 「A ⟹ B」は成り立つか？（反例を探す）
□ 「B ⟹ A」は成り立つか？（反例を探す）
□ 以下のテストケースを自作して検証：
  - 複数の連結成分があるケース
  - 境界条件（最小ケース）
  - 「ギリギリOK」と「ギリギリNG」のペア

特に危険なパターン

  • 「連結」の定義（全体が1つ vs 各要素が孤立していない）
  • 「マッチング存在」の条件
  • 「区間が重なる」の定義（片方向 vs 双方向）

5. サンプル入力情報チェック

□ サンプル入力の全データをリストアップ（N, M, Ai, Bi, ...）
□ サンプル出力を自分で導出する
□ 導出時に「使った入力」「使わなかった入力」を記録
□ 使わなかった入力があれば「なぜ不要か」を制約から説明できるか確認
□ 説明できない場合、自分の理解が間違っている

6. グリッド問題のチェックポイント

□ 行・列単位の圧縮
  - 「行iを整備」→ 行全体に影響する場合
  - → 行・列を状態として持つDPやダブリングを検討

□ 「遠くに行く」貪欲法
  - 最短回数で目的地に到達したい場合
  - 「1回の操作で最も遠くに行く」貪欲が最適なことが多い

□ ダブリング適用条件
  - Next[i]が一意に決まる
  - クエリが多い（前計算が有効）

7. 小課題2の典型パターン（O(NM)許容）

「複数の選択肢から1つ選ぶ」問題：

  • 「最も○○なものを選ぶ」貪欲法が最適なことが多い
  • 例：目的地までの距離が最大、締め切りが最も早い、コストが最小

8. Output Only問題の心構え

□ 提出するのはコードではなく出力ファイル
□ 実行時間は数分〜数時間かけてOK
□ 入力データごとにパラメータ調整する
□ 小さい入力は厳密解（bit DP等）
□ 大きい入力は近似解（焼きなまし、2-opt等）