外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

I - Another 1122 Problem

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 350 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

この問題で行える操作は、連続部分文字列 1122 を 2222 に置き換えることです。 この操作について、次の性質が成り立ちます。

可能な限り操作を行ったとき、最終結果は操作の順番と関係がない

  • ある時点で文字列の中に存在する 1122 同士が重なり合うことはありません。また、操作によって変化するのは 1 →\to 2 のみであり、すでにある別の 1122 の 1 を変化させることもありません。したがって、ある場所で操作をしたせいで、別の場所でできたはずの操作ができなくなることは起きません。
  1. 単調である: 1 が 2 に変わるだけであり、2 が 1 に戻ることはありません。

これらより、どの順番で操作を行ってもこれ以上操作できる場所がなくなるまで繰り返した最終状態は一意に定まり、その最終状態において 2 の連続部分文字列の長さも最大化されます。

後ろから 11 文字ずつ見る解法

操作 1122 →\to 2222 は、「22 つ以上連続した 2 の左側に 11 が隣接していれば、それを 22 に変えて左へ伸ばす」操作と見ることができます。

文字列を左から順に見ていくと、右側の文字を追加したことで左方向へ連鎖的に操作が可能になる場合(例:111122 →\to 112222 →\to 222222)があり、後ろに戻って確認する必要が出てきます。

そこで、文字列 SS を右から左に向かって 11 文字ずつ見ていくことを考えます。

右側の部分文字列に対して可能な限りの操作をすべて終えた文字列 TT があるとします(つまり TT には 1122 が含まれていません)。この TT の左端に 11 文字 cc を付け加えたとき、次のどちらかになります。

  • c=’2’c = \text{'2'} の場合: 新たに作られる長さ 44 の部分文字列は先頭から始まるものだけですが、先頭が 2 であるため 1122 にはなり得ません。よって操作は発生しません。
  • c=’1’c = \text{'1'} の場合: 新たに作られる長さ 44 先頭 44 文字が 1122 であれば、2222 に置き換えます。 置き換えた後の先頭 44 文字はすべて 2 になるため、この置換によってさらに新たな 1122 が生まれることはありません。

この性質により、後ろから 11 文字ずつ追加するたびに先頭 44 文字が高々 11 回 1122 になるかを確認するだけで、操作をこれ以上行えない状態を求めることができます。

3. 実装のポイント

プログラム上で先頭への文字の挿入や書き換えを行うよりも、配列や文字列の末尾に追加していく方が高速で実装が簡単です。 SS を後ろから走査して新しい文字列 TT の末尾に追加していく(つまり反転した状態で構築する)と、元の文字列での 1122 は TT 上では 2211 に対応します。

  1. SS を末尾から 11 文字ずつ読み、文字列(または配列) TT の末尾に追加する。
  2. TT の長さが 44 以上で、末尾 44 文字が 2211 ならば、末尾 22 文字を 22 に書き換える。
  3. 最終的な TT に含まれる 2 の連続長の最大値を数えて出力する。

この解法の時間計算量は O(∣S∣)O(|S|) であり、これは十分高速です。

実装例

C++

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

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

    string T = "";
    for (int i = (int)S.size() - 1; i >= 0; --i) {
        T.push_back(S[i]);
        int len = T.size();
        if (len >= 4 && T[len - 4] == '2' && T[len - 3] == '2' &&
            T[len - 2] == '1' && T[len - 1] == '1') {
            T[len - 2] = '2';
            T[len - 1] = '2';
        }
    }

    int ans = 0, cur = 0;
    for (char c : T) {
        if (c == '2') {
            cur++;
            ans = max(ans, cur);
        } else {
            cur = 0;
        }
    }

    cout << ans << "\n";
    return 0;
}

Python

S = input().strip()

T = []
for c in reversed(S):
    T.append(c)
    if len(T) >= 4 and T[-4:] == ['2', '2', '1', '1']:
        T[-2] = '2'
        T[-1] = '2'

ans = 0
cur = 0
for c in T:
    if c == '2':
        cur += 1
        if cur > ans:
            ans = cur
    else:
        cur = 0

print(ans)

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。