SRM538 Div.1 Easy(250) EvenRoute

気づけばとても簡単な問題。

問題

TopCoder Statistics - Problem Statement

いくつかの格子点が与えられる。原点からスタートし、与えられたすべての格子点を1度以上通り、与えられた格子点のどこかで終了するパスを考える。このようなパスのうち、長さの偶奇がwantedParityであるようなものが存在するか答えよ。

解法

まず、ある点p1からp2への移動を考えると、p1からp2までのパスの長さのパリティは、p1からp2までをどのように通ってもp1, p2間のマンハッタン距離の偶奇に等しい。この「どのように通っても」というのがミソ。この問題の場合、最後の頂点さえ決まれば他の頂点をどのようにたどってきたとしてもパスの偶奇は決まってしまう。よって原点と与えられた各点とのマンハッタン距離の偶奇を調べ、1つでもwantedParityに一致するものがあればYES、そうでなければNOとすればよい。

class EvenRoute {
    public:
    string isItPossible(vector<int> x, vector<int> y, int w) {
        int N = x.size();
        rep(i, N) {
            if ((abs(x[i]) + abs(y[i])) % 2 == w) return "CAN";
        }
        return "CANNOT";
    }
};

余談

本番は上の解法に確信が持てなかったので、dpで適当に1000回くらいループを回した。一応そのコードも載せておく(実際は最初だけ見ればいいのでやっていることは完全にムダ)

各頂点ごとに、そこまでのパスの偶奇それぞれがありうるかをboolでDPした。

class EvenRoute {
    public:
    string isItPossible(vector<int> x, vector<int> y, int w) {
        int N = x.size();
        vector<vector<bool>> dp1(N, vector<bool>(2, false)), dp2(N, vector<bool>(2, false));
        rep(i, N) {
            dp1[i][(abs(x[i]) + abs(y[i])) % 2] = true;
        }

        rep(t, 1000) {
            rep(i, N) {
                rep(j, N) {
                    if (i == j) continue;
                    rep(k, 2) {
                        if (!dp1[i][k]) continue;
                        dp2[j][(k + abs(x[i] - x[j]) + abs(y[i] - y[j])) % 2] = true;
                    }
                }
            }
            swap(dp1, dp2);
        }

        rep(i, N) {
            if (dp1[i][w]) return "CAN";
        }

        return "CANNOT";
    }
};