SRM 538 div1 easy: EvenRoute
解法
実はめっちゃ簡単です。
「(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"; } };