Eまで五完。
コンテスト後のツイート
E クエリごとにbit DPしながらダイクストラでいいと勘違い。予め全頂点間の移動時間を前計算して、橋の渡り方を全探索すると間に合う。
— titia (@titia_til) August 31, 2024
F セグ木DPを復元する感じかと思ったが、上手くいかないまま終了。
F - Gather Coins
セグ木DPで答えを求められるのはあっていたが、復元方法が分からなかった。
コインをソートした状態で考え、各コインが何回で取れるかという情報を持っておけば良い……というシンプルな方法だった。
G - As far as possible
解説放送を見てAC。
貪欲に長いpathを取っていけばいいというのは分かったが、実装が分からなかった。
木DPでそういうpath分解ができるというのは思いつかなかった。典型のようなので身に着けておきたい。
0 件のコメント:
コメントを投稿