Problem : Dinner
問題文
- 与えられる要素は整数 $N, P, Q$ と長さ $N$ の数列 $C$ である．
- この問題では $N$ 日間の夕食の計画を立て，各日の幸福度の合計を最大化したい．
- 各日の行動の選択肢は2つあり，「自炊する」か「食堂に行く」ことである．
- $i$ 日目の行動が「食堂に行く」である場合，この日の幸福度として$C_i$を得る．
- $i$ 日目の行動が「自炊する」である場合，この日の幸福度として$P \times y_i$を得る．
- なお，数列$y$は次のように決まる :
- $y_1 = Q$
- $i$ 日目の行動が「自炊する」である場合， $y_{i+1} = y_{i} + 1$ が成立する．
- $i$日目の行動が「食堂に行く」である場合， $y_{i+1} = y_{i} - 1$ が成立する．
( Japan Alumni Group Summer Camp 2014 Day 4 Problem D, 2014/9/15 )
解説1 (確かこれが想定解法だったはず…)
すべて「食堂に行く」ことにする．この時，幸福度は $S=\sum_{i} C_i$ であり，この時の数列 $y$ の具体的な値は $y_i = Q + 1 - i$ となる．この数列を $y'$ とおく．
ここからは，$k$ 日を選んで「自炊する」を選択する場合を考える． 仮に 数列 $y$ が $y'$ のまま変化しなければ $i$ 日目に自炊した場合の幸福度は $(Q + 1 - i) \times P$ である．
実際には数列 $y$ は変化し，先ほどの幸福度からの増分は，すべての日で合計すると $ k \times (k-1) \times P$ となる． なぜなら，$i$ 日目が $j$ 回目の自炊日であれば $y_i = y'_i + 2 (j-1)$ となるからである． ここで求めた増分は具体的な「自炊する」日の選択日に依存しない．
したがって，すべて「食堂に行く」場合と比較した幸福度の差分は次のようになる． $$ (\sum_{i : (k日分の自炊日)} P \times (Q + 1 - i) - C_i )+ k (k-1) P $$ この場合 $k$ が定数であることも考慮しつつ整理すると，次の式を得る．
$$ \sum_{i : (k日分の自炊日)} - P \times i - C_i + (定数) $$
元の目的は最大化なので，$Pi + C_i$ の昇順に自炊日を採用すれば 自炊日数 $k$ の最大幸福度を得ることができる．
元々求めたかった値は 固定する日数 $k$ を変化させた中での最大値である． 上記式を整理すれば，各 $k$ ごとの取りうる最大値も求めやすくなり，全体として $O(N \log N)$ 時間で求めたい値を求めることができる．
コメント
特別な解からの比較を考えると特別な性質が垣間見えて，それを利用すると解ける問題，という感じでしょうか．
とても自然な $O(N^2)$ 時間のDPをベースにした高速化も効かない上，思いつきやすい貪欲法だと破綻するため，考察に手戻りが発生しやすい問題です．
解法2
コメント
特別な解からの比較，という観点では同じことをしています．
この問題に関しては私が解説記事を書いていなかったため，彼が解説を書いてくれました．可能な限り式を使用していない分，設定側を調整している印象です．
この方針に関しては式を使用せずに問題設定を等価変形していくため，再利用が難しい解法をもつ問題だと認識されてしまったかもしれません．
そういえばtesterのよすぽさんは当時大学一年生でした．今でも問題を多く作成されていて本当にすごいです．
解法3
2020年9月に新しめのタイプの解説記事が登場しました． optさんの記事へ
コメント
上記の解法では突然 $k$ を固定していますが，このような固定の仕方は見えづらい印象です． こういった壁を簡便な式変形で吸収している点で納得しやすいと思います．
また，バイナリ変数に対する $x_i^2=x_i$ の変形は最適化界隈の人っぽいなぁという印象を持ち，個人的にはポイント高めでした．人によっては一番思いつきづらいパートかもしれません．
余談
- やはりコンテスト本番当時も多くのチームを苦しめました．
- 最初はジャッジの入力を適当に作りましたが，それだとある種の山登りか何かで通ってしまいました．
- そこで入力セットは作りこみをして，単純な空間で考えれば局所最適解が多く発生するようにしました．
- 最小化 / 最大化問題はこういう時に怖いです．
- 私の問題では比較的よくあることですが，サンプルが小さいものばかりでした．今更ながら申し訳ないなと思います．