The 46th World Championship ICPC Y問題：Compression

問題. Compression

0 と 1 からなる非空な文字列 が与えられる。 の連続する 2 つの同じ連続部分列に対して 1 つの連続部分列を取り除く操作を再帰的に繰り返していく。最終的に得られる文字列の中で長さ最小のものを答えよ。

制約：

解法.

0 のみからなる連続部分列に対して操作を行うと 0 の一文字に圧縮される。1 のみからなる連続部分列も同様である。したがって、同じ文字が連続する連続部分列は 1 文字に圧縮できるので、そのような操作を可能な限り行った後の文字列を考える。そのような文字列は、1 と 0 が交互に現れる文字列か 0 と 1 が交互に現れる文字列となる。そのような文字列にさらに操作を行うと最終的に次のような結果が得られる。

・1 → 1
・0 → 0
・1010...10 → 10
・0101...01 → 01
・1010...101 → 101
・0101...010 → 010

この結果が長さに関して最小であることは、101 や 010 となる元の文字列がどのようにしても 1, 0, 10, 01 にならないこと、10 や 01 となる元の文字列がどのようにしても 1 や 0 にならないことから分かる。
例えば、(11...100...0)(11...100...0)...(11...100...0)11...1 は 10 とならない。なぜなら、10 に対して連続部分列を任意に選びそれを前後どこかに加える逆操作を任意回行っても末尾を 1 にすることができない。

計算時間：

ソースコードを表示

#include <iostream>

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

    std::string d;
    d.push_back(s.front());
    for (size_t i = 1; i < s.size(); ++i) {
        if (d.back() == s[i]) continue;
        d.push_back(s[i]);
    }

    if (d.size() == 1) {
        std::cout << d.front() << std::endl;
    }
    else if (d.front() == d.back()) {
        std::cout << d.substr(0, 2) + d.back() << std::endl;
    }
    else {
        std::cout << d.substr(0, 2) << std::endl;
    }

    return 0;
}

　

一番解かれていた問題。問題文の前半では文字集合がアルファベットだったので気構えてしまった。