計算量の目安

• 10の7乗くらいはたいがい間に合う
• 10の8乗はシンプルな処理なら間に合う
• 10の9乗はめちゃくちゃシンプルなら間に合う

定数倍改善テク

• ボトルネックの部分のみ最適化をする
  • ボトルネックじゃないところはどうでもいい
  • ボトルネックの部分はかなり狭い場合もある
• 最初は普通に実装する。最初から最適化はしようとしない。
• 添字アクセスは遅いので iterator を使う
  • どうしても添字アクセスが必要な場合は get_unchecked や get_unchecked_mut を使う
• ループの外でできる処理はループの外でする
• 配列の動的確保は遅いのでできるだけ避ける
• 出力には fastout を使う
• &u32 より u32 を使う
  • iter().copied() の copied() をすると早くなることがある

問題ごと

log を減らす

• ABC323 E - Playlist
  • modint の逆元計算の回数を減らして1200ms → 60ms になった

定数倍改善

• ARC174 C - Catastrophic Roulette
  • modint の逆元計算の回数を減らして AC になったパターン。（逆元の前計算をした）
  • 改善前は富豪的プログラミングのノリでたくさん逆元の計算をしていた。
  • 計算量: 10^6 × log(998244353) ≒ 4.5 × 10^7
    • これでも雑に雑に計算すると落ちるのか

10^9 程度の計算量でも間に合うパターン

• ABC348 F - Oddly Similar
  • 8×10^9 (実はnC2 の部分があって、4×10^9 になっている）