ABC-055-D Menagerie

■■■問題■■■

すぬけくんは動物が好きなので動物園を作りました。

この動物園では 1,2,3, ・・・ ,N の番号を割り振られたN匹の動物が円環状に並べられています。
i(2 <= i <= N-1) 番の動物は i-1 番の動物と i+1 番の動物と隣り合っています。
また、1番の動物はN番の動物と2番の動物と隣り合っており、
N番の動物は N-1 番の動物と1番の動物と隣り合っています。

動物園には本当のことしか言わない正直者の羊と、嘘しか言わない嘘つきの狼の2種類の動物がいます。

すぬけくんには羊と狼の区別がつかないので、
それぞれの動物に両隣の動物が同じ種類かどうかを訪ねたところ、
i番目の動物はsiと答えました。
siがoならば両隣の動物が同じ種類であると、xならば異なる種類であるとi番の動物が言ったことを示します。

より形式的には、羊は両隣の動物がどちらも羊あるいはどちらも狼のときoと答え、そうでないときxと答えます。
狼は両隣の動物がどちらも羊あるいはどちらも狼のときxと答え、そうでないときoと答えます。

これらの回答結果と矛盾しないような各動物の種別の割り当てが存在するか、すぬけくんは気になっています。
存在するならば一例を示し、存在しないならば-1を出力しなさい。

■■■入力■■■

N
s

●3 <= N <= 10万
●sはoとxのみからなる長さNの文字列

■■■出力■■■

sと矛盾しないような各動物の種類の割当てが存在しないならば-1を出力してください。
存在するならば以下の形式で文字列tを出力してください。
tで示される割り当てがsと矛盾しないならば正解となります。

●tは長さNでSとWのみからなる文字列
●tiがSならばi番の動物が羊であることを、Wならば狼であることを示す

■■■サンプルケースのイメージ■■■

■入出力例1のイメージ■

例えば 1,2,3,4,5,6 番の動物がそれぞれ羊、羊、羊、狼、狼、羊であるとき発言と矛盾しません。
その他、狼、羊、狼、羊、狼、狼であるようなときも矛盾しません。

両隣が同じ種類の動物のとき羊はoと発言し、狼はxと発言すること、
両隣が異なる種類の動物のとき羊はxと発言し、狼はoと発言することに注意してください。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("6");
            WillReturn.Add("ooxoox");
            //SSSWWS
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("oox");
            //-1
            //存在しない場合は-1を出力してください
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("oxooxoxoox");
            //SSWWSSSWWS
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static string s;
    static int N;

    static void Main()
    {
        List<string> InputList = GetInputList();
        N = int.Parse(InputList[0]);
        s = InputList[1];

        string Wariate1 = DeriveWariate("SS");
        string Wariate2 = DeriveWariate("SW");
        string Wariate3 = DeriveWariate("WS");
        string Wariate4 = DeriveWariate("WW");

        if (Wariate1 != "-1") { Console.WriteLine(Wariate1); return; }
        if (Wariate2 != "-1") { Console.WriteLine(Wariate2); return; }
        if (Wariate3 != "-1") { Console.WriteLine(Wariate3); return; }
        if (Wariate4 != "-1") { Console.WriteLine(Wariate4); return; }
        Console.WriteLine(-1);
    }

    //最初の2匹を引数として、各動物の割り当てを返す
    static string DeriveWariate(string pSaisyo2)
    {
        int UB = N - 1;
        char[] WariateArr = new char[UB + 1];
        WariateArr[0] = pSaisyo2[0];
        WariateArr[1] = pSaisyo2[1];

        for (int I = 1; I <= UB - 1; I++) {
            char Prev = WariateArr[I - 1];
            char Curr = WariateArr[I];
            char Hatugen = s[I];

            char NextAnimal = DeriveNextAnimal(Prev, Curr, Hatugen);
            WariateArr[I + 1] = NextAnimal;
        }

        //最初の2匹が矛盾していないかチェック
        if (WariateArr[0] !=
            DeriveNextAnimal(WariateArr[UB - 1], WariateArr[UB], s[UB])) {
            return "-1";
        }
        if (WariateArr[1] !=
            DeriveNextAnimal(WariateArr[UB], WariateArr[0], s[0])) {
            return "-1";
        }
        return new string(WariateArr);
    }

    //前とカレントの動物と、カレントの動物の発言を引数として、カレントの次の動物を返す
    static char DeriveNextAnimal(char pPrev, char pCurr, char pHatugen)
    {
        if (pPrev == 'S' && pCurr == 'S') {
            if (pHatugen == 'o') return 'S';
            if (pHatugen == 'x') return 'W';
        }
        if (pPrev == 'S' && pCurr == 'W') {
            if (pHatugen == 'o') return 'W';
            if (pHatugen == 'x') return 'S';
        }
        if (pPrev == 'W' && pCurr == 'S') {
            if (pHatugen == 'o') return 'W';
            if (pHatugen == 'x') return 'S';
        }
        if (pPrev == 'W' && pCurr == 'W') {
            if (pHatugen == 'o') return 'S';
            if (pHatugen == 'x') return 'W';
        }
        return '\0';
    }
}

解説

最初の2匹を決めると、残りは連鎖的に決まることを使ってます。
最初の2匹は4通りしかないので、TLEになりません。