ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)

　Fまで六完でした。

コンテストへのリンク

コンテスト後のツイート

ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286) Fまで六完。
C x回rotateしたときの最小値をそれぞれ調べる
D DP
E N回BFS
F 拡張ユークリッドの互除法で復元。素数だけだとダメで、4や9を使う。
G 一筆書き問題に帰着させたいが、帰着させるのを失敗。

— titia (@titia_til) January 21, 2023

G - Unique Walk

　解説AC。

　一筆書き問題へ帰着する方針はあっていたが、帰着させ方が分からなかった。

　Sに含まれない辺でつながった頂点をUnion-findでくっつけて良い、というのは解法としては分かりやすいが、直感的に明らかという気もしない。ので、思いついていたらすぐ実装しようと思えたかも分からない。

　ただ、Sに含まれる辺については一筆書きの考え方を使えそうなのだから、Sに含まれない辺で何かをしよう、と考えるべきだった。