【AtCoder】ABC 416 B - 1D Akari | 緑コーダーが解くAtCoder

https://atcoder.jp/contests/abc416/tasks/abc416_batcoder.jp

配点: 250 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 56 / NoviSteps: 6Q

問題概要
制約
考察
実装例
コメント

問題概要

., #からなる文字列 $S$ が与えられる。以下の条件を全て満たす文字列 $T$ のうち、oの文字数が最大となるものを一つ求めよ。

$|T| = |S|$
$T$ は., #, oからなる。
$S_i=$ # であるとき、 $T_i=$ #である。
$T_i=T_j=$ o $(i \lt j)$ ならば、 $T_{i+1},\ldots,T_{j-1}$ の中に#が一つ以上存在する。

制約

$1 \leq |S| \leq 100$

考察

$T$ を全て.で置き換えた後、とりあえず $S_i=$ #に対応する場所は#で埋めるしかない。

その上で、oの間には#が必要なので、#の左隣の.をoで置き換えることで、条件を満たしつつoの個数を最大化することができる。

また、 $T$ の先頭が.であれば、それもoで置き換えられることに注意しよう。

実装例

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

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

    rep(i, 0, S.size())
    {
        if (S[i] == '#')
        {
            cout << '#';
        }
        else if (i == 0 || S[i - 1] == '#')
        {
            cout << 'o';
        }
        else
        {
            cout << '.';
        }
    }
    cout << endl;

    return 0;
}