コンテストページ: Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 289） - AtCoder

コンテスト中AC: A〜E
コンテスト後にFをAC。WAが出たので、解説を見たが、解法は合っていて実装が間違っていた。

E - Swap Places

高橋くんがいる頂点と青木くんのいる頂点の組について、その状態となるのに最小の操作回数のみを記録していればよく、逆に、同じ状態になるのに、それより操作回数が大きくなる場合は無視できます。

これより、全頂点の組について、その状態になるための最小の操作回数を調べていく解法が考えられます。

状態と遷移の関係を有向グラフとみなすことができるので、BFSにより最小回数を決定していくことができます。

この有向グラフの頂点数は全頂点対となるので $N^2$ 個となるのはわかりますが、辺数はコンテスト中分かりませんでした。(ただ、解法として考えうるのがこの方法しかなかったので、提出しました。)

辺数は、公式解説で見積もり方が書いてありました。こちらにもメモしておきます。

あるグラフ $G=(V,E)$ の全頂点対について、頂点対から出る全ての辺の合計は $4M^2$ 以下となる

実装: Submission #38811108 - Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 289）

F - Teleporter Takahashi

操作をシミュレートすると、下のような感じの各辺がx軸とy軸に平行な長方形領域が得られます。
oxoxoxo
xxxxxxx
oxoxoxo
xxxxxxx
oxoxoxo

上の1文字を長方形領域に含まれる格子点の1つとみなします。
oが $(s_x , s_y)$ が移動可能な場所、xが不可能な場所です。また、この領域の縦と横の長さは問題で与えられる長方形 $R$ によって異なります。

この長方形領域の左端、右端のx座標をそれぞれ $X_0, X_1$ 、下端、上端のy座標を $Y_0, Y_1$ とします。

oが現れるのは、この長方形領域内の格子点であって、格子点 $(x,y)$ について、 $x-X_0$ が2の倍数かつ、 $y-Y_0$ も2の倍数の時となります。

操作終了後に $(t_x , t_y)$ がoの場所に存在すれば、 $(s_x , s_y)$ から移動可能ということになります。

$i$ 回目の操作終了後の $X_0$ を $X_0[i]$ とします。 $X_1,Y_0,Y_1$ も同様とします。
$i$ 回目の操作終了後に $(t_x , t_y)$ がoであるための条件は以下です。

$X_0[i]\leq t_x \leq X_1[i]$
$Y_0[i]\leq t_y \leq Y_1[i]$
$(t_x-X_0) \ mod\ 2 \equiv 0$
$(t_y-Y_0) \ mod\ 2 \equiv 0$

問題文の条件から、 $10^6$ 回しても上記条件を満たすものが存在しない場合はNoです。

ところで、操作に従って $X_0[i],X_1[i],Y_0[i],Y_1[i]$ を計算できる必要があります。
これは、端から端への移動になるので、以下のように計算できます。

$X_0[i] \leftarrow min(|a-X_0[i-1]|,|b-X_0[i-1]|,|a-X_1[i-1]|,|b-X_1[i-1]|)$
$X_1[i] \leftarrow max(|a-X_0[i-1]|,|b-X_0[i-1]|,|a-X_1[i-1]|,|b-X_1[i-1]|)$

$Y_0[i],Y_1[i]$ についても、 $a,b$ が $c,d$ に変えて同じように計算できます。

では、Yesの場合に操作の列の構築方法を記載します。
前準備として、操作終了までの $X_0[i],X_1[i],Y_0[i],Y_1[i]$ を全て記録しておきます。

$i$ 番目の操作の直後の点を $(x_{i},y_{i})$ とします。 $i$ 番目の操作で $R$ 上の格子点 $(m_x,m_y)$ を選んだとします。
操作前の点 $(x_{i-1},y_{i-1})$ は

$x_{i-1} = m_x + m_x - x_i = 2m_x - x_i$

同様に、

$y_{i-1} = m_y + m_y - y_i = 2m_y - y_i$

と計算できます。
ここで、 $(x_{i-1},y_{i-1})$ が満たすべき条件は、

$X_0[i-1] \leq x_{i-1} \leq X_1[i-1]$
$Y_0[i-1] \leq y_{i-1} \leq Y_1[i-1]$

なので、

$X_0[i-1] \leq 2m_x - x_i \leq X_1[i-1] \Rightarrow \lceil \frac{X_0[i-1]+x_i}{2} \rceil \leq m_x \leq \lfloor \frac{X_1[i-1]+x_i}{2} \rfloor$

同様に、 $\lceil \frac{Y_0[i-1]+y_i}{2} \rceil \leq m_y \leq \lfloor \frac{Y_1[i-1]+y_i}{2} \rfloor$

ここで、 $a\leq m_x \leq b$ 、 $c\leq m_y \leq d$ も満たす必要があります。従って、 $(m_x,m_y)$ が満たすべき条件は、

$max(a,\ \lceil \frac{X_0[i-1]+x_i}{2} \rceil) \leq m_x \leq min(b,\ \lfloor \frac{X_1[i-1]+x_i}{2} \rfloor)$
$max(c,\ \lceil \frac{Y_0[i-1]+y_i}{2} \rceil) \leq m_y \leq min(d,\ \lfloor \frac{Y_1[i-1]+y_i }{2} \rfloor)$