Codeforces Round 880 (Div. 1)

　A一完のみ。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 880 (Div. 1) Aしか分からなかった。
A aを全探索。
B mの制約が小さければできそうなのだが……。
C 鳩ノ巣原理を使うのかなーと考えていたけど、そこから考察が進まず。

— titia (@titia_til) June 18, 2023

B. Lottery

　こたつがめさんの実況放送を見てどうにか理解した。

　この解法に思い至れなかった要因は、当たりの位置をずらすことを考えていて、「何番目を買うとしたら当たりくじの位置はどこからどこまでか？」という考え方を全くしなかったこと。その後の考察も難しいけど、少なくともこれはどちらも考えてみるべきだった。

　PyPyだとTLEしたためRUSTに直したが、そこでも苦戦した。特に、

・RUSTのbinary_searchで、その要素が複数個入っていたときは、そのうちどのindexをわたすか分からない（多分。自分で実験した限りはそうだった）

　というのを知らなかったため原因に気付かず大変だった。今度RUSTで二分探索を使うときは気を付けよう。

C. Twin Clusters

　こたつがめさんの実況放送で理解。ただ、実装は乱択で通した。

　区間xorの値が同じになるのが二つあれば、それを使って答えが作れるのだろう……とは思っていたが、0が一つだけある場合はそれを除いて考えて良いということが分かっていなかった。そうすると、端点が同じ（[l, r]、[l2, r2]でl=l2の場合）な場合に答えが作れるということも。

　これを思い付いていれば、乱択しようと思えたかな……。

　乱択じゃない解法については、鳩ノ巣原理を利用したいという気持ちを強く持てば下半分と上半分の桁で分けようと思えるのかな、と感じた。

　ただ、この鳩ノ巣原理はかなり余裕があるからできているわけで、それなら乱択で通るよね、という気持ちになった。