ABC422 A - Stage Clear

ABC422 B - Looped Rope

ABC422 C - AtCoder AAC Contest

• 知見
  • 答えを変数にするとうまくいく
    • 数学では典型だが、競プロだと数学ほど頻出ではない印象
• 考察
• メモ
  • 実は二分探索不要で、式変形で O(1) にできる
    • 式変形するとx≤cのパターンになる
  • 解説では自明な上界が達成可能であることを示している

ABC422 D - Least Unbalanced

• 知見

  • ビット逆順 (bit reversal) にして考えると、いい感じに散らばってくれる

    

    • 参考: ARC182 B - |{floor(A_i/2^k)}|
• メモ

  • 「長さ 2^N の…」って書いてあったらセグ木が思い浮かびがち

    

ABC422 E - Colinear

• 知見
  • 2点 $(x_0, y_0), (x_1, y_1)$ を通る直線の方程式: $(x-x_0)(y-y_1) = (x-x_1) (y-y_0)$
    • 導出
    • 別の形式
  • TL の 2000ms ギリギリまで計算するテクがある（AHC ではよくある）
  • 存在性判定で、答えが Yes の場合ときに全探索をしたら 1/2 や 1/4 などの（入力に依存しない定数の）確率で満たす場合には乱択が有効
    • 形式的には、ある $c >0$ が存在して、 各入力集合 $A$ に対して「$A$ が空集合でないならば $P(A) \geq c$ 」がいえるケースで乱択が有効
• メモ

  • 1点で乱択するか2点で乱択するかの2択がある

    • 1点の場合は、ヒット確率は 1/2 だが、gcd の計算があったり、HashMap が必要だったりで計算が遅い問題がある
      • 選んだ1点を起点としたとき、その点から他の点への方向を全列挙する。その方向が逆向きの違いを同一視して同じかどうかを判定する（商集合テク）
    • 2点の場合だと、ヒット確率が1/4 の代わりに1回あたりの計算時間が短い
      • 2点あれば直線が定まり、他の点がその直線に乗るかどうかを判定すればよい

  • 最初 gcd で割る正規化を忘れてた

  • HashMap がおそすぎる

    • 5×10^6 の計算量ですら 1000ms
      • 乱択回数10回
    • 最初は5×10^7 で投げて TLE してた
      • 乱択回数100回
    • gcdが遅い説も少しある？

  • ベンチマーク

    上から HashMap, sorted().dedup_with_count(), counts() (内部で HashMap)

    

    HashMap 周りの計算量の感覚を身につける必要がある

  • 競プロにおける乱数の活用例

    https://x.com/paruma184/status/1825928367734219034?s=46

    乱数の活用(ゾブハ)

ABC422 F - Eat and Ride