C

後で考える

式変形するとx≤cのパターンになる

実は二分探索が不要

D

セグ木

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

ビット逆順 (bit reversal) にして考えるといいらしい

参考: ARC182 B

E

• 知見
  • 2点 $(x_0, y_0), (x_1, y_1)$ を通る直線の方程式: $(x-x_0)(y-y_1) = (x-x_1) (y-y_0)$
    • 導出
    • 別の形式
• メモ

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

  • Pos に対して normalize という関数を定義しておくと見通しが良い。

  • HashMap がおそすぎる

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

  • ベンチマーク

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

    

2000ms ギリギリまで計算するテク（AHC ではよくある）

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

• 図形の方程式