AtCoder Regular Contest 010 C - 積み上げパズル

問題

 m色のうちどれか1色で塗られているブロックがn個順番に落ちてくる。1個落ちてくるたびにそのブロックを山に積むか捨てるか選ぶことができ、最終的に山に積まれたブロックによって次のように点数を付ける。

  • 色ボーナス:色ごとに決められた点数が個数分与えられる
  • コンボボーナス:同じ色のブロックがx個続いて積まれる場合、定数Yに比例したY(x - 1)点与えられる
  • 全色ボーナス:m色全て存在する場合Z点与えられる

 点数を最大化せよ。

解法

 メモ化再帰で解く。状態を一意に定めるために必要な情報は

  • 今見ているブロックのインデックス(0からn-1まで)
  • 直前に積まれたブロックの色(m種類)
  • 今までに積まれたことのある色

 であり、最後のものはm色にそれぞれ1ビット与えて管理することにより2^{m}の種類となる。全体で計算量はO(nm2^{m})であり、間に合う。

 遷移は

  • 積む場合:色ボーナス + 直前が同じならコンボボーナス + 今回で全色達成したなら全色ボーナス
  • 積まない場合:そのまま

 というようにしていけばよい。

反省

 1時間14分でAC。最初はまずDPで必要な状態がきちんと考察できず時間が30分ほど溶かした。というのも、直前にある色が「何個」続いているかも状態に含まないといけないと勘違いしており、これだと状態の数が多くなりすぎて計算量的に間に合わないと思っていたのだった。

 わからないままにコードを書き出してみると直前に何個続いているかは保持しなくてよいことがわかり、そのまま書き出す。ここでスッと実装できていたら40分ほどでできていたのだろうが……。

 最初はメモ化再帰で書き始めたにも関わらず、書きやすいと勘違いしてforループによるDPに書き直したところサンプルさえ合わない状態に。全色ボーナスを毎回足していたり、全色達成しえないときにも足していたりと、forループでは面倒くさいと思い直してメモ化再帰を書き直してようやくAC。実装の方針がダメダメだった。

 全色ボーナスは最後に足すのでも問題なかったか。そこによって遷移中の方針が変わることはないか……どうか。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

ll n, m, Y, Z;
vector<ll> a;
vector<ll> p;
ll max_pow;

vector<vector<vector<ll>>> memo;

ll solve(ll i, ll pre, ll stacked) {
    if (i == n) {
        return 0;
    }

    if (pre!= -1 && memo[i][pre][stacked] != -1) {
        return memo[i][pre][stacked];
    }

    //積む
    ll score1 = p[a[i]];
    if (a[i] == pre) {
        //preと同じ色ならボーナス
        score1 += Y;
    }
    ll nstacked = stacked | (1LL << a[i]);
    if (stacked != max_pow - 1 && nstacked == max_pow - 1) {
        //今回で全色達成したならボーナス
        score1 += Z;
    }
    //次以降
    score1 += solve(i + 1, a[i], nstacked);

    //積まない
    ll score2 = solve(i + 1, pre, stacked);

    if (pre != -1) {
        memo[i][pre][stacked] = max(score1, score2);
    }

    return max(score1, score2);
}

int main() {
    cin >> n >> m >> Y >> Z;

    p.resize(m);
    a.resize(n);
    max_pow = 1LL << m;
    memo = vector<vector<vector<ll>>>(n, vector<vector<ll>>(m, vector<ll>(max_pow, -1)));

    vector<char> c(m);
    map<char, ll> color2num;
    for (ll i = 0; i < m; i++) {
        cin >> c[i] >> p[i];
        color2num[c[i]] = i;
    }

    string b;
    cin >> b;
    
    for (ll i = 0; i < n; i++) {
        a[i] = color2num[b[i]];
    }

    cout << solve(0, -1, 0) << endl;
}