Codeforces Round 870 (Div. 2)

　Dまで四完、と思ったらシステムテストでDが落ちた。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 870 (Div. 2) Dまで。
A 全探索できるけど何を全探索すれば良いか難しい。Aとしては難問
B 差のgcd
C nの最も小さい1でない約数<=m
D 右端全探索。左側からB[i]+iをつめていき、その大きい二つか三つが候補。
E 計算量n*n*mかかる気がした。高速化できず終了。

— titia (@titia_til) May 5, 2023

D. Running Miles

　システムテストで落ちたのは、B[i]+iが同じならindexが大きい方から優先して調べるべき、ってところを考慮してなかったためでした。そこを修正してAC。

E. Walk the Runway

　bitsetを使うと聞いてもピンと来なかったが、こたつがめさんの実況放送の振り返りを聞いたら理解できた。

　ただ、Python通常のbitset（普通の整数をbitsetとして使う）では通らず、64個ずつに分けて、0～(1<<63)の数字の配列をbitsetとして使ったらACできた。

　この方法、書いたことなかったので勉強になった。面倒かと思ったけれど、意外と実装するのは簡単だった。