hogecoder

tsutaj 競技プログラミングの記録

Codeforces Round #581 Div. 2 D: Kirk and a Binary String

問題概要

原文 → Problem - D2 - Codeforces

0 と 1 のみからなる長さ  N の文字列  S が与えられる。 S の文字を、以下の条件が満たされた上で変更することを考える。

  • 全ての  1 \leq l \leq r \leq N に対して、 S l 文字目から  r 文字目までのみからできる最長単調非減少列の大きさが元の文字列と変わらない

変更後の文字列であって、0 を最も多く含むものを求めよ。

解説

まず、"10" という文字列について変更不可能であることがわかる。ここから考察を進めていこう。

"10" という文字列は 1 と 0 を 1 文字ずつ含んでいるが、"10" を通過する直前の部分列が最後にどの文字を使ったかによって場合分けする。

  • 部分列が最後に "0" を使用していた場合、つまり "....0xxx10" (x は選択していない文字) のような状況であった場合、それに "10" の 0 を続けるか 1 を続けるか 2 通りの選択ができる
  • 部分列が最後に "1" を使用していた場合、つまり "...1xxx10" のような状況であった場合、それに "10" の 1 を続けることができる

最後に使用した文字に続きうる文字のうち、どれか 1 つを "10" から使用することができることがわかるであろう。言い換えれば、「"10" を通過するときは必ずどれか 1 文字をその中から使っていて、適切に選択すれば最長単調非減少列の大きさに影響しない」ということにもなるため、このようなパターンは元々なかったものとして (削除して) 構わない。

文字列から "10" というパターンを左から順に消していくと、最終的にできる文字列は "0000...0111.....1" のように左が 0 で右が 1 となる文字列である。この文字列に関しては全て "0" に変更してしまっても最長単調非減少列の大きさは変わらない。

ゆえに、stack などを用いて高速に解くことができる。

ソースコード

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

    vector<bool> checked(s.size());
    stack< pair<char, int> > st;
    for(size_t i=0; i<s.size(); i++) {
        if(st.empty() or st.top().first == s[i] or st.top().first == '0') {
            st.emplace(s[i], i);
        }
        else {
            checked[i] = checked[st.top().second] = true;
            st.pop();
        }
    }

    for(size_t i=0; i<s.size(); i++) {
        if(!checked[i]) s[i] = '0';
    }
    cout << s << endl;
    return 0;
}

"10" が変わらないのは思いついたけど、その後が全然ダメだった。難しい・・・