[ARC140] B - Shorten ARC
[Q] https://atcoder.jp/contests/arc140/tasks/arc140_b
考察
0. "ARC"を"AC"にしても、新たな"ARC"は生まれない。
1. "ARC"を"R"にしたとき。
"AARCC"から"ARC"が生まれることはある。
2. Rを起点にして、左にA、右にCの連結個数をメモする。
ARC = 1
AARCC = 2
AAARCCC = 3
最大値と最小値を常に取得したかったので、multisetに入れた。
3. あとは2.の数値処理。もう文字列Sは見ない。
もし奇数番目の処理なら、大きい値3->2に減らして、2は再処理できる。
なので、最大値を処理するのがいい。
もし偶数番目の処理なら、3->0で消滅してしまう。
なので、最小値を処理するのがいい。
4. 処理できなくなるまでシミュレート。
実装
int main() {
cincout();
ll N;
string S;
cin >> N >> S;
multiset<ll> M;
rep(i, N) {
// Rをみつけて、左A右Cの個数を数える
if (S[i] == 'R') {
ll cnt = 0;
ll n = 1;
while (i - n >= 0 && i + n < N) {
if (S[i - n] == 'A' && S[i + n] == 'C') {
++cnt;
} else
break;
++n;
}
if (cnt > 0) M.insert(cnt);
}
}
ll ans = 0;
bool odd = true;
// simulate
while (!M.empty()) {
++ans;
if (odd) { // 奇数番目なら最大値をとる。
auto it = M.end();
--it;
ll val = *it;
M.erase(it);
if (val > 1) {
M.insert(val - 1);
}
} else { // 偶数番目なら最小値をとる。
M.erase(M.begin());
}
odd ^= true;
}
cout << ans << endl;
}