はまやんはまやんはまやん

hamayanhamayan's blog

倉庫番ロボット [パソコン甲子園2020 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0436

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0436/review/5811448/hamayanhamayan/C++14

解くのにかなり手こずった。難しかった。
ちょっとだけ遠回りも記しておこう。

遠回り

ダイクストラで解けないか考えて実装までしたがTLEした。
xy座標が[0,300]の範囲の点を状態として、遷移は上下左右の4移動と、移動可能なななめ移動である。
ななめ移動部分は無限に行けそうに見えて、実は

  • とあるy座標に対してx座標が[0,300]のどれか
  • とあるx座標に対してy座標が[0,300]のどれか

のどちらかとなる。
なので、遷移は301×2+4になるので、状態数とそこからの遷移で考えると、まあ、間に合わないのだが、
aojなので間に合ったりしないかなーとか思ったが当然のようにダメでしたね…

方針はあってる

ちょっと他の解法見ながらズルをしながら考えると、遷移を貪欲に絞ることが求められるようだ。
最短経路を取る問題は始点から終点までピンと糸を貼るような問題になるので、
一旦戻るような遷移にはならない。
一旦戻って(見た目勢いをつけて)移動しているようなものは糸を引っ張るようにすると、
戻らない経路に移る。
よって、始点から終点まで移動する場合、必ず終点の方向に移動することになる。
具体的には、x0≦x1、y0≦y1であるときに、遷移(a,b)から(c,d)を考えると、
a≦cかつb≦dを満たすことになる。
これにより遷移が一方向になり、遷移によってループすることがなくなる。
つまり、ダイクストラというよりDPで計算ができるようになる。

実装に落とし込んでいく

ここまで分かれば、それほど難しくない。
必須ではないが、問題を簡単化するためにx0≦x1、y0≦y1となる様に座標を調整しておこう。
具体的にはx0>x1であれば、図面を反転させることで、位置関係を変化させずに大小関係を修正できる。
反転させると、座標が負の数になってしまうので、+301で平行移動して正の座標にしておこう。
301とするのは壁の場所を調整するためである。

DP

dp[y][x] := (x0, y0)から(x,y)に移動する最短距離

としてDPを計算していく。
移動は常に単調増加していく感じで実装する。

dp[y][x]からdp[y+1][x]とdp[y][x+1]に遷移する。
これに加えて、y座標が奇数であれば、棚の上側にいるので、右上へのななめ移動ができる。
x座標が奇数であれば、棚の右側にいるので、これも右上へのななめ移動ができる。
ななめ移動はsqrt関数をうまく使ってコスト計算をする。

dp[y1][x1]が答え。

int X0, Y0, X1, Y1;
double dp[305][305];
const int MA = 302;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X0 >> Y0 >> X1 >> Y1;

    if (X0 > X1) X0 = - X0 + 301, X1 = - X1 + 301;
    if (Y0 > Y1) Y0 = - Y0 + 301, Y1 = - Y1 + 301;

    rep(y, 0, MA) rep(x, 0, MA) dp[y][x] = inf;
    dp[Y0][X0] = 0;
    rep(y, Y0, Y1 + 1) rep(x, X0, X1 + 1) {
        chmin(dp[y + 1][x], dp[y][x] + 1);
        chmin(dp[y][x + 1], dp[y][x] + 1);
        if (y % 2 == 1) rep(xx, x + 1, X1 + 1) chmin(dp[y + 1][xx], dp[y][x] + sqrt(1 + (xx - x) * (xx - x)));
        if (x % 2 == 1) rep(yy, y + 1, Y1 + 1) chmin(dp[yy][x + 1], dp[y][x] + sqrt(1 + (yy - y) * (yy - y)));
    }

    printf("%.10f\n", dp[Y1][X1]);
}