問題
- この問題ではナイーブに解くとO(N * M)
- いもす法を使うとO(N + M)
いもす法の覚えかた
- いもす法で検索して本人の解説を読む
- 喫茶店の例までで十分
- 今回の問題の解答を読む
- サンプル1のテストデータで図を書き、いもす法のシミュレートまで行う
印象
- 後の計算に使うための統計情報を効率よく求める方法
その他の学び
- int[], vector
などは0で初期化されていない - したいならこう書く
const int N_MAX = 100000; int table[N_MAX+10] = {};
