ちょっと散歩した。古地図を見ながら歩くのは楽しい。

---

ABC357に出た。多少練習してたせいか、久しぶりにまともに戦えた。生成AI禁止の触れが出るのを見ると結局競プロもそういう感じになるのか～という微妙な失望がある。ネット検索全てOKというのが競プロの座学競技としての異端たる所以のように感じていたのだが。

A: Mから順次引けばよい。

B: やるだけ

C: 再帰

D: $N$の文字列長を$L$とする。$N$が小さければ「$10^L$倍する→$N$を足す」を$N$回やればいいのだが、$N$がデカいのでダブリングをする。問題は上記の操作を複数回まとめてやるにはどうすればよいか。式変形すれば「$10^{kL}$倍する→$N(L^k-1)/(L-1)$を足す」によって$k$回まとめて出来るので、あとはこの調子でやればよい。

E: 連結とは限らないことに注意。なもりグラフは末端からBFSするものと相場が決まっている。木DPみたいにすることで各頂点に到達可能な頂点の数が求められる。末端を全て削ると輪だけが残る。輪の中の頂点は連結する全ての頂点から到達できるので、連結成分の大きさがそのまま到達可能な頂点数になる。

F: 区間変更と区間取得がある以上遅延セグ木以外に無いので遅延セグ木をやる。十分な情報を乗せれば大体通るのだが、こういう処理をやるのに純粋に慣れてないので時間をかけすぎて結局時間内に通せなかった。というかほぼ解けていたのだが最後に些細なミスがどうしても見つけられず終了した。大分くやしい。

G: 見てない