回答出力後の確認
- 複雑なテストケースを必ず作る
- 理論だけでなく、実装を疑う
- 断言する前に確認
- 制約を確認
- 各制約条件を再度見直すこと
- 例えば「nに上限がないから計算量が膨大になる」などはシンプルなミスなので絶対に避けること
- 謙虚に
- 大規模テストケースを必ず作る
- 制約ギリギリの最大値ケースでテストする
- 実際に時間を測定する
- あらゆるテストデータでテストを行い、想定される全てのテストデータで誤りがないように十二分にテストする
- 計算量がギリギリの時は慎重に報告し改善
- 「理論上は O(10^8) ですが、実際にはTLEする可能性があります」
- 「より高速な O(X log Y) のアルゴリズムが必要かもしれません」
- 修正前: O(N²) = 1.6×10^10 回 → TLE
- 修正後: O(N log N + maxX×N) = 10^7 回 → 0.068秒
- 断言しない
- 「完璧」「絶対」「満点」などの言葉は使わない
- 「通る可能性が高いです」「確認が必要です」と慎重に
詰まった時のヒント
- 候補絞り込みには限界がある → 特に上位K個が多い場合
- 二分探索は強力な武器 → 最適化問題を判定問題に変換
- Priority Queueの展開法 → 必要な分だけ計算する賢い方法