ABC430 A - Candy Cookie Law

ABC430 B - Count Subgrid

ABC430 C - Truck Driver

二分探索で区間を求めるタイプの問題。たまに見る気がする

• ABC389 F - Rated Range
• EXAWIZARDS2019 C - Snuke the Wizard
• ABC440 D (log^2 解法)

ABC430 D - Neighbor Distance

• 知見
  • BTreeMap では、Index は実装されているけど、IndexMut は実装されていない。
    • つまり map[x] = y みたいな代入は出来ない。代わりに insert や entry を使う
  • 総和の差分更新の実装テク
• メモ
  • BTreeSet の使い方わからない。代入とか簡単にできないの？
  • セグ木解法がある
    • 類題: ABC370 D - Cross Explosion

ABC430 E - Shift String

• 解法
  • ロリハ・SA・Z-algorithm などの文字列アルゴリズムを使う
• 知見

  • 検索したいパターンが1種類しかない場合は、SA を使うより Z-Algorithm のほうが楽

  • ロリハを累積ロリハではなく、セグ木を使うと57ms→315ms でちょっと遅くなる

    

  • 末尾追加はループを考え、ループするのは A + Aを考える典型テクがある

  • 実はロリハは群をなす(逆元計算できる)

• メモ
  • Z-algorithm

ABC430 F - Back and Forth Filling

• todo
  • 解説解法とコンテスト中にやった解法が全然違うので後で見直す
• メモ
  • 「入次数」「出次数」はすぐに変換できると便利（コンテスト中はなかなか変換できず）
  • トポソートの実装方法は復習しておくといいかも
  • DAG になる証明はしておくといいかも
    • →無向グラフを考えるとパスになるので閉路は当然できない

ABC430 G - Range Set Modifying Query

なぜ素朴な遅延セグ木で解けないのかを言語化しておくといいかも