けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 予選 2019 C - マルバツスタンプ (AOJ 0654) (4Q, 難易度 3)

JOI JOI難易度3 JOI予選・二次予選 AtCoder AOJ NoviSteps4Q Greedy Greedy:今が良いほど未来も良い Greedy:どちらも可なら厳しい方 0と1の問題 テク:区間ごとに分割する ランレングス圧縮 Greedy:端から順に決まっていく 探索順序を工夫して解く スタンプ

文字列を左から見ていき、隣接する 2 文字が異なる箇所を見つけるやいなや、マルバツスタンプを使う、という Greedy でよい！

問題概要

マルスタンプ、バツスタンプ、マルバツスタンプの 3 種類がある。

  • マルスタンプを使うと、文字 'O' を印字できる
  • バツスタンプを使うと、文字 'X' を印字できる
  • マルバツスタンプを使うと、文字列 "OX" か "XO" のいずれかを印字できる

JOI 君はスタンプを左から順に印字していって、長さ N の文字列 S を作った。マルバツスタンプを使用した回数として考えられる最大値を求めよ。

制約

  • 1 \le N \le 10^{5}
  • S は文字 'O', 'X' からなる長さ N の文字列

考えたこと：まずは具体例

たとえば S = "OOOXOXXXOX" を考えてみましょう。

この手の問題の定石として、左端から順に決めていくというものがあります。この例において、1 文字目の文字 'O' について、どのスタンプを使用し得るのかを考えてみましょう。

この例では、1 文字目の 'O' の右隣（2 文字目）は文字 'O' ですから、1 文字目をマルバツスタンプによって印字されたということはあり得ないことがわかります。よって、1 文字目の文字 'O' はマルスタンプで押されたということで確定します。

同様に、2 文字目の文字 'O' もマルスタンプで押されたことが確定します。

次に、3 文字目の文字 'O' を考えましょう。今度は右隣（4 文字目）は文字 'X' ですから、3 文字目の 'O' と 4 文字目の 'X' をまとめてマルバツスタンプで "OX" と押した可能性があります！！

ここで、左から順に見ていってマルバツスタンプが使える状況になったら使ってしまって損はないということがいう考察をします！！！！！！　

なぜなら、ここでマルバツスタンプを使うことで、その後マルバツスタンプを使いにくくなるようなことは発生しないからです。よって、3 文字目の 'O' と 4 文字目の 'X' をまとめてマルバツスタンプを押したことにしましょう。

そして、次は 5 文字目について 6 文字目と見比べて......と繰り返していきます。最終的に下図のように、マルバツスタンプを 3 回使ったと求められます。

一般に

以上の具体的な考察を一般化すると、次の方法によって、マルバツスタンプ使用回数の最大値が求められることがわかります（0-indexed で書いています）。

文字列 S を左から順に見ていく。現在見ている文字を i 番目とする。

  • もし S_{i} = S_{i+1} であるならば、文字 S_{i} を印字するのにマルバツスタンプは用いない。このとき、 i を 1 増やす
  • もし S_{i} \neq S_{i+1} であるならば、文字 S_{i} と文字 S_{i+1} をまとめてマルバツスタンプを押す。このとき、 i を 2 増やす

以上の解法の計算量は O(N) となります。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, res = 0;
    string S;
    cin >> N >> S;

    for (int i = 0; i + 1 < N;) {
        if (S[i] != S[i+1]) {
            res++;
            i += 2;
        } else {
            i++;
        }
    }
    cout << res << endl;
}