hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

TopCoder SRM 719 Div1 Easy (Div2 Med): LongMansion

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

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

 (sX, sY) から  (eX, eY) まで移動するとき、コスト和の最小値を求めよ。

解説

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

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

ソースコード

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;
    }
};