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