Potion [SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) F]

https://atcoder.jp/contests/abc192/tasks/abc192_f

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/abc192/submissions/20347402

DPで解くが、考察の流れは分かりにくいかもしれない。

どこから考え始めるか

色々な可能性から攻めていくが、問題の弱点から考え始めるのが良い。
弱点を探すと、N≦100という明らかな弱点が用意されている。
ここから何か読み取れないだろうか。
N≦100ということは同様にkもk≦100であることが言える。
つまり、kを固定した場合に簡単に解ける方法はないだろうか。

kを固定する

kを固定した場合、良い部分が固定化される

• k個選択すればいい
• k個選択したあと、必要な魔力の残りがkの倍数であればいい

特に魔力の残りがkの倍数であればいいという部分が重要で、魔力は制約を見るとかなり大きな値になるのでそのままでは扱いにくい。
魔力についてはkの倍数について考える、つまり、kで割った余りでグルーピングすることができるようになる。
この辺と過去の記憶を合成していくことでDPを使えば解けそうな感じに見えてくる。

DP

dp[i][use][mo] :=
i番目までの素材からuse個を選んで合成している、
かつ、
ポーションの魔力になるまで必要な残魔力をkで割った余りがmoであるときの、
ポーションの魔力になるまで必要な残魔力の最小値

以上のDPを使って計算する。
初期値はすべて∞でdp[0][0][X%k]だけXである。
初期値については、定義を見れば納得できるだろう。

後は、ナップサックのように選ぶ・選ばないで遷移を書いていけばいい。
DPを作り終わったら、目的のものはdp[N][k][0]に入っているはずである。
k個を選んでkの倍数、つまり、余りが0であるもの。

必要な時間はdp[N][k][0]/kとなるので、この最小値を求めれば答え。
ちなみに作れない場合もあるので、それは検出して弾くこと。

計算量はO(N⁴)くらいになってざっと10⁸くらいなのだが、dp問題は基本軽いので、まあ大丈夫。
もしTLEしたら、要素の配置をうまい事変えるとかしてキャッシュ率を上げるとか、枝刈りちゃんとするとかしてやれば通ったりする。
この辺のテク誰かまとめてくれんかな…

int N; ll X, A[101];
ll dp[101][101][101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X;
    rep(i, 0, N) cin >> A[i];

    ll ans = infl;
    rep(k, 1, N + 1) {
        rep(i, 0, N + 1) rep(use, 0, k + 1) rep(mo, 0, k) dp[i][use][mo] = infl;
        dp[0][0][X % k] = X;

        rep(i, 0, N) rep(use, 0, k + 1) rep(mo, 0, k) if (dp[i][use][mo] != infl) {
            chmin(dp[i + 1][use][mo], dp[i][use][mo]);
            if (use < k) chmin(dp[i + 1][use + 1][(((mo - A[i]) % k) + k) % k], dp[i][use][mo] - A[i]);
        }
        if(dp[N][k][0] != infl) chmin(ans, dp[N][k][0] / k);
    }
    cout << ans << endl;
}