エクサウィザーズ 2019 C - Snuke the Wizard

exawizards2019.contest.atcoder.jp

問題概要

分かりやすいけど、難しいので説明しません！（読めば分かると思います…）

気づいたこと

• 「俺の方が崖に近いのに落ちてない」みたいなことは絶対にない。

例えば左から100番目のやつが左に落ちた時、必ず左から1~99番目のやつも落ちている。
なぜなら、99番目のやつは100番目より右に行くことは不可能だからです（最高でも重なるのが限界）

→ゴーレムが、2つの境を挟んで、
左に落ちる 左に落ちる 左に落ちる || 落ちない 落ちない 落ちない 落ちない || 右に落ちる 右に落ちる 右に落ちる
となっていることに気づいた

この時点で、この問題は「左に落ちるボーダーライン || と、右に落ちるボーダーライン || を求める問題」に変換できる。

• とある地点のゴーレムが落ちるかどうかは、シミュレーションすればN(Q)で求められる

int ochi(int now) 関数を作って、左に落ちる→-1、落ちない→0、右に落ちる→1と返すようにした

ボーダーラインの求め方…にぶたん！！
二分探索を使えば、ボーダーラインがlogNで求められる。今日二分探索を使う問題を解いたばっかだったので、その発想はすぐに浮かんできた。
めぐる式二分探索を使った。leftとrightを使って、(ochi(i) == -1)と(ochi(i) == 1)のボーダーラインをそれぞれ求めた。

あとは「ボーダー右 - ボーダー左」を出力すればいいです。