読者です 読者をやめる 読者になる 読者になる

競プロ記録

問題を解いた際に自分の復習用として使ってます

055ABC D問題D - Menagerie

競技プログラミング

問題D - Menagerie

この問題は1番目と2番目を決めてあげれば3番目がSかWかが決定できます。

そこで1番目、2番目を 『S、S』『S、W』『W、S』『W、W』と決めてあげれば与えられた文字列から全体を決定することができます。 そして完成した文字列が与えられた文字列と矛盾していないか最後には判定します。文字列を作成するのにはox文字列の最後から一つ前まで見てあげれば良いです。 したがって矛盾判定を行う箇所はox文字列最後の要素を含んだ3組を判定してあげれば良いです。 具体的には以下の3組ようになります。

n-3 n-2 n-1

n-2 n-1 0

n-1 0 1

これらの3組が全て矛盾していないか判定し、一例を示せば良いです

ソースコードは以下のようになります。

#include <iostream>
#include <string>
using namespace std;

char a[4][100005];
char s[100005];

bool check(int x, int y, int z, int j){
    bool flag = false;
    if(s[y] == 'o'){
        if(a[j][y] == 'S'){
            if(a[j][x] == 'S' && a[j][z] == 'S'){
                flag = true;
            }else if(a[j][x] == 'W' && a[j][z] == 'W'){
                flag = true;
            }
        }else if(a[j][y] == 'W'){
            if(a[j][x] == 'S' && a[j][z] == 'W'){
                flag = true;
            }else if(a[j][x] == 'W' && a[j][z] == 'S'){
                flag = true;
            }
        }
    }else if(s[y] == 'x'){
        if(a[j][y] == 'S'){
            if(a[j][x] == 'S' && a[j][z] == 'W'){
                flag = true;
            }else if(a[j][x] == 'W' && a[j][z] == 'S'){
                flag = true;
            }
        }else if(a[j][y] == 'W'){
            if(a[j][x] == 'S' && a[j][z] == 'S'){
                flag = true;
            }else if(a[j][x] == 'W' && a[j][z] == 'W'){
                flag = true;
            }
        }
    }
    return flag;
}

int main(void){
    long n;
    int cnt = 0;
    bool flag2 = false;
    
    cin >> n;

    for(int i=0;i<n;i++){
        cin >> s[i];
    }

    a[0][0] = 'S';
    a[0][1] = 'S';
    
    a[1][0] = 'S';
    a[1][1] = 'W';
    
    a[2][0] = 'W';
    a[2][1] = 'S';
    
    a[3][0] = 'W';
    a[3][1] = 'W';

    for(int j=0;j<4;j++){
        for(int i=2;i<n;i++){
            if(a[j][i-2] == 'S'){
                if(a[j][i-1] == 'S'){
                    if(s[i-1] == 'o'){
                        a[j][i] = 'S';
                    }else if(s[i-1] == 'x'){
                        a[j][i] = 'W';
                    }
                }else if(a[j][i-1] == 'W'){
                    if(s[i-1] == 'o'){
                        a[j][i] = 'W';
                    }else if(s[i-1] == 'x'){
                        a[j][i] = 'S';
                    }
                }
            }else if(a[j][i-2] == 'W'){
                if(a[j][i-1] == 'S'){
                    if(s[i-1] == 'o'){
                        a[j][i] = 'W';
                    }else if(s[i-1] == 'x'){
                        a[j][i] = 'S';
                    }
                }else if(a[j][i-1] == 'W'){
                    if(s[i-1] == 'o'){
                        a[j][i] = 'S';
                    }else if(s[i-1] == 'x'){
                        a[j][i] = 'W';
                    }
                }
            }
        }
        if(check(n-3,n-2,n-1,j) == true && check(n-2,n-1,0,j) == true && check(n-1,0,1,j) == true){
            for(int i=0;i<n;i++){
                cout << a[j][i];
            }
            cout << endl;
            return 0;
        }
    }
    cout << "-1" << endl;
    return 0;
}