ABC_285_E "Work or Rest"をrubyで解く
試験勉強しなきゃならんから競技プログラミングの勉強が捗るぜ。
今回の問題はこちら
今回の問題は既にpythonの解説記事があります。
やる事はほぼ同じなので、pythonが読めないruby専の方だけこの先へお進みください。
DPに気づくコツ
緑以下でDPが得意な人は多分いないと思います。
私としてもコツがあるならこっちが聞きてーよと言いたい所ですが、今回ひらめいた切っ掛けは休日で区切られた範囲内での最適解は、範囲外、特に範囲より前の部分に左右されないという点でした。
10日あるうちの三日目で休んだ場合、「1~2日目に働いていた場合は4日目以降は休みを入れた方が最適、1~2日目に休みがちだった場合は4日目以降はぶっ続けで働いた方が最適」という事はありません。4日目以降の最適解は1~2日目に左右されないわけです。
こういう問題では現時点までの(各条件の)最適解を計算材料にして一個先の最適解を算出するようなDPである事が多いです。ナップザック問題だってナップザックに入れるアイテムのスコアが固定だからDPで解けるのであって、アイテムの組み合わせごとにスコアが変わったら大難問ですよね。
平日・休日サイクルのモジュール化
今回の問題では休日に挟まれた平日の連続期間が重要ですが、両端に休日を置いて考えるとこんがらがるので「まず一日休日、その後連勤」のサイクルで考えます。
一日サイクルは一日休み、2日サイクルは一日休んで一日働く(直後に次のサイクルの初日=次の休日が来る)時のスコア、3日サイクルは一日休んで2日働く時のスコア……、一日働いて残りは週末までぶっ続けで働くスコアを全て予め計算してキャッシュしておきます。これがナップザック問題でいう所のアイテムです。
あとはこれを週というナップザックに最適に詰めていくだけです。サイクルは何回使ってもいい(300日で1休2勤を100連打とかもOK)なので、通常のナップザック問題ではなく個数制限なしナップザックで問いてください。
いやその個数制限なしナップザックを説明しろよ
という人だけ読み進めてください。分かる人は最後のACコードに飛んでください。
一般的なナップザックはループを回してアイテムを一個ずつ取り出し、「これを選ぶならナップザックがどこまで埋まって最適スコアがいくら、選ばないならナップザックがどこまで埋まって最適スコアがいくら」といった解き方をします。しかし個数制限がない場合はTLEの危険があります。今回のナップザックのサイズは5000なので一日サイクルを5000個、2日サイクルを2500個……ってやれば解けるんでしょうか？ 誰か教えて下さい。
そこでナップザックの容量の方をループで取り出します。「ナップザックを1マスきっちり埋めた場合の最適スコアがいくら」「ナップザックを2マスきっちり埋めた場合の最適スコアがいくら」……という方向です。
1マスとか2マスで考えると逆にわかりにくいので、5マス目まで最適解[0,a,b,c,d,e]を求め終わって次が6マス目というパターンを考えて見ましょう。6マスを埋めるためには
・空(0マス)のナップザックに6マスのアイテムを一個入れる0+f
・1マスのアイテムに残り5マスの最適解の組み合わせを足すa+e
・2マスで最適の組み合わせに4マス最適の組み合わせを合わせるb+d
・3マス最適の組み合わせを二個詰めるc+c
の4パターンが考えられます。この中でのハイスコアが「ナップザック6マスきっちりでの最適組み合わせ」となるわけです。
「2マス×3とかのパターンが入ってない」などと考える必要はないわけですね。2マス×2の4マス最適解を調べたときにすでに採用されているはずで、もし却下されていたらそもそも2×3がハイスコアになる事自体がありえません。
あ、隙間残したら駄目ですよ、念の為。
ACコード
まず8行目でdp配列を「初日休んで、後は(index-1)日間ぶっ続けで働く」のスコアで埋めます。(0日間のスコアは計算の便宜上0にしておきます。)
その後14行目で0日間から順に「i-1日間までの最高効率はわかっているので、それらを2つ組み合わせてi日間の最高効率を求めて、いいスコアが出れば更新」を繰り返して行きます。二日間(一日休んで一日働く)までは更新なんて起きようがないんだから三日間くらいからでも良かったんじゃないかなあ。
その後19行目で半分に割っています。ごちゃごちゃやっていますが、これは1.upto(i / 2)とやっているのと同じです。shorterが0でlongerぶっ続けのパターンは8行目で最初にやっているので、考えなくてokです。
本番中はこんな華麗な解法など思いつかず、「一日休んでの最適解、2日休んでの最適解。一日目と三日目に休んだ時の最適解、一日目と四日目に休んだ時の最適解……」を算出し、反転して合計N+2日(切れ目で2連休しているのと、最後の一日の休日は翌週にはみ出す)にして足すというアーティスティックでアクロバティックな解き方をやっていました。
苦手なジャンルはDPで、二度とできないしそもそも説明できないようなエスパーでACしました！
緑コーダーなんて、それでいいんだよ。
お前……カッコイイぜ。(例の画像)
Discussion