SRM 536 div1 med: RollingDiceDivOne

Laycrs さんがこどふぇすの時言ってた問題多分これですね。

問題

TopCoder Statistics - Problem Statement

解法

ｴｲﾔでサンプル合わせたら WA 食らったので editorial 見ました。
http://apps.topcoder.com/wiki/display/tc/SRM+536

まず様子を観察して見るためのコードを書いてみます。gnuplot を使ってたので僕も gnuplot で書きました。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> dice(n);
    for (int i = 0; i < n; i++) cin >> dice[i];
    vector<int> ways(100);
    ways[0] = 1;
    for (int i = 0; i < n; i++) {
        vector<int> _ways(100);
        for (int j = 0; j < 100; j++) {
            if (ways[j]) {
                for (int k = 0; k <= dice[i]; k++) _ways[j+k] += ways[j];
            }
        }
        ways = _ways;
    }
    int maxX = 0, maxY = 0;
    for (int i = 0; i < 100; i++) {
        if (ways[i] == 0) break;
        maxX = max(i, maxX);
        maxY = max(ways[i], maxY);
        cout << i << "  " << ways[i] << endl;
    }
    FILE *fp = popen("gnuplot -persist", "w");
    if (fp == NULL) return -1;
    fprintf(fp, "set xrange [0:%d]\n", maxX);
    fprintf(fp, "set yrange [0:%d]\n", maxY+1);
    fprintf(fp, "plot '-' with lines linetype 1 title \"ways\"\n");
    for (int i = 0; i < 100; i++) {
        if (ways[i] == 0) break;
        fprintf(fp, "%d\t%d\n", i, ways[i]);
    }
    pclose(fp);
    return 0;
}

見る前から知ってた, という人も多いかと思いますが一応説明しますと, 最終的なグラフは左右対称であり,
(狭義単調増加) -> (一定の値キープ) -> (狭義単調減少), というようになります。
一例として, 上のプログラムに 3 1 2 17 と入れたものを載せておきます。

このことから,

• dice の和
• (一定の値キープ)の幅(plateau(台地) とする)

がわかれば, 答えを求めることが出来ることがわかります。dice の値は 1〜d, というようにするよりも, 0〜d, とするほうが扱いやすいのでそのようにします。

plateau を求めましょう。これは今の確率分布から dice[i] を振った時, 一定のルールにしたがって変化します。あ, あと今までに振った dice の和 sum という変数も用意しておきます。

dice[i] < plateau の時

この場合, 図のように「plateau の中からのみ遷移する」という dice の和が存在し, それが最大になります。これによって, plateau の数は d 減少します。
dice[i] > sum の時

この場合分けに最初気づきませんでした(上の 1 2 17 という例を見ると明らかにそういう場合があることに気づく)。
この場合は, 今までにあったすべての事象(0, 1, ..., sum が出る確率)をすべて包含しながら派生する場合が dice[i]-sum+1 個存在します。なので, plateau = dice[i]-sum+1 です。
それ以外
ちょっと説明しづらいですが, 「左右から平等に遷移させる」のが最も確率を高くしそうです。そのため,

• dice[i]-plateau が奇数の時は plateau = 1
• dice[i]-plateau が偶数の時は plateau = 2

となります。

これを 各 dice について回せば答えが得られます。

class RollingDiceDivOne {
public:
    long long mostLikely(vector <int> dice) {
        ll sum = 0, plateau = 1;
        for (int d : dice) {
            d--;
            if (d < plateau) plateau -= d;
            else if (sum <= d) plateau = d-sum+1;
            else {
                ll tmp = d-plateau;
                if (tmp%2) plateau = 1;
                else plateau = 2;
            }
            sum += d;
        }
        ll ret = dice.size();
        cout << sum << "  " << plateau << endl;
        if (sum%2==0) {
            assert(plateau%2==1);
            ret += sum/2 - plateau/2;
        } else {
            assert(plateau%2==0);
            ret += (sum-plateau+1)/2;
        }
        return ret;
    }
};