No.74 貯金箱の退屈

No.74 貯金箱の退屈 - yukicoder

• union find を使った解法。
• 連結成分が確定した後に one の結果を連結成分に適用しないとダメ。(忘れて WA した。)

class BoredomOfSavingsBox {
public:
    void solve(void) {
            int N;
            cin>>N;

            //
            // 同時にひっくり返せるものを一つのグループとして考える。
            //
            // 0,1,1,0,1,...
            //
            // これは適当にコインをひっくりかえすことで
            //
            // A. 1,1,1,...,1,1
            // B. 1,1,1,,..,1,0
            //
            // のどちらかのケースに帰着できる
            // (以下のように反転していけるから
            // 0,1,* -> 1,0,*
            // 0,0,* -> 1,1,*
            // 1,0,1 -> 1,1,0
            // 1,0,0 -> 1,1,1
            // )
            //
            // 一度に二個のコインをひっくり返すので
            // 裏になっているコインの数の偶奇は変化しない。
            // よって初期状態の裏のコインの数が奇数のときは全て表にはできない。
            //
            // ただし1個だけコインをひっくり返せる場合はそれで帳尻があうので全て表にできる。
            //
            UFTree uft(N);
            vector<bool> one(N,false); // 1 個だけコインをひっくり返せるか？
            REP(i,N)
            {
                int d;
                cin>>d;
                int l = (1000*N+i-d)%N;
                int r = (d+i)%N;
                // 同時にひっくり返せるものを統合する
                uft.unite(l,r);
                if (l == r)
                    one[i] = true;
            }
            // 各連結成分での偶奇チェック
            vector<int> num(N,0);
            REP(i,N)
            {
                int w;
                cin>>w;
                num[uft[i]] += (w==0); // 裏になっているコインの数を数える
                // 各 one の結果を連結成分に適用
                if (one[i])
                    one[uft[i]] = true;
            }
            // 各連結成分ごとにチェック
            REP(i,N)
            {
                if (uft[i] != i) // 連結成分ごとにチェック
                    continue;
                if (num[uft[i]]%2 && !one[uft[i]])
                {
                    cout<<"No"<<endl;
                    return;
                }
            }
            cout<<"Yes"<<endl;
    }
};