またレートを落としてしまったが、大失敗というわけでもないので……。
コンテスト後のツイート
F 子方向に何歩進めるか？ と、親方向へ進むものを別に管理しようとしたが上手くかけずTLE。
— titia (@titia_til) July 12, 2025
自分でも計算量が悪化してそう、と思って書いていたのでダメ。
F - Jump Traveling
解説＆解説放送でAC。
後一歩で解けたのではないか？ とコンテスト終了時には思っていたが、本質が分かっていなかった。
ウニグラフのときの遷移の処理が難しいが、各頂点について、「その頂点についてk歩目に行く」というのは二回遷移してあれば十分、というのがポイントで、それで計算量を減らすことができる。
言われてみれば分かるが、思いつきにくい計算量の減らし方だった。
辺属性のDPを考えているとき、頂点の出入りで計算量を減らせる、というのは気付きにくい。
G - AtCoder Express 4
解説放送を見てAC。
「区間に辺を張るテク」は聞いたことはあった気もするが、内容は覚えておらず、今回初めて実装した。
理解するのは難しくないが、実装は結構面倒くさいね。