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);
}

No.643 Two Operations No.2

No.643 Two Operations No.2 - yukicoder

考察

xとyの比を取って、p = x/yと置くとx=yにするということはp=1にするということと同値であることが分かります。
（ただし、y=0のときはp=∞であると考えることにします。また(x, y) = (0, 0)は少し特殊なので無いものとします）
このpで与えられた各操作を考えてみると、

• 操作1:p -> 1/p
• 操作2:p -> (p+1)/(p-1)

にすることであるということが計算によって分かります。この操作を繰り返してp=1にするゲームだと思えばいいことになります。

p=1に1ステップで行ける状態を考えてみます。操作1は1を1にするだけなので考えてもしょうがないです。操作2は(p+1)/(p-1)=1となるpを求めることになりますが本来ならそのようなpは存在しません……
ですがp=∞とすると、（∞+1)/(∞-1) = ∞/∞ = 1なのでp=∞からp=1へは１ステップで行けることが分かりました。（この計算は本当はめちゃくちゃなので、元の(x,y)で計算して確かにこれが正しいことを示す必要があります）

次にp=∞に1ステップで行ける状態を考えてみます。操作1を考えると1/0=∞なので0から１ステップで行けます。操作2を考えると分母が0になるpということなのでp=1から操作2で１ステップで行けます。（本当はめちゃくちゃ）

さらにp=0に1ステップで行ける状態。操作1では1/∞=0なので∞から0へ１ステップで。操作2ではp=-1のとき分子が0になるので、-1から0へ１ステップで。

さらにp=-1に1ステップで行ける状態。操作1では明らかに-1から-1。操作2では(p+1)/(p-1)=-1を解くと、p=0。0から-1へ１ステップ。

ここで状態がもう増えなくなったので結局どういうことになっているかをグラフにまとめると以下のようになっています。

よって、与えられた(x,y)からpを求めて、それがこのグラフに乗っていればその最短距離を返す。
これ以外の点であれば、これらの操作を繰り返してもp=1に到達することはできないので-1を返します。

感想

とても難しい★２だと思いました。コンテスト中には解けませんでしたが……楽しかったです。

この考え方は、testestestさんがまとめていてくれている「射影空間へうつす」という奴に対応しているはずでそれを使うと今回の議論が正当化できるはずです……多分。

http://sugarknri.hatenablog.com/entry/2018/02/03/021632

No.642 Two Operations No.1

No.642 Two Operations No.1 - yukicoder

考察

とりあえず整数を頂点、操作を辺としてグラフにしてみると以下のような感じになります。

頂点数はNで辺の数は2Nなので、N <= 10^6程度ならこのグラフで頂点1からBFSをすることで
最短距離（最小操作回数）が求められますが、今回はN <= 10^9なのでもう少し工夫しないといけないようです。

頂点iへの最短距離をdist(i)と書くことにします。

グラフをよく見てみると、奇数の頂点は１つ大きい数からしか到達できないのでi = 2k + 1とすると、dist(2k + 1) = dist(2k + 2) + 1となっていることが分かります。

問題は偶数の頂点で、この頂点には辺が２つ入ってきます。なので
dist(2k) = min(dist(k), dist(2k+1)) + 1
と書けます。何となく、小さいケースでいくつか試してみると、常にdist(k) <= dist(2k+1)が成り立っているような気がします。

実際に、頂点2kの周りとkの周りの関係を書いてみると以下のようになります。

もしここで、dist(k) > dist(2k+1)が成り立っていたとしたら最短路を逆順にたどっていくと、2k -> 2k+1 -> 2k+2までは一直線に進みます。ここでまた分岐するのですが、もしここで2k+2 -> k+1と戻る枝を使ったとすると、結局k+1から3ステップで2kに来ることになるので、dp(2k) = dp(k+1) + 3となります。（下図赤線）
一方で、k+1 -> k -> 2kと高々2stepで行くことができるので、dp(2k) <= dp(k+1) + 2であることが分かります。（下図青線）
これは矛盾しているので、2k+2 -> k+1と戻る枝を使ったことは誤りとなります。

なのでさらにさかのぼって2k -> 2k+1 -> 2k+2 -> 2k+3 -> 2k+4と行ってまた枝分かれするんですが、ここでも2k+4 -> k+2と戻る枝を使うと仮定すると矛盾が起こることが同様に分かります。

よって帰納的にこのようなことが示せてしまうので、結果的にはそもそもdist(k) > dist(2k+1)と仮定していたこと（つまり2k <- 2k+1が最短路に含まれていたと仮定したこと）が誤りであるということが言えます。よってdist(k) <= dist(2k+1)なので、「2kに行くにはkから来る枝を使う」としていいことが分かります。

上の議論によって何が言えるかというと、

• nが奇数のときは、n+1に戻ればよい
• nが偶数のときは、n/2に戻ればよい

ということなので、後はこれをn = 1になるまで繰り返せばよいということになります。2回に1回はnが半分になるので計算量的にもだいたいO(logN)なのでこれで十分間に合うということが分かります。

感想

難しい★２だと思いました。