この記事はレジリエントでウェルビーイングなぴょこりんクラスタ Advent Calendar 2024 の為に書いたものです。

はじめに

この記事は前回の続きです。

続きものとなりますので、前回の内容は（ここ）から参照してください。早速ですが問題のおさらいをして、解説に入っていきましょう。

Problem D2: Line of Delivery (Part 2) 問題設定(再掲)

英語を読むのが苦じゃない方なら原文の
Problem D2: Line of Delivery (Part 2) | Meta Hacker Cup - 2024 - Practice Round
をみるので十分かもしれませんが、
この記事はウェルビーイングな記事をめざしているため（？）、問題の要旨を以下に説明します

一次元のカーリングというゲームを考えましょう。これは一人用のゲームで、
座標 $0$ から右方向に大きさ１のストーンを次々と飛ばしながら、座標 $G$ にストーンを近づけることを目的とするゲームです。

あるプレイヤーは $N$ 個のストーンを $E_0, E_1, ... , E_{N-1}$ の力で順に飛ばしました。

ストーンは、 $E$ の力で飛ばされると、以下ようなふるまいをします。

道中に他のストーンがない場合、出発地点から距離 $E$ まで移動します

道中に他のストーンがあった場合、そのストーンを弾き飛ばします。つまり、衝突地点を座標とすると
- もともと動いていたストーンは座標 $s-1$ で停止します
- 弾き飛ばされたストーンは、座標 $s$ から力 $E-(s-1)$ で飛ばされます

このようなゲームをするにあたって、
$G$ 、 $N$ 、 $E_0, E_1, ... , E_{N-1}$ が与えられるとき、
$G$ に最も近いストーンの位置と、その番号（ストーンが何番目に飛ばされたか、の値）を答えてください。

Problem D2: Line of Delivery (Part 2) 解説

前回の記事でも書きましたが、僕はこの問題を解くことができませんでした。
というわけで、解けなかった問題の復習をした自分の軌跡をなぞる形で、この問題の解説をしていきたいと思います。

公式の Solution を読んでみる

コンテストが終了しているということで、公式での解法を Meta 社が書いてくれているものがあります。

英語を読むのが苦じゃない方なら原文をみるので十分かもしれませんが、要約を書きます。

力 $E$ でストーンを投げた場合、
ストーンが止まるまでには他のストーンに衝突が起こったりもするけれど、
最終的な石が止まる位置というのは、
ストーンがない座標のみを左から数えて $E$ 番目の位置である。
また、それ以前に存在していたストーンは、すべて座標が -1 される。

つまりは、特定の P に値を入れることと、P以前の値を1引くという操作を高速に（データ量に触れていませんが、この処理を $O(log N)$ で）計算できれば良い。こういうのに便利なデータ構造として Treap ってのがあるので、それをうまく使えば計算できるよ。

…と、書いてありました。

Treap とは？

Meta 社の解説でも Wikipedia のリンクが張ってあるので、さっそく Treap のページにとんでみましょう。

Treap - Wikipedia

ざっと上から読んでみると

In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys.

ということで、どうやら treap ってのは乱数をつかった平衡二分木と密接に関わりのあるもののようです。

の図を見ると、Search, Insert, Delete, が $O(log N)$ と書かれているし、ほぼほぼ二分木のように思われる。

なんなら Google 先生に聞いてみると

とのことだし、 Treap ≒ 平衡二分木と考えてよさそうです。

（ちなみに、これは後付けの説明で、僕は過去の競技プログラミング知識から軽く説明を見たところで
　「あー、完全平衡二分木ってあるよね、あんまりつかわないけど。それかなぁ」と考えてました)

さて、ここまで読んで僕は思いました。

…平衡二分木で、今回行いたい操作ができる気があんまりしないんだけど、どうなってるんだ？🤔

と。

他の人の解答を読んでみる

さて Treap が平衡二分木だとざっくり理解したところで、なんでそれで解けるのかがいまいちわからないので、ここでほかの参加者の解答を見てみようと思いいたります。

Meta Hacker Cup はほかの競技者の提出コードが公開されてるので、適当に上位層の解答を見てみることにします。

そうして出てきたコードがこのようなものになります。

int E[300000],s[300000];
int main() {
    int i;
    int t,T,N,G;
    scanf("%d",&T);
    for (t = 1; t <= T; t++) {
        scanf("%d %d",&N,&G);
        pii p = mp(2e9,-1);
        for (i = 0; i < N; i++) scanf("%d",&E[i]),E[i] -= N-i-1,s[i] = E[i];
        sort(s,s+N);
        for (i = 0; i < N; i++) s[i] += i;
        for (i = 0; i < N; i++) p = min(p,mp(abs(s[i]-G),-s[i]));
        int c = 0;
        for (i = 0; i < N; i++) c += (s[i] < -p.second);
        printf("Case #%d: %d %d\n",t,N-c,p.first);
    }
   
    return 0;
}

Treap ... どこ ... ？？？

同様に何個か解法を見てみたのですが、 Treap を用いている解答は復習してる当時は見つけることができませんでした*1。

というわけで、も少しほかの解法があるのではないか、といろいろと調べてみます。

公式 Solution を無視した解き方

たぶんいろいろな考え方はあると思うのですが、自分は以下のような考え方が納得できました。
盤面におけるストーンの位置エネルギー、みたいな概念を考えます。

ある盤面における、あるストーン S が座標 P にあるとき、このストーンの位置エネルギーとは、いったんストーン S を盤面から取り去った上で、ストーンがない座標のみを左から数えていったときに、座標 P が何個目にあるか？と定義します。

公式 Solution の方の図と見比べてみるとよいかもしれませんが、
力 $E$ で盤面に発射さた上で、玉突きなどされて最後まで動いていたストーンの位置の数え方と対応した概念ですね。

D1 問題のようなノリで発射された順番や衝突による停止を無視し、
$E$ で発射されたストーンは最後まで動いていたストーンの位置に移動すると解釈するなら、
力 $E$ で発射されたストーンは位置エネルギー E の場所にいる、といえます。

さて、このストーンの位置エネルギーはこの後どうなっていくでしょうか？

実のところ、この位置エネルギーは、この後ストーンが一つ発射されるごとに1減少すると考えることができます。

なぜならば、この後ストーンが一つ発射されたとして、

位置エネルギー $E$ の場所までストーンが到達していない場合 => ストーンの手前にある、ストーンのないマス目が一つ減るので、エネルギーが１減少する。
位置エネルギー $E$ の場所までストーンが到達している場合 => ストーンが１マス後ろに移動したと解釈することができるので、エネルギーが１減少する。

となるからです。

以上のことから、 $i$ 番目に力 $E$ で発射されたストーンは、 $N$ 個すべてのストーンが発射された後には、位置エネルギー $E - (N-1-i)$ の場所にいる、ということができます。

位置エネルギーはその手前のストーンの個数が分かれば座標へと変換することができるので、
あとは位置エネルギーを並べ替えて、エネルギーの低い順にストーンを配置しながら座標を確定させていけば、
最終的なストーンの座標一覧が取得できます。残りは D1 問題と同様です。

元のコードとも大差ありませんが、最終的に自分が練習で書いたコードも張っておきます。

#define rep(i, n) for (int i = 0; i < (n); i++)

typedef long long ll;
int main() {
    int Case;
    cin >> Case;
    int ans = 0;
    for (int ci = 0; ci < Case; ci++) {
        int N, G;
        cin >> N >> G;
        vector<int> E(N);
        rep(i, N) {
            cin >> E[i];
            E[i] -= N - 1 - i;
        }
        sort(E.begin(), E.end());
        int ind = 0;

        rep(i, N) {
            E[i] += i;
            if (abs(E[ind] - G) >= abs(E[i] - G)) {
                ind = i;
            }
        }

        cout << "Case #" << ci + 1 << ": " << N - ind << " " << abs(E[ind] - G)
             << endl;
    }
    return 0;
}

次回予告

以上で MetaHackerCup 2024 PracticeRound D2 を解くことができました。ちゃんちゃん。

と、してもよかったのですが、実はまだ一つ疑問が残っていましたね。

結局、 Treap を使ってこの問題を解くのってどうするんだ？

これです。

これは個人の経験の話になるのですが、
この手の問題って今回の時みたく「使わなくても解けちゃうんだよね」ってケースが多いせいで、
解けたところで満足してしまいがちだし、
実際に Treap を使ったらどうなるのか、みたいな情報が少くてよくわからないまま終わりがちです。

そこで今回はここに踏み込んで、次回からはこの問題を完全平衡二分木で解くことにチャレンジしたいと思います。

それでは次回をお楽しみに。

（実のところこれを書いている現時点では解けていません。頑張ります。対ヨロ）

*1:このブログを書き直す際に調べたら 1st の人の解法が Treap だったかもしれない？　未検証

やおよろず

ゆるふわな内容を書いても良い。と言うか何でも良い。そんな自由度の高いブログをめざします。

MetaHackerCup 2024 PracticeRound D 問題を語るその２：D2問題の解法と Treap の謎