Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 272 D問題 Root M Leaper

AtCoder ABC272 ABC D問題 400 pts

B# 問題 atcoder.jp

提出解答

問題の概要

$N$ 行 $N$ 列のマス目がある. 上から $i$ 行目, 左から $j$ 列目のマスのことを $(i,j)$ と書く.

最初, マス $(1,1)$ のみに駒がある.

各 $1 \leq i,j \leq N$ を満たす整数の組 $(i,j)$ について, 以下の問に答えよ.

次の操作を回以上行い, 駒をマスにある状態にすることは可能か? 可能ならばその操作回数の最小値を求めよ.
- マス $(i,j)$ に駒があるとする. $\sqrt{(i-k)^2+(j-l)^2}=\sqrt{M}, 1 \leq k,l \leq N$ を満たす整数の組 $k,l$ を選び, 駒をマス $(k,l)$ に移動させる.

制約

$2 \leq N \leq 400$
$1 \leq M \leq 10^6$

解法

駒をマス $(i,j)$ からマス $(k,l)$ に移動させることが可能かどうかは各座標の差の組 $(k-i, l-j)$ のみに依存する.

そこで, 整数の組の部分集合 $B$ を

$B:=\{(x,y) \in \mathbb{Z}^2 \mid \sqrt{x^2+y^2}=\sqrt{M}\}$

と定義する. このとき, 整数 $x$ について以下の事がわかる.

$(x,y) \in B$ となる整数 $y$ が存在するならば, $-\sqrt{M} \leq x \leq \sqrt{M}$ である.
各整数 $x$ において, $(x,y) \in B$ となる整数 $y$ は高々2個である.

よって, $\# B=O(\sqrt{M})$ であることがわかった.

あとは幅優先探索を利用してマス $(1,1)$ からの最小操作回数を求めれば良い. 計算量はマスの数が $N^2$ で, 各マスについて最大で $O(\sqrt{M})$ 個の移動の方法があるので, $O(N^2 \sqrt{M})$ 時間である.