PAST #3 が無料ということでを受けました。AtCoderさんマジ女神 !
というのはいいんだけどO問題クソ難しかったです
誰だこの問題作ったの、これまともな解法ないだろ
まず問題見てちょっと考ると簡単なDPが思いつきました
各輪について1投目で使う/使わない、2投目で使う/使わない、3投目で使う/使わないの8通りについてスコアへの寄与が計算できるので
dp[$i$][$j$][$k$][$l$] : $i$番目の輪までで1投目を$j$回, 2投目を$k$回, 3投目を$l$回使ったときの最大スコア
みたいなDPが立ちます
状態数は(ほぼ)$NM^3 \approx 6.2 \times 10^{10}$です。
...
遷移8個もあるしさすがに間に合うわけないので工夫を考えます
$M > \frac{N}{2}$の場合、選ぶ選ばないを全部反転して$M \leftarrow N - M$をすれば上のDPがほとんど同様に適用できます
$M \le 250$になって状態数が$500 \times 250^3$になりました(おいおい)
次に$N$個を半分ずつに分けて先ほどのDPをそれぞれでやることを考えました
そうすればdp1.back()[i][j][k] + dp2.back()[M - i][M - j][M - k]の最大値が答えです
ところで半分に分ける前にランダムシャッフルしておけば、最適解はどうせ3投全てにおいて左右からだいたい半分ずつ選ぶだろうから、左右それぞれのDPにおいては$i, j, k$が最終的に$\frac{M}{2} \pm 20$くらいに収まるやつだけ見ても多分バレないような気がします。うしししし
この条件でdp[$i$][$j$][$k$][$l$]として有効なのはだいたい
- $j, k, l$が$i$以下($i$個しか見てないので当たり前)
- $j, k, l$が$\frac{M}{2} + 20$以下
- $j, k, l$が$(\frac{M}{2} - 20) - (N - i)$以上(以後全部使っても$\frac{M}{2} - 20$に届かないのは見なくていいので)
(off-by-oneとかは考えてないのでだいたいで)
実際に見る状態数は最大で$N = 500, M = 250$の場合でだいたい
$2 \times $ (左右で2回やるので)
$(1^3 + 2^3 + ... + 144^3 + 145^3 + 145^3 + ... + 145^3 + 144^3 + 143^3 + ... + 40^3)$
となります
計算すると$4 \times 10^8$くらいになってます、ほれーい !
DPをin-placeで更新して、遷移8個は直書きすると1400msくらいで通ります
やった ! (爆
(SIMDの類は多分役に立たないのでやってません)
$\pm 20$ の $20$ は $10$ くらいまでは減らしても通りました
正しい答えを出す確率みたいなの誰か計算してくれ
($20$ の値に関わらず) $\Theta(N^4)$ですがもとのDPに比べて1 / 150くらいに状態数が減ってます
ふぅ、反省してます
やったやった、全完全完うしししし...