AtCoder Regular Contest 173

　Cまで三完。レートが上がって嬉しいけど、喜んでいい程の成績でもない……と思っていたけど、ARC/AGCで2200以上のパフォを出したのは去年一回だけだったらしい。なら、喜んでいいかも。

コンテストへのリンク

コンテスト後のツイート

ただし、これだと端がおかしくなるので別計算。計算量は未証明。
端がダメなことはランダムテストを書いて気付いた。
Dは各点からダイクストラ差をgcd取って判定……みたいなのを提出したけど、的外れっぽいね。

— titia (@titia_til) March 10, 2024

D - Bracket Walk

　解説・解説放送を見てAC。

　コンテスト中は迷走していたが、正しい解法は非常にシンプルですね。

　ただ、負閉路判定にベルマンフォード法が使えることをちゃんと覚えていなかった。ベルマンフォード法自体のやり方自体は覚えていたけども……。負の辺があるときの最短距離ではベルマンフォード法を使うというのは覚えていたけれど、負閉路判定にも使えると覚えておきたい。

　この問題やこの問題のsigmaさんの解説も押さえておく。

E - Rearrange and Adjacent XOR

　解説・解説放送を見てAC。

　最後に残る値を実験で求めるパートも難しいし、その後の実装も難しい。

　熨斗袋さんのツイートのように、「偶数個のxorで表せる」というのを、各A[i]に61bit目が立っていると考え、そのbitが0になるような答えを考えるというのが分かりやすいですね。