AtCoder Beginner Contest 140 D - 今日から始める競プロ日記
はじめに
AtCoder Beginner Contest 140 D ( ABC 140 D ) 。
コンテスト中に解けなかった。
前に見たことあるなー、 解けそうだなー、 と思いながら結局解けなかった問題。
D - Face Produces Unhappiness
解いた方針
自分なりに考えてみた解き方なので、 全然スマートではない。
文字列の圧縮(連続した同じ文字の文字数をカウント)
以下の文字列において、 同じ文字がいくつ連続しているかでまとめてみる。
LRLRRL
Lが1つ、Rが1つ、Lが1つ、Rが2つ、Lが1つ。
L R L R L 1 1 1 2 1
ここではもう、'L'と'R'はどうでもよくて、
11121
という整数列が重要になる。
反転する前の幸福人数を数える
11121
における幸福な人の数を数える。
条件:目の前にいる人が同じ向きを向いていれば幸福
以下は例。
文字列 | 幸福値 |
---|---|
R | 0 |
RL | 0 |
RLR | 0 |
RRL | 1 |
RLL | 1 |
RRR | 2 |
上の表から分かる通り、 連続した文字数が1である文字列では幸福値は0になる。
連続した文字数が2である文字列は幸福値は1。
連続した文字数が3である文字列は幸福値は2。
つまり、
幸福値 = 連続した文字数 - 1
である。
ということで反転する前の整数列
11121
の幸福値は1
である。
さらに、
一度幸福値を求めたら、
この11121
は11111
と考えられる(もうカウントされているから)。
反転したときの処理
11111
を一度反転させたとき、 幸福値はどのように変化するか考える。
例として2番目を反転させてみると、
両隣の文字と同じ文字になるので1+1+1=3
より
以下のようになる。
131
このとき、幸福値は+2
されたことが分かる。
では端っこの場合はどうなるか。
11111
の左端を反転させてみると以下のようになる。
2111
このときの幸福値は+1
されたことが分かる。
つまり、
- 端っこの場合は+1
- 端っこでなければ+2
することが分かる。
あとはK回の反転回数の内、 まずできるだけ端っこの文字を反転させて、 まだ反転させられるのならば端っこも反転させる。
ちなみに、 最大値はN-1になるので気を付ける。
流れ
- 同じ文字を数えて整数列を作成
- できるだけ端っこではない文字を反転させる
- 左端と右端も反転させられるならさせる
- 最大値は
N-1
を超えないので気を付ける
計算量のオーダーはO(N)
になるはず。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { // 入力 ll N, K; cin >> N >> K; string S; cin >> S; // 連続した文字を数えて整数列を作成 vector<ll> v; ll cnt = 1; char c = S[0]; for(int i = 1; i < N; i++) { if(c == S[i]) { cnt++; } else { v.push_back(cnt); c = S[i]; cnt = 1; } if(i == N-1) v.push_back(cnt); } // 反転する前の幸福値を計算 ll ans = 0; for(int i = 0; i < v.size(); i++) ans += v[i]-1; // 反転処理 // 端っこではない文字の反転 if(K <= v.size()-2) // K回だけ反転 { ans += 2 * K; K = 0; } else // 端っこではない文字をすべて反転 { ll times = max(0LL, (ll)(v.size()-2)); ans += 2LL * times; K -= times; } // 端っこの文字を反転 ans += min(2LL, K); //端っこは左端と右端の二つしかない // 最大値はN-1より大きくはならない ans = min(N-1, ans); // 出力 cout << ans << endl; return 0; }
おわりに
解けそうで解けない問題だった。