Codeforces Round #345 (Div. 1) B. Image Preview

この回かなり簡単だったみたいですね…(普段だと僕は B から苦戦しているはず)

問題

codeforces.com

解法

まず考察です。
写真の見かたを考えると, 「0 より右側の写真を見に行って, 次に左側(n-1, n-2, ... のことです)を見に行って, また右に…」とやるのは明らかに効率が悪いです。先に右側をギリギリまで見た後, 左側を見て終わりにする, とやるか, 左側までギリギリ見た後, 右側を見て終わりにする, のいずれかにするほうが効率が良いです。

先に右側を見たほうが良いか, 左側を見たほうが良いかは, 左側を見に行く数, 右側を見に行く数のどちらが多いかで決まります。

ここらへんまで考察すればあとは簡単です。
まず, dp[i] = (右側に突き進んでいった時, i を見終わるのにかかる時間), rdp[i] = (左側に突き進んでいった時, i を見終わるのにかかる時間) というのを前計算しておきます。で,

右側に進む上限 rp を決めた時に, 左側はどこまですすめるのか, というのを各 rp について二分探索し, (rp+n-lp+1) の最大値を求めれば良いです。

左側に進む座標 lp, 右側に進む座標 rp (rp < lp に注意)を決めた際, 写真をすべて見るのにかかる時間は, まず dp[rp] + rdp[lp] です。また,

• rp > n-lp のとき, 先に左側に進むほうが移動に必要なコストが下がる
• n-lp < rp のとき, 先に右側に進むほうが移動に必要なコストが下がる

ことに注意して, かかる時間を求めます。

const int MAXN = 500500;
// [0, i) まで見るのにかかる時間
ll dp[MAXN], rdp[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, a, b, T;
    cin >> n >> a >> b >> T;
    string s;
    cin >> s;
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        dp[i] = dp[i-1] + a + 1;
        if (s[i] == 'w') dp[i] += b;
    }
    for (int i = n-1; i >= 0; i--) {
        int prev = (i+1)%n;
        rdp[i] = rdp[prev] + a + 1;
        if (s[i] == 'w') rdp[i] += b;
    }
    int ans = 0;
    int first = 1+(s[0]=='w' ? b : 0);
    for (int rp = 0; rp < n; rp++) {
        if (first+dp[rp] > T) continue;
        ans = max(ans, rp+1);
        int low = rp, high = n-1;
        auto f = [&](int x) {
            ll t = first;
            t += dp[rp];
            t += rdp[x];
            if (rp > n-x) t += a*(n-x);
            else t += a*rp;
            return t;
        };
        while (high - low > 1) {
            const int med = (high+low)/2;
            if (f(med) <= T) high = med;
            else low = med;
        }
        if (f(high) > T) high++;
        ans = max(ans, min(n, n+rp-high+1));
    }
    cout << ans << endl;
    return 0;
}