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

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

AtCoder ABC 283 C - Cash Register (5Q, 灰色, 300 点)

AtCoder AtCoder300点 ABC-C 灰色diff ランレングス圧縮 for文:前回求めた値を活用する for文:ある状態がどこまで続くかを求める for文 テク:区間ごとに分割する 文字列 最適化問題 最小回数・最小個数を求める 最小コスト スタンプ

「0 が連続何個続くのか」を求めるタイプの問題

問題概要

数字からなる長さ N の文字列 S が与えられる。

「1」「2」「3」「4」「5」「6」「7」「8」「9」「0」「00」と書かれた文字列スタンプを順に押して行って、 S を作りたい。

スタンプを押す回数の最小値を求めよ。

制約

  • 1 \le N \le 10^{5}

考えたこと

文字列 S のうち、0 以外の数字が登場したら、それに対応するスタンプを押すしかない。

工夫のしどころは「0 が連続する区間」だ。たとえば、

S = "7500000470000"

のとき、7 と 5 と 4 と 7 は 1 回ずつ押すしかないが、

  • "00000" は「00」「00」「0」の 3 回
  • "0000" は「00」「00」の 2 回

で押せることに注意しよう。一般に、「0 が連続している区間」については、基本的に 2 個ずつ「00」で押して行って、余ったところは 1 個の「0」で押せば良いことがわかる。

残る問題は、各「0 が連続する区間」の長さを求めることだ。これは、次のように求められる。

  • 文字列 S を左から順にみていき、
  • 0 が登場したら、その瞬間の添字を記録しておいて、0 が途切れるところまで見ていき、何個見たかを求める

結局、for 文を 1 回回すことで問題が解けるので、計算量は O(N) となる。

コード

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

int main() {
    string S;
    cin >> S;

    int res = 0, prev = -1;
    for (int i = 0; i < S.size();) {
        if (S[i] == '0') {
            int j = i;

            // 0 が途切れるまで進める
            while (j < S.size() && S[j] == '0') j++;
            res += (j - i + 1) / 2;
            i = j;
        }  else {
            res++;
            i++;
        }
    }
    cout << res << endl;
}