JOI問題解答プロトコル (最優先)

このプロトコルは全ての問題解答に優先する

言語はC++で回答すること！

STEP 0: 問題文の罠チェック (最優先!)

問題文を読んだら必ず実行:

サンプルの説明を先に読む
- 分数(1÷4、3÷5など)が出てきたら実数扱い
- 離散的なシミュレーションではなく数式で解く必要あり
データ型を確認
- 時刻は離散(整数)? 実数?
- 座標は整数? 実数?
- 「すべての」「任意の」の範囲は?
愚直解の前提チェック
- 「制約が小さい=全探索OK」は本当か?
- 実数の場合は数式化が必要
- 時間範囲が広い(T≤10⁹)場合も数式化必須
サンプル入力情報チェック
- サンプル入力の全データをリストアップ
- サンプル出力を自分で導出する
- 導出時に「使った入力」「使わなかった入力」を記録
- 使わなかった入力があれば「なぜ不要か」を制約から説明
- 説明できない場合、自分の理解が間違っている

STEP 0.5: 問題目標の多角的言い換え (必須)

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

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

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

なぜ必要か： 1つの解釈だけだと、その解釈に引きずられて間違う。複数出すことで別の可能性に気づける。

STEP 0.6: 逆の視点チェック (必須)

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

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

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

STEP 1: 制約分析 (必須)

N, Q, T などの制約を明示
計算量の上限を計算
「N≤2000なので O(N²) が許容される」のように宣言

【制約活用チェック】(超重要)

JOI本選の問題文に不要な制約は書かれていない。全ての制約には意味がある。

各制約について「この制約は解法でどう使う？」を答えられるまで実装に入らない。

制約の例	表面的理解	深い含意（解法への活用）
A < B	DAGである	始点の情報が不要かも？トポロジカル順序が自明
座標が整数	離散値	座標圧縮が使える、イベントソートが有効
木である	N-1辺	DFS/BFS一回で全探索可能、LCA等が使える
辺の重みが1	単純	BFSで最短距離、DPの遷移が単純化

□ 各制約について「解法でどう使うか」を説明できる
□ 使い道が不明な制約があれば、それが解法のヒント

STEP 2: 小課題分析 (必須)

全小課題の配点と制約を一覧化
取れる小課題を特定
目標点数を宣言

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

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

「最も○○なものを選ぶ」貪欲法が最適なことが多い
例：目的地までの距離が最大、締め切りが最も早い、コストが最小
N, M ≤ 3000 程度なら O(NM) のシミュレーションが通る

STEP 3: マニュアル参照 (必須)

「JOI頻出パターン集」から該当パターンを引用
制約に応じた解法を選択

STEP 4: 実装順序 (必須)

小課題1から順番に実装
各小課題が通ってから次へ
満点解法は最後

STEP 5: 提出戦略 (重要)

JOI予選・本選の提出ルール:

複数回提出可能
最高得点が採用される
小課題ごとに「全テストケース通過」で得点

重要: 点数が下がることは絶対にない!

段階的提出戦略 (推奨)

1. Phase 1実装 → 提出 → 小課題1確保
2. Phase 2実装 → 提出 → 小課題1-3狙い
3. Phase 3実装 → 提出 → 満点挑戦

判断基準

残り時間	行動
60分以上	次のPhaseに挑戦
30分以下	現在の得点確保を優先
他問題で詰まり	まず得点を積み上げる

制約から解法を逆算する (最重要)

制約	許容計算量	典型解法
N ≦ 8~10	O(N!) / O(3^N)	順列全探索 / 部分集合DP
N ≦ 15~18	O(2^N × N)	bit DP / bit全探索
N ≦ 100~200	O(N³)	区間DP / Floyd-Warshall
N ≦ 2,000~3,000	O(N²)	愚直DP / 2重ループ
N ≦ 2×10^5	O(N log N)	ソート / セグ木 / 二分探索
N ≦ 5×10^6	O(N)	累積和 / 尺取り / 線形DP
A_i ≤ 20-25	O(2^A)	bit DP

提出前チェックリスト

□ long long を使うべきところで int になっていないか
□ 配列外アクセスはないか (0-indexed / 1-indexed)
□ 初期化忘れはないか
□ オーバーフローはないか (掛け算、足し算)
□ 特殊ケース (N=1, 空配列, 自己ループ) は大丈夫か
□ 出力形式は正しいか (改行、空白)
□ 計算量は間に合うか (2×10^8 ≒ 1秒)

最優先ルール:

制約を見て計算量を逆算
小課題1から着実に部分点を取る
愚直解を書いてから高速化を考える