Mister雑記

競プロやります。

TCO2019 Round3B Easy 「TwoLadders」 (250)

community.topcoder.com

問題

y軸の各整数座標に、x軸に平行な足場が敷かれたフィールドがある。 さらに座標 (lx_1, 0), (lx_2, 0)からy軸に平行に梯子が伸びている。 またフィールドにはコインが N枚落ちていて、 i枚目のコインは座標 (X_i, Y_i)に置かれている。

あなたは今座標 (sx, 0)にいて、単位時間毎に

  • x軸方向に1移動する
  • 梯子をy軸正方向に1登る(降りることはできない)

のいずれかができる。全てのコインを集めるのに必要な時間の最小値を求めよ。

制約

  • 各座標は 0以上 10^9以下の整数
  •  1 \leq N \leq 100

考察

各層にてコインを全回収してから梯子を登る、というのを繰り返す。 両端のコインを回収することと全てのコインを回収することは同値なので、両端のどちらのコインを先に回収するかで場合分けをすれば最短時間は求まる。

後は直前にどちらの梯子から登ったかをDPで持っておけば終わりなのだが、実装してみると色々と面倒なことが分かる。

まずゴールについて。もし今いる階層より上にコインがない場合、コインを全回収した後はもう梯子まで移動する必要はない。

そして y = 0にコインがある場合。このコインだけは例外で、スタート地点が梯子ではない。よって例外処理をするなり上手く遷移に組み込む必要がある。

実装例

using namespace std;

using lint = long long;
const lint INF = numeric_limits<lint>::max() / 3;

class TwoLadders {
    lint walk(lint s, lint m, lint t) {
        return abs(m - s) + abs(t - m);
    }

    lint walk(lint s, lint m, lint n, lint t) {
        return abs(m - s) + abs(n - m) + abs(t - n);
    }

public:
    long long minSteps(int sx, int lx1, int lx2, vector<int> X, vector<int> Y) {
        map<lint, vector<lint>> coins;
        for (int i = 0; i < X.size(); ++i) {
            coins[Y[i]].push_back(X[i]);
        }

        vector<lint> dp(2);
        vector<lint> rad({lx1, lx2});

        lint ans = 0;
        if (coins.count(0)) {
            // y = 0にコインがあったときは例外処理
            lint L = *min_element(coins[0].begin(), coins[0].end());
            lint R = *max_element(coins[0].begin(), coins[0].end());

            ans = min(walk(sx, L, R), walk(sx, R, L));

            for (int i = 0; i < 2; ++i) {
                dp[i] = min(walk(sx, L, R, rad[i]), walk(sx, R, L, rad[i]));
            }
            coins.erase(0);
        } else {
            for (int i = 0; i < 2; ++i) {
                dp[i] = abs(rad[i] - sx);
            }
        }

        lint H = 0;  // コインの最高点 = 梯子を登った時間
        for (auto& p : coins) {
            H = max(H, p.first);

            lint L = *min_element(p.second.begin(), p.second.end());
            lint R = *max_element(p.second.begin(), p.second.end());

            ans = INF;
            for (int i = 0; i < 2; ++i) {
                ans = min(ans,
                          dp[i] + min(walk(rad[i], L, R),
                                      walk(rad[i], R, L)));
            }

            vector<lint> ndp(2, INF);
            for (int i = 0; i < 2; ++i) {
                for (int j = 0; j < 2; ++j) {
                    // iからjに移動
                    ndp[j] = min(ndp[j],
                                 dp[i] + min(walk(rad[i], L, R, rad[j]),
                                             walk(rad[i], R, L, rad[j])));
                }
            }

            swap(dp, ndp);
        }
        return ans + H;
    }
};

反省

  • DPは考察を詰めてから(ry
  • 実装で詰まってから焦るの本当に良くない。