AtCoder ARC 148 B - dp (1Q, 緑色, 500 点)

辞書順最小と言われたら......！！

• 問題へのリンク

問題概要

文字 'd', 'p' からなる長さ の文字列 が与えられる。

この文字列のある区間をとって、その区間を 180 度回転させる（reverse した上で、'd' と 'p' を入れ替える）。

こうしてできる文字列のうち、辞書順最小のものを求めよ。

制約

• 

考えたこと

辞書順最小のものを求めよ！！と言われたら Greedy！！！

具体的には「後のことは考えずに、前の文字から順に小さくすることに集中する」と考えればよい。

今回の場合も、とにかく「0 文字目を 'd' にできるか」→「1 文字目を 'd' にできるか」→「2 文字目を 'd' にできるか」→ ...... というような思考をすればよい。

まず、もし の 1 文字目が 'd' であった場合、操作する区間が 1 文字目を含む必要はないことがわかる。なぜならば、もし 1 文字目を含む区間に対して操作して辞書順最小になるならば、その区間から 1 文字目を除いた区間に対して操作しても、少なくとも解は悪化しないからだ。

同様にして、 の先頭から見て、初めて 'p' が登場するまでは、それらの 'd' を含む区間は考えなくてよいことがわかる。逆に、初めて 'p' が登場したとき、可能ならばその文字は 'd' にしたい。

よって、結局、「最初の 'p' を左端とする区間」のみを考えればよいことがわかった。そのような区間の個数は であり、各区間に対して調べるのは の計算量でできるので、全体として の計算量で解ける。

コード

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

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

    auto flip = [&](char c) -> char {
        if (c == 'd') return 'p';
        else return 'd';
    };

    string res = S;
    int left = 0;
    while (left < N && S[left] == 'd') left++;
    for (int right = left+1; right <= N; right++) {
        string tmp = S;
        for (int i = left; i < right; i++) {
            tmp[i] = flip(S[left + right - 1 - i]);
        }
        res = min(res, tmp);
    }
    cout << res << endl;
}