AtCoder Regular Contest 014 の C 問題

古い ARC は難易度が読めなくて、ワクワク感がある反面、練習には微妙かもしれない。

この問題はとても面白かったので解説したくなった。

概要

赤、緑、青のボールが ${N}$ 個並んでいる。これを、順番に両端が開いた筒の中に入れていく。
右から入れても左から入れてもいいが、同じ色のボールが接触すると消滅する。
上手く筒の中のボールの数が少なくなるように入れていった場合、最後には何個のボールが筒の中に残っているか。

${1\leq N\leq50}$

考えたこと

${N}$ がとても小さい。
なので、その辺りを工夫してどうにかできないかなぁ、と最初は考えた。
のだけど、色々試しているうちに何となく思えてくることがあった。

「あれ、これって上手くやれば偶数個までなら消せるのでは？」

というわけで、これを証明（？）してみた。

証明っぽいもの

筒の中に何個ボールが残っているか、何色のボールが入ってくるか、で場合分けをする。
ここで、筒の中のボールの色を固定しても一般性を失わないような気がするので、それで説明していく。

筒の中のボールが【】の時、赤色のボールを入れる

右から入れても左から入れても同じ。
筒の中には赤色のボールが1個残る。

筒の中のボールが【赤】の時、赤色のボールを入れる

同じ色なのでボールは消滅する。
筒の中のボールは無くなる。

筒の中のボールが【赤】の時、緑色のボールを入れる

この場合も、右から入れても左から入れても同じ。
何故なら、これ以降の処理を全て左右逆にすることで、反対側の操作と全く同じ結果になるから。

筒の中には赤、緑2個のボールが残る。

筒の中のボールが【赤緑】の時、赤色/緑色のボールを入れる

同じ色なので、ボールを消すことができる。
（天下り的かもしれないが）【赤緑赤】のように、敢えて消滅させない入れ方は考えない。

筒の中のボールが【赤緑】の時、青色のボールを入れる

筒の中のボールは3個になる。
この時、あり得る形は【赤緑青】か【青赤緑】かのどちらで、これは「左右を操作することで、真ん中に来る色を選ぶことができる」という意味。

さて、ここまで考えると、筒の中にボールが3個の時というのは、必ず3色のボールが残っているということがわかる。

筒の中のボールが【赤緑青】の時、赤色/青色のボールを入れる

ボールは消滅し、筒の中には2個のボールが残る。

筒の中のボールが【赤緑青】の時、緑色のボールを入れる

この場合は、緑色のボールを消すことはできず、筒の中のボールは4個になる。

が、筒の中のボールが2個の時に述べたように、3つ並んだボールの真ん中の色は選ぶことができる。
そして問題の条件から、 ${i}$ 番目のボールの左右を決める段階で、 ${i+1}$ 番目のボールが何色かは判然としている。
つまり、筒の中にボールが3個になる時、その次のボールを消すような入れ方にしておくことは必ず可能となるわけだ。

よって、上の場合分けから、「筒の中に入っているボールはどのタイミングでも高々3個」にできるし、「その色は全て異なる」ことが言える。
言い換えると、「ある色のボールを筒に入れる時、もし筒の中に同じ色のボールが既にあるのなら、その2つのボールは消滅する」

さて、与えられた ${N}$ 個のボールのうち、赤色が ${R}$ 個だったとする。
${R}$ が偶数なら、上で述べた手順で全てのボールを消滅させることができる。
${R}$ が奇数の場合は、最終的に筒の中に1個の赤ボールが残ることとなる（1個だけだと消滅させることはできないので）。そして、赤色のボールをこれ以下の個数にすることはできない。

これらのことは、緑も青も同じに言える。

以上から、この問題は「赤、緑、青色のボールをそれぞれ数えて、奇数の色の数」が答えになることがわかる。

実装

import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.bigint;

void main()
{
    readln;
    auto S = readln.chomp.to!(char[]);
    int r, g, b;
    foreach (c; S) {
        switch (c) {
            case 'R':
                ++r;
                break;
            case 'G':
                ++g;
                break;
            case 'B':
                ++b;
                break;
            default:
        }
    }
    writeln(r%2 + g%2 + b%2);
}

感想

考えるのが楽しい問題だった。

意図したかどうかはわからないが、 ${1\leq N\leq50}$ という制約はちょっと意地が悪いなぁと思ったり。
${N}$ の最大が ${50}$ の条件で、まさか ${O(N)}$ で解けるとは瞬時には考えないような気がする。
（勿論、制約から解法を見繕うみたいなことをするのが悪いのだけど。）