SRM 538 Div2 Medium EvenRoute

問題

2次元座標上の複数の点が与えられ(0, 0)から全ての点を通る経路を考える.x, y座標を1移動する操作を1ステップとすると,全ての点を通るある経路のステップ数が偶数かどうかパリティビットを与えられる.そのようなパリティビットを満たす経路が存在するのかを判定する

解答

問題の性質

  1. (0, 0)から(x, y)に移動するステップ数はabs(x) + abs(y).
  2. 上記のステップ数が偶数なら偶数の点,奇数なら奇数の点と呼ぶと,偶数点と奇数の点間を移動する時のみステップ数の偶奇が入れ替わる
  3. 上記は全体のステップ数の偶奇は最終到着点の偶奇によって決まり,それまでの経路は関係ない.(0, 0)から任意の全ての点を通り(0, 0)に戻ってくる経路を考えると,どの経路を通っても全体のステップの偶奇は変わらない.その循環経路の中のどの辺を削除するかで偶奇が決まる)

この条件から奇数の点,偶数の点が少なくとも一つあれば必ずどちらのパリティビットを満たす経路が存在する.また,偶数の点のみならばパリティビットは必ず0, 奇数の点のみならばパリティビットは必ず1となることが言える.

class EvenRoute
{
public:
  string isItPossible(vector <int> x, vector <int> y, int wantedParity)
    {
      int n = x.size();
      int i;
      int nodd = 0;
      int neve = 0;
      for(i = 0; i < n; i++){
        if ((abs(x[i]) + abs(y[i])) % 2 == 1) nodd++;
        else neve++;
      }
      if (wantedParity == 0 && nodd == 0) return "CAN";
      if (wantedParity == 1 && neve == 0) return "CAN";
      if (nodd > 0 && neve > 0) return "CAN";
      return "CANNOT";
    }
};