全完したものの、Eに時間かかりすぎ。
C - Bowls and Dishes
最初、この前のARCのBみたいにUnion-findを使う問題に見えた。
が、ちょっと考えるとそれでは上手くいかず、Kの制約を見てbit DPに気付いた。
D - Staircase Sequences
とりあえず立式！
lからrまでの数の和の公式を使って立式すると、条件が分かる。
E - Magical Ornament
Kの制約からbit DPっぽい……とは思ったけれど、最初それをどう使えば良いか分からなかった。
$C_i$達同士の距離を求め、どう進むか順番（Kの順列）を決めたら答えは求まるけれど、それだとK!の計算量がかかってしまう。
そうやってしばらく考えた後、この問題は巡回セールスマン問題に似ていると気付いた。それでもどう解くか分からなかったけれど、巡回セールスマン問題がbit DPで解けるということは聞いたことがあったので検索。このページを見て、なるほど、と思い実装した。
最初気付かなかったのは仕方ないとしても、巡回セールスマン問題をbit DPで解く方法は頭に入れておかないと。
F - Shift and Inversions
とりあえず転倒数は求められる。
あとは、最初の数字を抜いたとき&それを最後に入れたときについて差分計算すれば良い。
0 件のコメント:
コメントを投稿