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

mayoko’s diary

プロコンとかいろいろ。

SRM 538 div1 easy: EvenRoute

TopCoder
解法

実はめっちゃ簡単です。
「(0, 0) からの距離が wantedParity と一致する点が一つでもあれば YES, そうでなければ NO」と言えます。なぜかというと,

  • 一致する点が一つでもある場合, (0, 0) から頂点に訪れる -> (0, 0) に戻る, を繰り返すと常に operate 数は偶数です。で, 最後に wantedParity と一致する頂点に行くようにすれば解決ですね。
  • 一致する点がひとつもない場合, (0, 0) 以外のすべての頂点同士の距離は偶数です。よって, どのように頂点を移動しても (0, 0) 以外に行った時の parity が変化しないので無理です。
class EvenRoute {
public:
    string isItPossible(vector <int> x, vector <int> y, int wantedParity) {
        int flag = 0;
        int n = x.size();
        for (int i = 0; i < n; i++) {
            int d = abs(x[i]) + abs(y[i]);
            d %= 2;
            flag |= 1<<d;
        }
        if (flag>>wantedParity&1) return "CAN";
        else return "CANNOT";
    }
};