SRM645D1Med ArmyTeleportation

• July 15, 2016
• TopCoder, Interesting

これこそ 600ptsだと思う

問題概要(原文)

二次元平面上の格子点に置かれた $N$ 個の区別できない石を，別の $N$ 箇所に移動させたい． 可能な操作は $(xt_i,yt_i)(1 \leq i \leq 3)$ に対称な点に移動させるのみ． 可能かどうか判定せよ．

考察

$2$ 回の操作を行うと $(2(xt_j-xt_i),2(yt_j-yt_i))$ だけ平行移動できる．さらに，平行移動は $3$ 種類ありそうに見えるが， $1$ つは他のベクトルの合成で表せるので不要．つまりこの問題はこう言い換えられる．

• $0$ 回，または $1$ 回の対称移動と， $2$ 種類の平行移動を任意回繰り返して，目標の位置に移動させることは可能か？

さて，$1$ 回の対称移動は簡単にできる．全体を並行移動させて一致するかどうかの判定は $x$ 座標についてソートして調べればよい． 最後は $p \times vx_1 + q \times vx_2 = dx, p \times vy_1+ q \times vy_2 = dy$ を満たす，整数 $p,q$ があるか判定する問題が解ければよい．

幸い，$|dx|,|dy| \leq 10^7$ なので， $p$ について全探索できる．

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class ArmyTeleportation
{
    public string ifPossible(int[] x1, int[] y1, int[] x2, int[] y2, int[] xt, int[] yt)
    {
        return f(x1, y1, x2, y2, xt, yt) ? "possible" : "impossible";
    }
    bool f(int[] x1, int[] y1, int[] x2, int[] y2, int[] xt, int[] yt)
    {
        var n = x1.Length;
        var vx = new List<int>();
        var vy = new List<int>();
        for (int i = 0; i < 2; i++)
        {
            vx.Add(2 * (xt[2] - xt[i]));
            vy.Add(2 * (yt[2] - yt[i]));
        }
        for (int i = 0; i < vx.Count; i++)
            Debug.WriteLine("{0} {1}", vx[i], vy[i]);
        if (g(x1, x2, y1, y2, vx, vy)) return true;
        for (int i = 0; i < 3; i++)
        {
            var X = x1.ToArray();
            var Y = y1.ToArray();
            for (int j = 0; j < n; j++)
            {
                X[j] = 2 * xt[i] - x1[j];
                Y[j] = 2 * yt[i] - y1[j];
            }
            if (g(X, x2, Y, y2, vx, vy)) return true;
        }


        return false;
    }
    bool g(int[] x1, int[] x2, int[] y1, int[] y2, List<int> vx, List<int> vy)
    {
        int n = x1.Length;
        Array.Sort(x1, y1);
        Array.Sort(x2, y2);
        var dx = x2[0] - x1[0];
        var dy = y2[0] - y1[0];
        for (int j = 0; j < n; j++)
        {
            if (dx != x2[j] - x1[j])
                return false;
            if (dy != y2[j] - y1[j])
                return false;
        }
        Debug.WriteLine("{0} {1}", dx, dy);
        for (long i = -5000000; i < 5000000; i++)
        {
            var u = dx + i * vx[0];
            var v = dy + i * vy[0];
            if (u != 0 && vx[1] == 0) continue;
            if (v != 0 && vy[1] == 0) continue;
            if (vx[1] == 0) return v % vy[1] == 0;
            if (vy[1] == 0) return u % vx[1] == 0;
            if (u % vx[1] != 0) continue;
            if (v % vy[1] != 0) continue;
            if (u / vx[1] == v / vy[1]) return true;
        }
        return false;
    }
}

コメント

• 対称移動を $2$ 回すると平行移動になる
• 連立方程式が整数解を持つかどうかで判定する
• 今回は全探索でも解けるが…
• 全体としては典型問題の組み合わせだけど面白い方だと思う

• math
• geometry
• sorting
• brute force

• Twitter