ABC205やったらD問題でハマり。
atcoder.jp

制約が 1 ≤ AN ≤ $10^{18}$
「こんなデカい数字なら二分探索だろ？きっと」
と二分探索で実装してみるもACならず。

「二分探索で解くでも充分高速だからイケる」
とコンテスト終了後、解説を読んだところ書いてあった。
「え、それなら直してみるか」
と、ちょっと直したらACになったので、何が間違ってたのか記録しておきます。
んー、くやしかー。

二分探索で解くでもイケるがnumpy + Python3で実装したコードが遅すぎ

最初の実装がnumpy + Python3.8.2で二分探索するコードで、ロジックはおしいけど無茶遅い。
numpyを配列Aの中に、何個arg以下の数値があるかのカウントに利用。

f:id:uchidamax:20210614174416p:plain — AC x 3

AC x 3、ほかTLEという驚きの低成績。

そのコード。

PyPy3 + bisect で二分探索

こりゃPython3じゃダメそうだから、PyPy3だろ。
と、方針を転換。
bisect.bisect_right で、配列Aの中に何個arg以下の数値があるかをカウントする。

f:id:uchidamax:20210614175216p:plain — WA x 2

この実装でTLEが無くなる。
WA x 2に。
killer_00.txt、killer_01.txtがWA。

f:id:uchidamax:20210614175848p:plain — killer_00.txt

そのコード。

二分探索の探索範囲が狭かった

WA x 2がなんで出てるのかは、二分探索の探索範囲が狭かったことが原因だった。
0 〜 $10^{18}$ + 7(=1000000000000000007)
の範囲で二分探索していたが、これが狭い。
0 〜 $2^{63}$ -1(=9223372036854775807)
にしたところAC。
制約が 1 ≤ AN ≤ $10^{18}$
だから
0 〜 $10^{18}$ + 7(=1000000000000000007)
で、大丈夫だと思ってたんだけど、なんで？まぁ、いいか。
とりあえず、killer_00.txt、killer_01.txtの答えは $10^{18}$ + 7以上の数ってことかな？