Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

最近の 45 度回転事情

数学

こんばんは, kagamiz です! ちょうど 1 歳老けたところです :).

この記事は Competitive Programming Advent Calendar 2014 の 21 日目の記事として書かれました.

この記事では, 最近ぼくが見た範囲で出題された 45 度回転の問題を紹介していこうと思います.ちなみに僕の中の最近は過去 6 年くらいまで含むのでご注意下さい.

1. 45 度回転の幾何学的解釈

競技プログラミングで 45 度回転 というと, 入力として与えられた 2 次元平面の点 (x,\ y) を (x - y,\ x + y) ないし (x + y,\ x - y) に変換する操作を指すことが多いです. 数学的な意味で, 点 (x, y) を原点に対して 45 度回転するという操作は, 行列を用いて

\begin{pmatrix}x' \\ y'\end{pmatrix} = \begin{pmatrix}\cos \dfrac{\pi}{4} & -\sin \dfrac{\pi}{4} \\ \sin \dfrac{\pi}{4} & \cos \dfrac{\pi}{4} \end{pmatrix}\begin{pmatrix}x \\ y\end{pmatrix} = \dfrac{1}{\sqrt{2}}\begin{pmatrix}x - y \\ x + y\end{pmatrix}

と表されるので, (x,\ y) \to (x - y, x + y) という操作は \boldsymbol{v} = (x,\ y) という位置ベクトルを, \sqrt{2} 倍して 45 度回転した位置に変換することを表しています.

勝手に大きさを \sqrt{2} 倍していいか心配になりますが, 大きさが本質でない問題でない限り変換後の点の大きさは使わないので問題ありません. むしろ大きさを考慮すると, 整数座標での入力が実数になったりしてかえって不便です.

45 度回転をして何が嬉しいのかはとりあえず以下の問題解説などで考えていきます.

問題紹介

問題文に x + y とか x - y と書かれていますね. 45 度回転チャンスです.
回転後のチェッカーボードを実際に書いてみると, 簡単な数式で答えが表されることが分かります.

この問題では菱型どうしの内包判定する必要がありますが, 菱型をそのまま扱うのは面倒です.
そこで, 座標系を原点について 45 度回転すると, 菱型が正方形になってグッと扱いやすくなります.

...ちなみに僕は本番では解けませんでした. 本戦の記憶は闇...ザンネン.

2. マンハッタン距離について

いきなり横道にそれます(ごめんなさい). しばしば 45 度回転の問題を考える上で一緒に出てくるマンハッタン距離 についてまず紹介をします.
マンハッタン距離とは, n 次元平面上の点 \text{P}(x_{P_1},\ \cdots,\ x_{P_n}), \text{Q}(x_{Q_1},\ \cdots,\ x_{Q_n}) について

d_{PQ} = \displaystyle\sum_{i=1}^{n} |x_{P_i} - x_{Q_i}|

で定義される量 d_{PQ} のことです.

上では n 次元の場合の式を書きましたが, 次の 2 次元の場合の式はよく見る機会があると思います :
2 次元平面上の点 \text{A}(x_A, y_A),\ \text{B}(x_B,\ y_B) について, d_{AB} = |x_A - x_B| + |y_A - y_B|.

1 次元の場合は普通のユークリッド距離と全く同じになりますね.

マンハッタン距離の性質1

マンハッタン距離を扱う問題では, しばしば各次元ごとの操作を独立に行うことが出来ます. 例えば, 次のような問題を考えてみます. (余裕があれば KOJ に入れます)

1 次元上の整数の点列 A_1,\ A_2,\ \cdots A_n を考える.
このとき, \displaystyle\sum_{i = 1}^{n} |A_i - x| を最小にする整数点 x と, その時の和の値を求めよ. x が複数ある場合どれを出力してもいい.
制約 : 1 \leqq n \leqq 10^5,\ -10^9 \leqq x \leqq 10^9.

この問題はよく知られている問題で, こうなる x は A_i の中央値 ( A_i が偶数個のときは 2 つの中央値の間の数であればなんでもいい) ということが知られています.
イメージとしては, 中央値を基準に, 中央値の左側の点たちと右側の点たちに点が 2 分されて, そこより右に点を動かすと左側の点と中央にあった点の分だけ和の値が増えるので損をし, 逆に動かしても同様, という感じです.
中央値さえ見つけることができればいいのでソートをすると O(n \log n) で解けます.

では, この問題をもとに次の問題を考えてみます.

2 次元平面上に n 個の格子点 A_1,\ A_2,\ \cdots A_n を考える.
このとき, \displaystyle\sum_{i = 1}^{n} d_{A_iB} を最小にする 2 次元平面上の格子点 B と, その時の和の値を求めよ. B が複数ある場合どれを出力してもいい. ただし d_{A_iB} は 点 A_i と B のマンハッタン距離.
制約 : 1 \leqq n \leqq 10^5,\ -10^9 \leqq x \leqq 10^9.

さっきの問題が 2 次元平面に拡張されたものです. このとき, マンハッタン距離の定義を思い出すと,

\displaystyle\sum_{i = 1}^{n} d_{A_iB} = \displaystyle\sum_{i = 1}^{n} |x_{A_i} - x_B| + \displaystyle\sum_{i = 1}^{n} |y_{A_i} - y_B|

となるので, x座標についてのマンハッタン距離と y 座標についてのマンハッタン距離の和を独立に最小化すれば良いということが分かります. こうすると 1 次元についてのこの問題を 2 回解けば良いことになります.

マンハッタン距離の性質2

性質とかいう名前をつけましたが, どちらかと言うと絶対値の性質を使っている感じです.

マンハッタン距離の定義の式には絶対値が出てきましたが, 時として絶対値が無い方がうれしいことがあります. そこで, 絶対値を

|x| = \text{max}(x,\ -x)

として考えてみましょう.

すると, S を n 個の +1,\ -1 のいずれかの数からなる多重集合とし, A を先の条件をみたす S を要素とする集合すると,
n 次元平面上の点 \text{P}(x_{P_1},\ \cdots,\ x_{P_n}), \text{Q}(x_{Q_1},\ \cdots,\ x_{Q_n}) のマンハッタン距離 d_{PQ} は

d_{PQ} = \displaystyle\sum_{i=1}^{n} |x_{P_i} - x_{Q_i}| = \max_{S \in A} \displaystyle\sum_{i=1}^{n}\text{sgn}(S_i)(x_{P_i} - x_{Q_i})

となります. ただし, \text{sgn}(x) は x \gt 0 なら 1, x \lt 0 なら -1, x = 0 なら 0 を表します.

いきなりやばい式になったので 1 次元の場合と 2 次元の場合を具体的に書きます.

1 次元の場合, 点 \text{A}(x_A),\ \text{B}(x_B) を考えると, マンハッタン距離 d_{AB} = \text{max}(x_A - x_B, x_B - x_A).

2 次元の場合, 点 \text{A}(x_A,\ y_A),\ \text{B}(x_B,\ y_B) を考えると, マンハッタン距離は

d_{AB} = \text{max}(x_A - x_B + y_A - y_B,\ x_B - x_A + y_A - y_B,\ x_A - x_B + y_B - y_A,\ x_B - x_A + y_B - y_A)

で与えられます. 絶対値の符号を + と解釈するか - と解釈するかの違いですね. あとのため見通しがよくなるように書き直すと

d_{AB} = \text{max}(x_A + y_A - (x_B + y_B),\ -(x_A - y_A) - -(x_B - y_B),\ x_A - y_A - (x_B - y_B),\ -(x_A + y_A) - -(x_B + y_B))

となります.

こんなことをして何が嬉しいかを考えてみましょう. たとえば, 上のようにマンハッタン距離を定義することで, n 次元上の m 個の点列のうち, マンハッタン距離が最も遠い点対を {\rm O}(2^n \cdot m) 時間で見つけることが出来ます.

問題紹介

上の解説の着想はほぼこの 2 つの問題から来ています.

マンハッタン距離についてググってたら tozangezan さんのブログに行き着いたのでこれも紹介しておきます.

性質 2 を使うと解けます. 詳しくは 5. に乗せている JAPLJ さんの記事が参考になると思います.

3. 45 度回転とマンハッタン距離

先に書いた性質 2 を凝視しましょう. x - y という項と x + y という項が現れていますね. これは 45 度回転チャンスです. 何が言いたいかというと, x' = x + y, y' = x - y と書き直すと, 2 次元平面上の 2 点 \text{A}(x_A,\ y_A),\ \text{B}(x_B,\ y_B) のマンハッタン距離 d_{AB} は

d_{AB} = \text{max}(|x_A' - x_B'|, |y_A' - y_B'|)

となって, 変換後の座標系では距離を導出するときに軸を分離して考えることが出来るのです.

問題紹介

でぐわーでぐわっ. DEGwer くんが作った問題です. かつて CodeForces で出そうとして Gerald さんに止められました(難度が当時のせっとと合わなかった.)
怪しい絶対値記号が書かれていますね. 45 度回転チャンスですね... これはどちらかと言うと逆回転ですが.

JOI の問題です. 平面上の点対を, マンハッタン距離が一定の 2 つのグループに分けるとき, 分ける基準の距離を最小化しようと言う問題です.
数学的な解き方もありますが, ここでは距離の最小化というキーワードから解のアプローチを考えます.
ある距離 D でグループ分けができれば, 距離 D + 1 でも同じグループのままグループ分けができていそうです. よって, 距離 X でグループ分けができるかどうかという判定が {\rm O}(f(n)) で出来たとすると, この問題は {\rm O}(f(n)\cdot\log A) ( A は解の最大値) くらいで解けそうです. 愚直な判定関数だと f(n) = {\rm O}(n^2) となって満点は厳しいかも.
ここで, 45 度回転した座標系でのマンハッタン距離を使うことを考えてみると高速な判定関数が書けそうです. 詳しくは
AOJ 0552: Exposition：Snowing day：So-net blog あたりをご参照下さい.

4. その他の 45 度回転事情

ここからは上で扱ったトピックとは別の 45 度回転の話を書きます.

問題紹介

catupper くんが作った問題を KCS に移植させてもらったものです. ジャッジでの制約は n \leqq 10^3 とかになっていますが, 実は同じ時間制限のままで n \leqq 10^5 でもこの問題を解くことが出来ます. キーとなるのは,

木 i から木 j への移動が可能であるときに, 不等式

T_j - T_i \geq |A_j - A_i|

が成り立つことです. 絶対値記号が出て来ましたね. マンハッタンチャンス, すなわち 45 度回転チャンスです. 詳しい解説は http://kagamiz.hatenablog.com/entry/2014/09/30/223219 に書いています.*1

https://twitter.com/takayuta1999/status/546648362317930496

5. まとめ

属性として 2 変数をもつものがあって, その関係が足し算や引き算で表されるもの, かつ絶対値が出てくるものは背後に 45 度回転が隠れていることが多々あります. (冒頭の菱型も式にすると |x - a| + |y - b| = c となって, x,\ y の関係が加減乗除や絶対値で表されている.)
積極的に 45 度回転を疑っていきましょう.
あと, 最近のとか言いながら最近の問題が 2 問しか無かったのめちゃくちゃ申し訳ないです.

6. 参考記事など

7. 謝辞

このアドベントカレンダーの記事は, JOI の夏期セミナーの際に Cicada Nude の問題文を読んで 3 分後に「45 度回転か」と言った @yutaka1999 先生に感銘を受けて書いた記事です. この場を借りて御礼申し上げます.

*1:本質は 45 度回転ではないが, 形として 45 度回転が出てくるのがとてもおもしろかった.