プロンプト改善アーカイブ（本選）
概要
JOI本選過去問のC・D・E問題（問題3・4・5）を60分自律解答で実行し、プロンプト改善につなげた記録。
進捗一覧
2023-2024年度
| 問題 | 実行日時 | 改善案 | スキル追加 |
|---|---|---|---|
| C（マラソン大会2） | 2026-01-05 | 満点（100点） | - |
| D（プレゼント交換） | 2026-01-05 | 詳細（10点） | 未 |
| E（道路整備） | 2026-01-05 | 詳細（43点） | 済 |
2022-2023年度
| 問題 | 実行日時 | 改善案 | スキル追加 |
|---|---|---|---|
| C | 2026-01-09 | 満点（100点） | - |
| D | 2026-01-10 | 満点（100点） | - |
| E（現代的な機械） | 2026-01-10 | 詳細（15点） | - |
2021-2022年度
| 問題 | 実行日時 | 改善案 | スキル追加 |
|---|---|---|---|
| C（選挙で勝とう） | 2026-01-06 | 詳細（10点） | - |
| D | 2026-01-06 | 満点（100点） | - |
| E（砂の城2） | 2026-01-06 | 詳細（19点） | - |
2020-2021年度
| 問題 | 実行日時 | 改善案 | スキル追加 |
|---|---|---|---|
| C | 2026-01-06 | 満点（100点） | - |
| D | 2026-01-06 | 0点（コードなし） | - |
| E（ダンジョン3） | 2026-01-06 | 詳細（11点） | - |
2019-2020年度
| 問題 | 実行日時 | 改善案 | スキル追加 |
|---|---|---|---|
| C | 2026-01-06 | 満点（100点） | - |
| D | 2026-01-06 | 満点（100点） | - |
| E（火事） | 2026-01-06 | 詳細（20点、RE） | - |
改善案詳細
2024-2025 C（ミ・テレフェリコ）
プロトコルへの追加
1. 制約活用チェック: 各制約について「この制約は解法でどう使う？」を答えられるまで実装に入らない
2. 問題目標の多角的言い換え: 1つの解釈に固執しない。問題の目標を複数の言い方で書き出す
3. サンプル入力情報チェック: 使わなかった入力があれば「なぜ不要か」を制約から説明できるか確認
2. 問題目標の多角的言い換え: 1つの解釈に固執しない。問題の目標を複数の言い方で書き出す
3. サンプル入力情報チェック: 使わなかった入力があれば「なぜ不要か」を制約から説明できるか確認
2024-2025 D（長いだけのネクタイ2）
問題点
- 問題の本質を見抜けなかった - 「反応する位置の列を非減少チェーンに分割」という構造に気づくのが遅かった
- 状態の持ち方を間違えた - 各長さのモデル「数」ではなく「存在するか」のbitで管理すべきだった
- A_i ≤ 21 の活用不足 - 2^21 ≈ 200万の状態でbit DP可能という発想に至らなかった
プロトコルへの追加
制約から解法を逆算するテーブルに追加:
A_i ≤ 20-25 → bit DP (2^A の状態で管理)
2024-2025 E（郵便局）
問題点
- 30分経過を守らなかった - 14分で解説を見て「30分経過」と虚偽報告
- 解説を見た後に改善コードを書かなかった
- 解法の選択ミス - 正解は「各郵便局の視点で、最後に発送する時刻を計算する」
プロトコルへの追加
逆の視点チェック:
- 動くもの（荷物、人、データ）の視点
- 動かないもの（郵便局、駅、サーバー）の視点
「動かないものの視点」で考えると、シンプルな貪欲法が見つかることがある
- 動くもの（荷物、人、データ）の視点
- 動かないもの（郵便局、駅、サーバー）の視点
「動かないものの視点」で考えると、シンプルな貪欲法が見つかることがある
2023-2024 D（プレゼント交換）- 10点
問題点
使った同値条件が間違っていた:
- 誤: 「全区間が1つの連結成分」⟺ プレゼント交換可能
- 正: 「各区間が少なくとも1つの他区間と重なる」⟺ プレゼント交換可能
対策
同値条件の検証ルール:
□ 自分が使う同値条件を明示的に書き出す
□ 「A ⟹ B」は成り立つか？（反例を探す）
□ 「B ⟹ A」は成り立つか？（反例を探す）
□ 複数の連結成分があるケースをテスト
□ 自分が使う同値条件を明示的に書き出す
□ 「A ⟹ B」は成り立つか？（反例を探す）
□ 「B ⟹ A」は成り立つか？（反例を探す）
□ 複数の連結成分があるケースをテスト
2023-2024 E（道路整備）- 43点
問題点
- 「行単位で考える」発想の欠如 - 連結成分（交差点単位）で考えてしまった
- 貪欲法の適用可能性を見逃した - 「できるだけ下で整備する」という貪欲が最適
- ダブリングのパターン認識不足
対策
グリッド問題のチェックポイント:
1. 行・列単位の圧縮を検討
2. 「遠くに行く」貪欲法を検討
3. ダブリング適用条件: Next[i]が一意に決まる、クエリが多い
1. 行・列単位の圧縮を検討
2. 「遠くに行く」貪欲法を検討
3. ダブリング適用条件: Next[i]が一意に決まる、クエリが多い
2022-2023 E（現代的な機械）- 15点
問題点
「N+1状態 → メモリ足りない → 諦める」で止まった。
遷移関数を観察すると、全部傾き1で境界が1箇所だけ → 境界点だけ保存すれば圧縮可能だった。
対策
□ 「状態数が大きい」と思ったら、遷移関数を手で書き出す
□ 遷移関数が「区分線形」なら圧縮可能
□ 「傾きが0か1しかない」は確実に圧縮可能のサイン
□ 遷移関数が「区分線形」なら圧縮可能
□ 「傾きが0か1しかない」は確実に圧縮可能のサイン
2021-2022 C（選挙で勝とう）- 10点
問題点
- 「どの州を使ったか」の管理漏れ - Phase 1で演説した州をPhase 2で再度使っている
- 問題の構造を見抜けなかった - 「協力者を増やす→効率UP」という構造
対策
□ 「リソースAを得ると効率UP」パターンを認識
□ DPを2フェーズに分けるとき、フェーズ1で使った要素をフェーズ2で再利用していないか確認
□ DPを2フェーズに分けるとき、フェーズ1で使った要素をフェーズ2で再利用していないか確認
2021-2022 E（砂の城2）- 19点
問題点
判定条件の言い換えができず、各長方形O(HW)で判定 → TLE
正解の手順
1. 「全マス通れる」条件を言い換える: 「入ってくる矢印が0本のマス」が1個だけ
2. 境界条件でパターン分け（81パターン）
3. 各パターンで2次元累積和
2. 境界条件でパターン分け（81パターン）
3. 各パターンで2次元累積和
2020-2021 E（ダンジョン3）- 11点
問題点
- 60分で小課題1の解法しか実装できなかった
- 「クエリをまとめて処理」という発想に至らなかった
- 「答えをUの関数として管理」という発想に至らなかった
正解の手順
1. 座標で言い換える: X_i = A_1 + ... + A_{i-1}
2. 各層の「担当区間」を決める（next_cheaper[i]）
3. 答えをUの関数として表す（折れ線関数）
4. BITで折れ線を管理
5. クエリをSの降順に処理
2. 各層の「担当区間」を決める（next_cheaper[i]）
3. 答えをUの関数として表す（折れ線関数）
4. BITで折れ線を管理
5. クエリをSの降順に処理
2019-2020 E（火事）- 20点（RE）
問題点
アルゴリズムは正解と同じ。REの原因は配列境界のバグ。
- BITのインデックス計算でedge caseで範囲外アクセスの可能性
- left_posの番兵が負の値で後続の計算に影響
対策
□ 「アルゴリズムは合っているのにRE」→ 配列境界を疑う
□ 番兵を使う場合は値の範囲を明示的に計算
□ BITやセグ木のサイズは 2N + α で余裕を持たせる
□ 番兵を使う場合は値の範囲を明示的に計算
□ BITやセグ木のサイズは 2N + α で余裕を持たせる
2018-2019 D（コイン集め）- 0点
問題点
コードは公式解法とほぼ同一。0点の原因は不明（提出ミス、コンパイルエラー等の可能性）。
対策
□ 提出前に「正しいファイルを提出しているか」を確認
□ コンパイルエラーがないか確認
□ サンプルで動作確認してから提出
□ コンパイルエラーがないか確認
□ サンプルで動作確認してから提出
2018-2019 E（珍しい都市）- 0点
問題点
- スタック復元ロジックのバグ - 公式解法は子を訪問するたびにスタックを復元しない
- ブロック条件の実装ミス
- 子の処理順序の複雑化
対策
□ 木の問題で「直径からのDFS」パターンを認識
□ 単調スタック+DFSの組み合わせでは子の訪問順序が重要
□ 複雑なDFSは公式解法の構造をトレース
□ 単調スタック+DFSの組み合わせでは子の訪問順序が重要
□ 複雑なDFSは公式解法の構造をトレース
2017-2018 C（だんご職人）- 0点
問題点
座標系変換をせず、競合条件を直接計算 → 複雑になりバグが入った
正解の手順
1. 斜めライン i+j ごとに独立と気づく
2. 斜めラインを3行グリッドに変換
3. 座標変換後、競合条件は「直前と同じ種類の串は選べない」に単純化
4. DPで最大串数を計算
2. 斜めラインを3行グリッドに変換
3. 座標変換後、競合条件は「直前と同じ種類の串は選べない」に単純化
4. DPで最大串数を計算
2017-2018 D（定期券）- 30点
問題点
- 「入る点」と「出る点」が別のパターンを考慮していない
- 状態の持ち方が不十分 - 公式は「U合流したか」「V分岐するか」の4状態を同時に管理
正解の手順
1. S, T, U, V の4点からDijkstra
2. 頂点をdistSの昇順にソート
3. DP[v][k]: 4状態（U合流済み×V分岐済み）を管理
4. S→T最短経路上の辺のみ遷移
2. 頂点をdistSの昇順にソート
3. DP[v][k]: 4状態（U合流済み×V分岐済み）を管理
4. S→T最短経路上の辺のみ遷移