Codeforces Round #345 (Div. 1) B. Image Preview
この回かなり簡単だったみたいですね…(普段だと僕は B から苦戦しているはず)
解法
まず考察です。
写真の見かたを考えると, 「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; }