B - だんだん強く

https://beta.atcoder.jp/contests/dwacon2018-final-open/tasks/dwacon2018_final_b

ニコ生の公式解説でちらっと触れていた解法が凄くスマートだったので復習を兼ねて書いておきます。

解法

与えられた[v_1, v_2, ..., v_n]を(K+1)倍に拡張した次のような配列を考えます。Cを十分大きな整数として、
[v_1 + K*C, v_1 + (K-1)*C, ..., v_1, v_2 + K*C, v_2 + (K-1)*C, ...]
とします。この配列に対して最長増大部分列問題(LIS)をO(NlogN)で解くおなじみのアルゴリズムを適用して終わりです。

配列のサイズが(K+1)Nになるので、計算量はO(KNlog(KN)) = O(KNlogN)になります。

なぜこれで解けるのか？

(K+1)倍に拡張した新たな配列は一体どういうものかと考えると、元の配列vを十分大きなギャップを持たせて(K+1)階の層に分けるようなことをしています。
そうすると、「増大していかなければいけない」というルールに違反することを「層を１つ上に上がる」ということに対応させることが出来ます。
例えば入力例1(K=2, v = [4,1,6,2,8,5,7,3])だと以下のようなイメージになります。

一番下の層は違反する余地が2回あって、真ん中は1回、一番上まで来るともう違反できないという感じになっています。
そして１つの解である[4,1,2,5,7,3]に対応するのが矢印で示された列になっていて確かにこれで上手くいくなということが分かります。

感想

初め問題を見たときは違反した回数ごとのセグメント木を持って何かごちゃごちゃやるんだろうなとか思って（実際そっちも１つの想定解らしいです）何かよく分からないなと思っていたのですが、発想１つでこんなにもスマートに解くことができるんだなあと感心しました。

コード

適宜省略

void main() {
    int n, k;
    int[] v;

    scan(n, k);
    v = readln.split.to!(int[]);

    immutable long c = 10L^^9 + 1;

    auto u = new long[](n*(k+1));

    foreach (i ; 0 .. n*(k+1)) {
        u[i] = v[i/(k+1)] + c*(k - i%(k+1));
    }

    immutable long inf = long.max;

    auto dp = new long[](n*(k+1) + 1);
    dp[] = inf;
    dp[0] = -1;

    long ans;

    foreach (i ; 0 .. n*(k+1)) {
        auto j = dp.assumeSorted.lowerBound(u[i]).length;
        dp[j] = u[i];
        ans = max(ans, j);
    }

    writeln(ans);
}