ABC417 A - A Substring

• コンパイル時に大きさが定まらない型の値はローカル変数として持てない。

ABC417 B - Search and Delete

• HashBag
  • iterator の collect で変換をする
  • set_iter は (値, 個数) の iterator を返す
    • dedup_with_count は (個数, 値) の iterator なので、順番が逆の点に注意
  • self.extend(iter) で拡張ができる。（HashBag に限らず）
• 一般的な Rust のコレクション
  • From は基本実装されていない（from や into での変換はできない）
  • FromIterator は実装されている（collect で iterator からの変換ができる）
• BTreeMultiset に iter と set_iter を実装した（HashBag と同様に）

ABC417 C - Distance Indicators

• 類題: ABC166 E - This Message Will Self-Destruct in 5s

  • 制約だけが違う: $A_i \leq 10^9$ か $A_i \leq 2\times 10^5$ か

• 今回の平面走査は Fenwick Tree が不要。ただの Vec（または HashBag） で良い。

  • $i<j, f(i) < g(j)$ をみたす $(i,j)$ の個数を求める場合は Fenwick Tree を使う
  • $i<j, f(i) = g(j)$ をみたす $(i,j)$ の個数を求める場合はただの Vec でよい。

  どちらも $f(i)$ の頻度分布を管理することになる。

  参考: 二重和(2つの値)

• 初期値 0 を代入する場合は 0_i64 のように型を明示的に書くのがよい。書かないと意図せずに i32 になってオーバーフローする可能性がある

  let mut cnts = vec![0_i64; max + 1];
  let mut cnts = FenwickTree::new(max + 1, 0_i64);
  

  また、出力する答えにも型を付与しておくと良い。

ABC417 D - Takahashi's Expectation

• 解の構造を考える
  • 類題
    • ABC415 G - Get Many Cola
    • ABC358 G - AtCoder Tour
    • ABC368 C - Triple Attack？
• 与えられる X が大きい問題について以下のように思考した
  • sum B + 500 以上であればすべてテンションが下がるのが答え（自明に求まる）
  • sum B + 500 以下の部分を高速に計算する思考を長くしてしまった。
  • 解の構造を考える部分（もっと X を小さくできる）までたどり着くのに時間かかった
    • tbw
    • （解の構造は毎回考えてもいいかもしれない）
• 提出防止タブとして dbg!("ここ変える") はよい。テスト用にマジックナンバーを小さくしているときにうっかり提出しないようにする効果がある。
• 二分探索に渡す述語の値がすべて false のパターン。最初に指定した ok の値が帰ってくる
• 前処理計算パートは、合成に関する suffix product を計算してると思うと良い
• export BACKTRACE=1 をやると配列外参照したときのバックトレースが見れる
  • ただし、クロージャーをライブラリに渡しているとかなりわかりにくい。