【思考ログ】COLOCON2018D: すぬけそだて――トレーニング――
Nov 24, 2019 17:11
ますぐれです。昨日のDDCCで久しぶりにhighestを更新できました。この調子で青まで行けたらいいなあって気持ちです。
今日の問題はバチャコンで解いた問題です。
本日の問題
問題概要
長さ$N$の単調増加整数列${T_i}$と整数$X$が与えられます。
時刻$t = 0$の時点で$X$のスタミナを所持しています。スタミナは1秒ごとに1ずつ増えていきます。$X$より多くはなりません。
時刻$T_i$のタイミングでスタミナを任意の量だけスコアに変換することができます。
各$K = 1, \ldots, N$について、$K$個以下の$T_i$を選んだ時のスコアの最大値を求めましょう。
制約
- $1 \le N \le 5000$
- $1 \le X \le 10^9$
- $1 \le T_i \le 10^9 \quad (1 \le i \le N)$
考察
最初に考えたこと
とりあえずある$T_i$を選んだ時、そこでスタミナを使い切らないのはもったいないので考えなくてよいことが分かります。
そして選ぶ$K$個の$T_i$間の距離をすべて$X$以上離すことができるなら、スコアは$KX$となりこのときが最適です。
解法1(嘘解法)
以上の考察から、$K$が十分に小さいうちは最大値$KX$が得られるはずです。また、初期のスタミナがマックスなので$T_1$を選ばない理由はないです。
従って、$K$が小さいうちは最後に選んだ$T_i$から$X$以上離れた最小の$T_j$を取れば最適になります。
$X$以上離して取れなくなったら、現在取っている隣接している$T_i$間の区間の中から一番長いものを選んで、その間にいる$T$のうちスコアを最大化するものを追加すれば良いと考えました。
これを実装して提出するもWAがでます。
解法2(嘘解法)
少なくとも、最初の処理は間違いなく最適なので誤りはないと考えられます。なぜなら、$K$回の操作で取得できる最大値と完全に一致しているためです。
そうすると嘘なのは後ろの構築っぽいんですが、特にダメなところが思いつかなかったので、とりあえず計算量的にも行けるし全部の選択していない$T$を見るようにしました。がこれもWAです。
ここでバチャの時間が終わったので解説を見ました。
なんでハマったのか
解説に書いてある通り、DPができます。そっちの解法については解説を読めばわかるので説明はしません。遷移の計算量落とすところが工夫ですが、これはまあそんなに難しくはないと思いました(解説を読んだ後なので適切な評価ができません)
今回の敗因は各$K$に対して選択する$T_i$の集合が違っても良いという事実が頭の中からすっぽり抜けていたところです。 この認識がなかったので、前から貪欲で最適解自体を構成しようと考察を進めています。実際には最適値しか求められていないことからもこの考察の筋が悪いことが分かりますが、当時は気づけませんでした。
制約見ても空間計算量を$O(N^2)$使うDPができるなってことに気づくべきでしたね。更にいえばDPは貪欲よりも考慮する解空間がでかいはずなので、計算量に余裕があるならこっちの方が様々な可能性が拾えるはずです。 その点から言えば、制約を見て小さかったらDPを考慮に入れるというのは結構重要な話なのかもしれないと思いました。
反省点
- 制約に余裕があれば探索空間を広くとろう
- 貪欲は完全に証明ができるとき以外は使っちゃダメ
- 逆にとりあえずDPを考えるのは悪くなさそう