AtCoder ABC 315 F - Shortcuts (青色, 500 点)

実は DP の添字の取りうる範囲が log オーダーであることを見抜く問題。より高度な問題でもしばしば見られる考え方。

• 問題へのリンク

問題概要

二次元平面上に点 がある。点 の座標は である。

今、点 1 にいて、原則として点 を順に通過して最終的に点 に到達したい。ただし、途中いくつかの点をスキップしてもよい。最終的にスキップした点が 個であるとき、 ならば のペナルティが課せられる。

点 に到達するまでの道のりと、ペナルティとの総和の最小値を求めよ。

制約

• 
• 

考えたこと

第一感思いつくのは、次の配列 dp を更新していく DP だろう。

dp[i][j] ← 点 に到達するまでの方法のうち、途中 個の点をスキップした場合の、道のりの最小値

しかしこれでは、DP 更新の遷移先も考慮すると の計算量となって間に合わない。

添字の取りうる値の範囲が log オーダー

そこで、よくある考察としては「実は DP の遷移先は少ないで済むのではないか」や「実は DP の添字の取りうる値の範囲は小さいのでは」といったものがある。

今回は、ペナルティ という値に着目しよう。これは指数関数なので、 が大きくなると急速に大きくなる。 は小さい範囲だけ考えれば良いのだ。

具体的には、 が「すべての点を飛ばさなかった場合の答え」を超えない範囲を考えればよい。すべての点を飛ばさなかった場合の答えとして考えられる最大値を考えても、それは 以下なので、 くらいまで考えれば十分だ。

ここでは余裕を持って、 までを考えることにした。計算量をあえてかけば、座標値の最大値を として、 と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<double> X(N), Y(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];
    
    auto calc = [&](int i, int j) -> double {
        double res = (X[i]-X[j])*(X[i]-X[j]) + (Y[i]-Y[j])*(Y[i]-Y[j]);
        return sqrt(res);
    };
    
    const double INF = 1LL<<60;
    const int MAX = 50;
    vector dp(N, vector(MAX, INF));
    dp[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < MAX; ++j) {
            for (int add = 0; add < MAX; ++add) {
                int i2 = i + add + 1;
                if (i2 >= N || j + add >= MAX) continue;
                chmin(dp[i2][j+add], dp[i][j] + calc(i, i2));
            }
        }
    }
    double res = INF;
    for (int j = 0; j < MAX; ++j) {
        double add = 0;
        if (j > 0) add += 1LL<<(j-1);
        chmin(res, dp[N-1][j] + add);
    }
    cout << fixed << setprecision(10) << res << endl;
}