TopCoder SRM 719 Div1 Easy (Div2 Med): LongMansion

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

行無限列のマス目がある。 行目のマスを踏むとき、どの列においてもコストが かかる。

から まで移動するとき、コスト和の最小値を求めよ。

解説

横方向に移動するとき、複数の行を利用するメリットはありません (途中でどこかの行に移動するほうが得である場合は、最初からより得になる行にいたほうが良いため、結局 つの行しか使いません)。なので、どの行を利用して横方向に移動するかを全探索すればよいです。

横方向の移動に 行目を利用するとき、 という移動経路を取るため、コストを計算するにはこの つをそれぞれ計算すれば良いです。累積和を用いると になりますが、 が小さいので愚直にやっても通ります。

ソースコード

class LongMansionDiv1 {
    public:
    int sum[60];
    long long minimalTime(vector<int> t, int sX, int sY, int eX, int eY) {
        int N = t.size();
        for(int i=0; i<N; i++) {
            sum[i+1] += sum[i] + t[i];
        }

        long long int ans = INF;
        for(int i=0; i<N; i++) {
            long long int tmp = 0;
            // sX -> i
            int mi = min(i, sX), ma = max(i, sX) + 1;
            tmp += sum[ma] - sum[mi];

            // y
            long long int width = abs(sY - eY);
            tmp += width * t[i];

            // i -> eX
            mi = min(i, eX), ma = max(i, eX) + 1;
            tmp += sum[ma] - sum[mi] - t[i];
            ans = min(ans, tmp);
        }
        return ans;
    }
};