問題概要

円環状に動物 $1, 2, \dots, N$ がこの順に並んでいる。各動物は羊 ('S') か狼 ('W') である。ただし、各動物がいずれであるかが分かっていない。

各動物 $i$ に、両隣の動物が同じ種類かどうかを質問した。

自身が羊であるとき
- 両隣が同じ種類のとき：「はい」と答える
- 両隣が異なる種類のとき：「いいえ」と答える
自身が狼であるとき
- 両隣が同じ種類のとき：「いいえ」と答える
- 両隣が異なる種類のとき：「はい」と答える

各動物の答えが与えられる。各動物がなんであるかを求めよ（複数ある場合はそのうちの 1 つを答え、解なしの場合は -1 を出力する)。

制約

$3 \le N \le 10^{5}$

考えたこと

0-indexed で考える。たとえば動物 $N-1$ と $0$ がそれぞれ狼か羊かを決めると、

動物 1 が種類が決まる
- 動物 0 の種類によって、「両隣が等しいか」に対する回答が真実か嘘かが決まる
- それによって動物 $N-1$ の種類から、動物 1 の種類がきまる
同様に、動物 2 の種類が決まる
同様に、動物 3 の種類が決まる
...
最後に、動物 $N-2$ の種類が決まる

というように、順々に決まっていくのだ。こうして、 $N$ 体の動物が全て決まる。最後に、これが整合しているかを確認する必要がある。動物 $N-3, N-2$ が決まったとき、もともと最初に決めた動物 $N-1, 0$ と整合しない可能性があるからだ。

以上の手続きを、動物 $N-1, 0$ の種類 ( $2^{2} = 4$ 通りある) をすべて試せばよい。計算量は $O(N)$ となる。

コード

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

int main() {
    int N;
    string S, tmp, res = "-1";
    cin >> N >> S;

    auto flip = [&](char c) -> char { return (c == 'S' ? 'W' : 'S'); };
    auto check = [&](char front, char back) -> string {
        string res = string(N, '.');
        res[0] = front, res.back() = back;
        for (int i = 0; i < N; i++) {
            char c;
            if (res[i] == 'S') {
                if (S[i] == 'o') c = res[(i+N-1)%N];
                else c = flip(res[(i+N-1)%N]);
            } else {
                if (S[i] == 'o') c = flip(res[(i+N-1)%N]);
                else c = res[(i+N-1)%N];
            }

            // 整合性 check
            if (res[(i+1)%N] == '.') res[(i+1)%N] = c;
            else if (c != res[(i+1)%N]) return "-1";
        }
        return res;
    };

    if ((tmp = check('S', 'S')) != "-1") res = tmp;
    if ((tmp = check('S', 'W')) != "-1") res = tmp;
    if ((tmp = check('W', 'S')) != "-1") res = tmp;
    if ((tmp = check('W', 'W')) != "-1") res = tmp;
    cout << res << endl;
}