AOJ 0364 - Dungeon
概要
(0, 0), (W - 1, 0), (0, H - 1), (W - 1, H - 1)を頂点に持つ長方形の座標領域内に、N個の重複しない点がある。(1 <= H, W, N <= 10^5)
あなたは最初に(0, 0)にいる。次の行動が任意回行える。
1, x座標、もしくはy座標を1増減させる。(もちろん長方形内に収まるように動くこと) そのさい、コスト＋１とする。
2. 今いる頂点を(x, y) = (a, b)とすると、x = aとy = b上のすべての点を消す。
すべての点を消しきるまでにかかる最低のコストはいくつでしょう？
ACするまで
1. 愚直にやると二乗でTLE。かといって座標圧縮もできない。
2. 両軸を左右に分ける二部グラフのノリで書き直すも、何も見えない。
3. 何度も曲がる必要がないので、一度曲がれば済むとわかる。
4. あきらめた。もっと粘り強くやるべき。
5. O(N)とO(N log N)なら間に合うときに、座標上の点を扱うにあたっての常套テクニック、「片方の座標をキーにしてソート」(一つの軸を固定してそれをキーにソート)を行う。
6. その操作を行った後ひとまず曲がり角を全探索でもしてみるとあら不思議、ソートされてるおかげで前処理をすれば1回あたりO(1)で計算できる。 -> AC
考察
O(N^2)は厳しいけど、O(N log N)ならば問題ないというときには、
片方の座標をキーとしてソート
を試すのが鉄則。
今回の場合、ひとまずy軸(0 -> Hの方)をキーとして並び替えてみる。
並び替えたのちのy座標が小さい順からi番目の点で90度曲がるとする。
この時、0 -> i番目の点は定義から距離が簡単に求まる。
方向転換後、i番目の点からすべての点を消しきるまでにx軸の向きへ移動する距離を求まればよい。
y座標が小さい順からi番目までのすべての点はすでにここまで来る途中に処理されているので、小さい順からi + 1番目から最後までの点でのx座標の最大のものまで行けば、i番目の点で方向転換するときの最適解が求まる。
この時、a番目から最後までという値は、配列で後ろから見てメモすることで前計算をO(N)で済ませば、O(1)でアクセスできる。
よって、全体的にO(N)かければ全探索ができるということがわかる。
ちなみに、今はひとまずy軸の向きに進みそれからx軸の向きに進んだが、x軸の向きに進みそれからy軸の向きに進む場合も最適である可能性があるので、先ほどと同じようなこともやらないといけない。
ACコード：
Aizu Online Judge
一言
痛い目に遭って初めて深く刻まれる。
