「まわしてそろえる」のコスト計算過程の備忘録
記事の概要
「まわしてそろえる」とは、第3回 RCO日本橋ハーフマラソン 本戦Bの問題です。
atcoder.jp
本記事は、以下のmaspy さんの記事を見て復習していたのですが、コストの効率的な導出をきちんと理解するために、ちゃんとゴリゴリと式展開をした過程をメモした、自分用の備忘録です。
maspypy.com
解法の概略としては「2つの領域に分ける問題」の小問題として3つに分割し、各小問題では、一部の要素に限定して$x$座標または$y$座標の総和でビームサーチをします。例えば、0～3の数字を「0または1」と「2または3」に上下で分ける時、「0または1の$y$座標の総和」がコスト関数になります。解法の細かなポイントは他にもいくらかありますが、記事の本質ではないので省略します。
上記の計算は、2次元累積和を管理することで高速化ができるのですが、きちんとその導出を自分の手で行おうとしたら詰まってしまったので、その流れをメモすることが本記事の目的です。
導出方法
本記事でやることは1つだけで、現在の解の状態から特定の領域を90度、180度、270度、１回だけ回転させた時に、どのようなコスト差分になるか計算することを目指します。以下では、例として領域$S$を$a \leq x < a + s, b \leq y < b + s$（この$x, y, s$は、問題中の操作に対応します）、$D_S$ を$S$の内部で下へ寄せたい要素（上記の例では「2または3」）、$U_S$は$S$の内部で上へ寄せたい要素（上記の例では「0または1」）とし、$p \in U_S$ に属する$y$座標の総和がどう扱われるかを書いてみます。
$Y(p): Z^2 \rightarrow Z$を、座標$p = (x, y)$から$y$を取り出す関数、同様に$X(p): Z^2 \rightarrow Z$ を座標$p = (x, y)$から$x$を取り出す関数とすると、コスト関数は以下のように書けます。
$$
\sum_{p \in U_S} Y(p)
$$
今、$p$ を$(a, b)$を起点に時計回りに90度回転させて$f(p)$に移動させる時、回転させる小領域内部で左上を原点と見なす相対座標$(x_r, y_r)$は、以下のように移ります。
$$
(x_r, y_r) \rightarrow (s - 1 - y_r, x_r)
$$
ここで、$x = a + x_r, y = b + y_r $に注意すると、最終的に$(x, y)$ は以下のように式変形して移ります。
\begin{align}
(x, y) & = (a + x_r, b + y_r ) \\\
& \rightarrow (a + s - 1 - y_r, b + x_r) \\\
& \rightarrow (a + b + s - 1 - y, b - a + x)
\end{align}
今、関数$F(V) = \{ f(p) | p \in V \}$ を、集合$V$の各要素を回転を通じて移動させる関数として、
$$
\sum_{p \in F(U_S)} Y(p)
$$
が$\sum_{p \in U_S} Y(p)$と比べてどう変化するのかを知りたいです。これは、
\begin{align}
\sum_{p \in F(U_S)} Y(p) &= \sum_{p \in U_S} Y(f(p)) \\\
&= \sum_{p \in U_S} Y(f( (x, y) )) \\\
&= \sum_{p \in U_S} Y( (a + b + s - 1 - y, b - a + x) ) \\\
&= \sum_{p \in U_S} (b - a + x) \\\
&= |U_S| (b - a) + \sum_{p \in U_S} X(p)
\end{align}
みたいなことをすると、計算が展開できます（$p = (x, y)$と置き換えたのが、やや不自然かもしれません…）。同様に$X(p)$の方も頑張って展開すると$|U_S| (b + a + s - 1) - \sum_{p \in U_S} Y(p)$のような式が出てくることから、結局以下の計算が高速にできると嬉しいことがわかります。
\begin{align}
c_y &= \sum_{p \in U_S} Y(p) \\\
c_x &= \sum_{p \in U_S} X(p) \\\
c_1 &= |U_S|
\end{align}
これらの計算は、$U_S$が長方形上の領域であることを考えると、2次元の累積和を用いることで高速化できることがわかります。
また、$f$で回転させる操作を何度も適用しても同じことなので、180度、270度の回転でも同じことが言えます。$F$を通じた$(c_x, c_y)$の変化を改めて明示すると、
\begin{align}
\sum_{p \in F(U_S)} Y(p) &= |U_S| (b - a) + \sum_{p \in U_S} X(p) \\\
&= c_1 (b - a) + c_x
\end{align}
と書けるので、$c_y \rightarrow c_1(b - a) + c_x$ と移ることがわかります。同様に、
\begin{align}
\sum_{p \in F(U_S)} X(p) &= |U_S| (a + b + s - 1) - c_y \\\
\end{align}
となるので、$c_x \rightarrow c_1(a + b + s - 1) - c_y$ と移ります。
この写像を1, 2, 3回適用させると、それぞれ90度、180度、270度回転に対応するので、簡単に計算ができることがわかりました。
ここまで振り替えってみると、線形の写像しか登場しないし、わかってしまえばそれはそうだよなーという感じでしたが、結局このきちんとした導出をするために数時間溶かしてしまったので、メモを残したのでした。少し冗長な表現な気もする（例えば、わざわざ$F$のようなものを持ち出したあたり）のですが、わからなくなった時に自分が一番しっくりきた表現だったので、ここでは将来の自分のためにそのまま残しておくことにします。
