隠されていたゲーム2 [yukicoder No.602] - はまやんはまやんはまやん

解法

解くときに使った、もう少し強いサンプルを先に載せておきます。

答え

0回で移動可能な場合は「x=y=0」である。
1回で移動可能なのは、(0,0)と(x,y)のマンハッタン距離がd1～dnにある場合である。
　
問題が2回で移動可能な場合だが、典型を使おう。
「マンハッタン距離を使う問題は45度回転をする
X = X+Y, Y = X-Yのように変換をして、absをとったものをdx,dyとする。
すると問題が、以下のように変わる。
「(0,0)と(dx,dy)からそれぞれ半径をd1～dnで適切に選んで交わるものがあるか」
正方形で交わるかどうかなのでma=max(dx, dy)だけが関係してくる。
一番簡単そうな条件を考えると、d[i]≦ma/2を満たすd[i]があれば交わることができそう。
(0,0)と(dx,dy)のそれぞれで半径d[i]の正方形を作ると、必ず交わる。
が、これで出すとWA
　
サンプルを作りながら反例を考えていく。
と、同じd[i]を2回使って移動すると、(0,0)からのマンハッタン距離は偶数である地点しか移動できない。
つまり、(X,Y)へのマンハッタン距離が奇数の場合は、2つのdは奇数と偶数のペアである必要がある。
なので、X+Yが奇数の場合は処理を分ける。
　
odd := 奇数のdの集合
を使って、偶数のdを全探索して、交わりそうな奇数のdを試す。
交わりそうな奇数のdはabs(ma-d[i])に最も近い奇数のdである。
これはlower_boundを使えば、境界周りの要素が手に入る。
これでチェックしよう。
check(d1, d2, ma) := 半径がd1とd2の正方形を(0,0)とma=max(dx,dy)を満たす(dx,dy)においたときに交わるか
交わらない条件をチェックすることでこの関数は解決する。
a=min(d1,d2), b=max(d1,d2)とすると、

a+ma
a+b

が交わらない条件となる。
　
条件を全て満たさないなら-1

int N, D[101010], X, Y;
//---------------------------------------------------------------------------------------------------
int check(int d1, int d2, int ma) {
    int a = min(d1, d2);
    int b = max(d1, d2);

    if (a + ma < b) return 0;
    if (a + b < ma) return 0;
    return 1;
}
//---------------------------------------------------------------------------------------------------
int solve() {
    if (X == 0 and Y == 0) return 0;
    rep(i, 0, N) if (D[i] == abs(X) + abs(Y)) return 1;

    int dx = abs(X + Y);
    int dy = abs(X - Y);
    int ma = max(dx, dy);

    if ((X + Y) % 2 == 0) {
        rep(i, 0, N) if (ma <= D[i] * 2) return 2;
    } else {
        vector<int> odd;
        rep(i, 0, N) if (D[i] % 2 == 1) odd.push_back(D[i]);
        sort(all(odd));
        rep(i, 0, N) if(D[i] % 2 == 0) {
            int j = lower_bound(all(odd), abs(ma - D[i])) - odd.begin();
            if (j < odd.size() and check(D[i], odd[j], ma)) return 2;
            if (0 <= j - 1 and check(D[i], odd[j - 1], ma)) return 2;
        }
    }

    return -1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    while (cin >> N) {
        rep(i, 0, N) cin >> D[i];
        cin >> X >> Y;

        cout << solve() << endl;
    }
}