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;
}
おわりに
解けそうで解けない問題だった。
