ABC 149 E - Handshake

解説を読みながら実装してもなかなか苦戦したのでメモ。

解説はもちろん公式解説PDFと、このツイート、

フェネック「E問題は、「どのペアまで使えるか」で二分探索だねー。Kを固定したとき、「各iについてA[i]+A[j]≧Kとなるjの個数」は累積和を使って全体でO(N)で求められるから、f(K)≦M＜f(K+1)を満たすKをO(NlogA)で求められて、」

— 競技プログラミングをするフレンズ (@kyopro_friends) December 29, 2019

そしてこのブログを参考にした。

emtubasa.hateblo.jp

3つ合わせることで、実装できるところまで理解できた。

どこで詰まったか

二分探索の範囲を間違えていた。 A_iの上限は10⁵だが、A_i + A_jの上限は2 * 10⁵なので、2*10⁵の範囲で二分探索する必要がある。 10⁵の範囲で二分探索していたのでWAが多発していた。

その他

WAを直すには、自分と同じケースでWAしている提出を見つけて、その人がどこを修正してACできたのかを見てみると、どこが間違っているか気づきやすいことがわかった。 ただ、そういう提出を探すには手動で一個一個見ていくしかないのが辛いところ。 そういうツールでもあれば良いんだけど… 欲しいなら自分で作れって話ですね

あとがき

年内にACできてよかった。 しかし、E問題はまだ難しい…