SRM526 Div1 250

とぷこだ 過去問

問題

w*hのグリッドに分割される牧場があり、各セルには、何もいないか、1匹のアヒルがいる。

牧場にはN匹のアヒルがいて、全てのアヒルを縦か横方向に1列に連続して並べたい。
しかし、座標(a,b)にいるアヒルを座標(c,d)に動かすためには、|a-c|+|b-d|秒かかる。
1度に1匹ずつしか動かせないとき、アヒルを一列に並べる最小の時間を求めよ。

1<=w,h<=50

考え方

一列に並ぶ場所が決まれば、そこへアヒルを最短時間で動かせばよい。

もし、アヒルが並ぶべきセルが決まっているとき、そこへアヒルを動かす最短時間はどうやって求められるかを考える。
横方向に一列に並べる場合ならば、x方向で一番左側にいるアヒルから順番に、列の左側にいれていくのが最短となる(同じx座標に2匹以上いても関係ない)。
縦方向に一列に並べる場合でも同様にすればよい。

並ぶべきセルは、そのスタートするセルだけがわかればよいのでh*w。
そのセルから縦方向か横方向に並べた場合の最短時間を求めるのにh*w。
なので、h^2*w^2 = 6.25 * 10^6程度。

反省

一列に並ぶ場所はアヒルの各座標の中央値の場所のとき移動距離が最小になる(縦方向か横方向かも考えなくてよい)ので、それを使うとO(h*w + NlogN)でできる。