CODE FESTIVAL 2016 Tournament Round 3: A - ストラックアウト / Struck Out

問題概要

1~Nまでの番号がついたN個のパネルがある。1度のゲームではK回ボールを投げてi回目にパネルjに当てるとi×Aj点が得られ、各回の点の和が得点となる。当てたパネルを順にP1, P2, ..., PK としたとき、1 <= P(i+1) - Pi <= M という条件の下でありうる最大の得点を求めよ。

N, M <= 105

K <= min(300, N)

解法

dp(i, j): i回目にパネルjに当てたときの最大の得点

とすると、dp(i, j) = max(dp(i-1, k) for k in (j-M)~(j-1)) である。セグ木をK本持てば普通にできそうだが、それだと O(KNlongN) で2秒には間に合わない。ここでjの小さいほうから順にdpを更新していく過程を見ていると、dp(i-1)から区間を横にずらしつつ最大値を取っていく形になっていることがわかる。このような場合スライド最小値(ここでは最大値だが)のやり方が使えて、これだと計算量がならしでO(N)になる。これでlogが落ちて答えが求まる。

おまけ:スライド最大値について(たぶん俺にしかわからないので蟻本2版p300を見てください)。

  • まず両端キュー(deque)を用意する。
  • このキューには値ではなくインデックスが入る
  • このキューの並び順は、常に次の条件を満たす
    • 左にあるものほど、そのインデックスが指す要素の値が大きい
    • 要素の値の大きさが同じ場合は、左にあるものほどインデックス自体が小さい
  • この条件が満たされている場合、区間の最大値は常にキューの左端に入っているインデックスを参照することでO(1)で得ることができる
  • 既にキューがこの状態になっていると仮定して、区間を右にひとつずらすことを考えると
    • まずずれた結果区間から外れたインデックスをキューから削除する。もしキューの左端を見て、そのインデックスがそれであればそのままpopする。そうでなければそのインデックスはもうキューの中にはないので何も操作する必要がない。
    • 次に新しく加わるインデックスをキューに追加する。今度は右からキューを見ていって、キューが空になるかあるいはキューの右端インデックスの指す要素の値が新しいインデックスの要素の値より小さい間は右をpopし続ける。止まったらそこに新しいインデックスをpushする。
    • 以上の操作では各インデックスについてpushとpopが高々1回ずつしか行われないので、ならしでO(N)となる

感想

まんまとlogをつけてTLEした。ゆきことか昔のABC-Dっぽい教育的問題感がある(スライド最小値名前だけ聞いてシカトしてたので勉強になった)。このくらい狙った設定じゃないとなかなかlog付きだけ落とすぞってのは難しそう

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip, std.regex;

immutable long INF = 1L << 59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto K = s[2];
    auto A = readln.split.map!(to!long).array;

    auto dp = new long[][](2, N);
    dp[0] = A.dup;
    int cur = 0, tar = 1;

    foreach (i; 1..K) {
        dp[tar].fill(-INF);
        auto q = new long[](2*N+10);
        int x = N/2;
        int y = N/2;
        foreach (j; i..N) {
            int a = j - M - 1;
            int b = j - 1;
            if (a >= 0 && x < y && q[x] == a) x++;
            while (x < y && dp[cur][q[y-1]] < dp[cur][b]) y--;
            q[y++] = b;
            dp[tar][j] = dp[cur][q[x]] + A[j] * (i + 1);
        }
        swap(cur, tar);
    }

    dp[cur].reduce!max.writeln;
}