コンテスト後のツイート
F DP[次の位置が決まっていない方の位置]=最小コストとする。片方しか動かさない場合は、Bと同じところから、左右に+1していけば良い（ただし、別のものの位置は追い越せない）。両方動かす場合は、ギリギリまで動かす一個だけもてば良い。
— titia (@titia_til) October 19, 2024
……で良いと思ったが22/37ACで終了。
↑ツイートのFの位置が間違っています。
F - Hands on Ring (Hard)
既にあるACコードとランダムテストなどしてAC。
本質的なやり方は正しかったが、場合分けが足りていなかった（目的地の場所に別の手がある場合、二通り押し出すことを考えなくてはいけないのを忘れていた）り、既に目的地に手がある場合にも押し出すことを考えて答えが減ったりし、非常に苦労した。
コンテスト後に一時間以上かかっている。本来ならランダムテストを書く時間も必要だったからもっとかかっただろう。解法は分かってもACは遠い問題ですね。
G - Treasure Hunting
解説放送を見てAC。
解法を思い付くのは難しいかもしれないけど、解法を教えてもらったとき理解するのは難しくない。
ただ、実装方針はやや難しい。トポロジカルソート順にマージするのか？ などと考えてしまいダメだった。
平均重みが大きいものから、親と比較し、マージしていくというのが正解。方針が分かってしまえば実装も重くない。
類題（元ネタ？）というこれも解いておきたい。→ACしたけど結構実装に時間かかってしまった。maspyさんが類題をまとめてくれているので、これも解いておくべきか。
0 件のコメント:
コメントを投稿