こういうの楽しいよね！

問題へのリンク

問題概要

$N$ 個のマスが横一列に並んでいます。各マスは赤、青、黄、緑のいずれか 1 色で塗られている ("RBYG" からなる長さ $N$ の文字列 $S$ で与えられる)。

以下の操作を好きな順序で好きな回数だけ行えます。文字列 $T$ を作ることが可能かどうかを判定せよ。

異なる色で塗られた隣接 2 マスを選ぶ
その 2 マスをどちらにも用いられていない 2 色で 1 つずつ塗る

制約

$2 \le N \le 10^{6}$

考えたこと

この手の問題は不変量を導きたくなるところ。とりあえず各色を 0, 1, 2, 3 に対応させて考えることにしよう。一瞬、mod とかを考えたくなるけど、それだとあまりうまくいかない。たとえば mod 4 で不変なのかと思いたくなるけど、

(0, 1) と (2, 3)
(0, 2) と (1, 3)
(0, 3) と (1, 2)

のうち、真ん中のやつは mod 4 だと上手くいかない。

XOR

そこで、

0 ^ 1 ^ 2 ^ 3 = 0

であることに着目しよう。そうすると、

0 ^ 1 = 2 ^ 3
0 ^ 2 = 1 ^ 3
0 ^ 3 = 1 ^ 2

であることがいえる！！！！！つまり、全体の XOR 和は不変なのだ。S と T とで XOR 和が等しいことが必要条件となる。しかしこれだけでは不十分で、

S != T
S がすべて同色
T がすべて同色

という場合はどうしようもない ( $N = 1$ はケースにない)。逆にそうでなければできる。一応そのことを証明してみる。

数学的帰納法

この手の証明は数学的帰納法というイメージがある。まず、 $N = 2$ のとき、XOR が等しい全パターン作れることはいえる。とくに、

(0, 1) → (2, 3) → (1, 0)

というように、媒介することで swap ができることに注意しておく。 $N = 3$ の場合も大丈夫そう。

それでは、 $N \ge 4$ で $S, T$ がともに全部同色ではないとき、互いに移れることを数学的帰納法によって示そう。まず前提として今回の操作は逆操作が可能なので、あらかじめ $S$ や $T$ に都合よく操作してしまってかまわない。全部同色でない文字列は、どの隣接する 2 文字も異なるようにできることに注意します。よって次のようにして $S, T$ を一致させることができます。

S や T をあらかじめ、どの隣接する 2 文字も異なるような状態にしておきます
S の先頭の 2 文字に対して操作を行うことで、S[0] == T[0] となるようにします
このとき、S, T の後半 N-1 文字中は「全部同色」という状態ではないので、帰納法の仮定から、互いに一致させることができます

まとめ

S == T なら Yes
S または T が「全部同色」なら No
S の XOR 和 != T の XOR 和なら No
それ以外は Yes

計算量は $O(N)$ 。

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

int conv(char c) {
    if (c == 'R') return 0;
    else if (c == 'B') return 1;
    else if (c == 'Y') return 2;
    else return 3;
}

bool solve(string S, string T) {
    if (S == T) return true;
    int sx = 0, sy = 0;
    set<int> ss, st;
    for (auto c : S) ss.insert(c), sx ^= conv(c);
    for (auto c : T) st.insert(c), sy ^= conv(c);
    if (ss.size() == 1 || st.size() == 1) return false;
    return sx == sy;
}

int main() {
    int N;
    string S, T;
    cin >> N >> S >> T;
    if (solve(S, T)) cout << "Yes" << endl;
    else cout << "No" << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 3177 Painting (HUPC 2020 day3-F)

問題概要

制約

考えたこと

XOR

数学的帰納法

まとめ