SRM645D1Med ArmyTeleportation
これこそ 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$ 回すると平行移動になる
- 連立方程式が整数解を持つかどうかで判定する
- 今回は全探索でも解けるが…
- 全体としては典型問題の組み合わせだけど面白い方だと思う
