VK Cup 2016 - Qualification Round 1 D. Running with Obstacles

問題

codeforces.com

解法

戦略としては, JUMP するときは a[i]+1 から a[i+1]-1 のようにめっちゃ走ってから, a[i+1]+1 のように障害物の直後の場所に着地する, というようにするのが良さそうです。

dp[i] = (a[i]+1 から走って JUMP することで a[par]+1 -> (適当に走ってジャンプ) -> m にたどり着ける場合, その par の値)
とします。後ろから順番に dp[i] を求めていくと,

• a[i]+1 から走ってジャンプする条件として, (a[i]+1) + s <= a[i+1]-1
• a[i+1]-1 からジャンプして a[par]+1 に着地するための条件として, a[i+1]-1 + d >= a[par]+1

を満たしていたら, dp[i] = par とし, 次の目標地点 par を i に変更します(par はなるべくスタート地点に近いほうが良いのでここは貪欲で良い)。

あんまり dp っぽくなかったですねすみません。どちらかというと後退解析みたいな感じ(？)

const int MAXN = 200200;
int a[MAXN];
// 次にいける場所
int dp[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, s, d;
    cin >> n >> m >> s >> d;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a, a+n+1);
    a[0] = -1;
    int par = n;
    for (int i = n-1; i >= 0; i--) {
        if (a[i+1]-a[i] >= s+2 && a[par]-a[i+1] <= d-2) {
            dp[i] = par;
            par = i;
        }
    }
    if (par > 0) cout << "IMPOSSIBLE" << endl;
    else {
        for (int i = 0; i < n; i = dp[i]) {
            cout << "RUN " << a[i+1]-a[i]-2 << endl;
            cout << "JUMP " << a[dp[i]]+1-(a[i+1]-1) << endl;
        }
        if (m > a[n]+1) cout << "RUN " << m-(a[n]+1) << endl;
    }
    return 0;
}