perogram

【C++】いもす法を覚えた!abc017_3

問題

beta.atcoder.jp

  • この問題ではナイーブに解くとO(N * M)
  • いもす法を使うとO(N + M)

いもす法の覚えかた

  • いもす法で検索して本人の解説を読む
    • 喫茶店の例までで十分
  • 今回の問題の解答を読む
  • サンプル1のテストデータで図を書き、いもす法のシミュレートまで行う

f:id:peroon:20181209185910j:plain

印象

  • 後の計算に使うための統計情報を効率よく求める方法

その他の学び

  • int[], vectorなどは0で初期化されていない
  • したいならこう書く
const int N_MAX = 100000;
int table[N_MAX+10] = {};

私の提出

beta.atcoder.jp