AOJ 1333 Beautiful Spacing

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1333

解法

二分探索＋しゃくとり法．
二分探索は，普通に「スペースの隙間を X にして条件をクリアできるか」でやる．

次にしゃくとり部分．二分探索の過程で与えられた，空けていい間隔を S とする．

先に以下のテーブルを定義しておく．
dp[i] := i 番目の単語を左端にして，その後ろだけ考えた場合にクリアできるか．
更新は後ろからやる．

まず各 i について，「x[i] から x[j] まで一行に詰め込めるような，最大の j 」を考え，R1 とする．
次に，各 i について「x[i] から x[j] まで一行に詰め込んだ時に，Sをクリアできるような最小の j 」を R2 とする．
すると，R2 から R1 の間であれば，どこで一行を終えてもよい．また，位置 p を右端にして区切ってクリアできるかどうかは，dp[p + 1] をみればわかる．
したがって，
dp[i] = (dp[R2 + 1] + ... + dp[R1+1]) > 0
となる．

R1, R2, dp[R2 + 1] + ... + dp[R1 + 1] はすべてしゃくとりで計算できる．
したがって，これで計算量が O(NlogW) にできている．

ただし，最終行だけは右端に文字を置く必要がないと問題文に書かれているので，そこだけ辻褄を合わせる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int W, N;
    while(cin >> W >> N, W) {
        vector<int> x(N), sum(N + 1);
        for(int i = 0; i < N; ++i) {
            cin >> x[i];
            sum[i + 1] = sum[i] + x[i];
        }

        auto check = [&](int space) {
            vector<int> dp(N + 1);
            int limit_r = N, ok_r = N;
            int ok_cnt = 0;
            for(int i = N - 1; i >= 0; --i) {
                while(W - (sum[limit_r] - sum[i]) - (limit_r - i - 1) < 0) {
                    ok_cnt -= dp[limit_r--];
                }
                while(ok_r > limit_r || ok_r - i - 1 > 0 && (W - (sum[ok_r] - sum[i]) + ok_r - i - 2) / (ok_r - i - 1) <= space) {
                    ok_cnt += dp[ok_r--];
                }

                dp[i] = limit_r == N || ok_cnt > 0;
            }

            return dp[0] == 1;
        };

        int lb = 0, ub = W;
        while(ub - lb > 1) {
            const int mid = (ub + lb) / 2;
            if(check(mid)) {
                ub = mid;
            } else {
                lb = mid;
            }
        }

        cout << ub << endl;
    }
}

感想

無限にバグった．
最初 O(NlogNlogW) 解で通るやろと贅沢に書いていたら11secぐらいでTLEしてしまい，泣きながらしゃくとりを書いた．
終わってみればしゃくとりのほうがコードはスッキリしていた．