12日目 - hukurou code

AtCoderの過去問に予想以上に時間をとられてサーバーサイドまで手が回らず。

競技プロ的なアルゴリズムのスライドのまとめ - yukicoder Wiki

このページから得た知見をメモしておく

整数Nを素数か判断するときは√Nだけ探索すればよい
- 約数は2つで１セットで、片方は必ず√N以下であるから
a/bを切り上げた整数を計算したいときは、{a+(b-1)}/b を整数で計算すればよい
二分探索をざっくり説明：解が存在する区間を２つに分けて、どちらに解が存在するかを判定。これを繰り返して解の区間を狭めていき、解を近似する手法。指数的に精度が上がっていくので高速！
文字列探索
- BM法：パターン比較時に後ろの文字から比較していって、失敗した文字種類によってずらす量を決める
  - 例えば探したい文字列がababcだった場合、文中のcで不一致だった場合5つずらすことになる
  - 探したい文字列の文字種類が多い場合O(N/L)となり爆速になる

とりあえずA-Cを完投できるだけの基礎能力をGW終わりまでに構築したいところ
明日はサーバーサイド優先でいこう。