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

はじめに

今年はちょっと時間がとれなさそうなので、一つのネタに絞ったうえで４回に分ける省エネスタイルです。

ここ数年は競技プログラミングからはだいぶ身を引いてるところではあるのですが、
Meta Hacker Cupの Practice Round には参加していて、
解けない問題を復習がてら少し戯れたことがあったので、その問題の話をしたいと思います。

競技プロうグラミングについては僕がこれまで何度も記事を書いていることから割愛。
さっそく本題に参りましょう。

Problem D1: Line of Delivery (Part 1)

今回話題にしたい問題は、D 問題の Line of Delivery という問題です。
この問題は D1 と D2 の二部構成になっており、本当に話をしたいほうは D2 (Part 2) の方なのですが、
設定が類似していたり、ある程度前提となる考え方が共通していたりもするので、 D1 から順を追って話をしていきます。

問題設定

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

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

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

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

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

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

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

D1 問題解説

察しの言い方は衝突時のふるまいの図を見たあたりですでにお気づきかもしれませんが、
衝突して玉が移動した結果は、ストーンの位置だけをみれば、衝突せずに素通りしたと思っても変わりがありません。　

つまり、最終的なストーンの位置だけに着目すると、ストーンは $E_0, E_1, ..., E_{N-1}$ の位置に存在するといえます。

このことから、 $G$ に最も近いストーンの位置は、 $E_i$ の中で最もGに近いものと等価になります。

さて、Gに最も近いストーンの位置はわかったとして、次に知るべきはその番号です。

先ほどまではストーンが弾き飛ばされることを無視して考えましたが、
改めてストーンが弾き飛ばされることに着目すると、
「先には飛ばしたストーンは、絶対に後に飛ばしたストーンよりも右側にある」ことに気づきます。

つまり、Eの大小がどうであったとしても、
一番最初に飛ばしたストーンはなんやかんや弾き飛ばされて一番遠くにいくし、
その次は二番目に飛ばしたストーンになるし…と、
ストーンを飛ばした順が早いものから、最終的には遠くの座標にあるということを意味します。

例えばこの例でいうと、最初に $E_0$ で飛ばされた石は最終的には $E_2$ の位置にある、ってこと。
というわけで、Gに一番近い座標が右から何番目にあるか、を答えることで、ストーンの番号を答えることが可能です。

D1 回答例

以上を踏まえると、以下のような感じで D1 はとくことができます。

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

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];

        sort(E.begin(), E.end());
        int ind = 0;
        rep(i, N) {
            if (abs(E[ind] - G) >= abs(E[i] - G)) {
                ind = i;
            }
        }

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

このコードでは、最初に $E$ をソートしてしまってから、 $G$ に一番近い位置とストーンの番号を答えるようにしています。
そこそこコンパクトに書けますね。

Problem D2: Line of Delivery (Part 2)

ここからが本題。D2問題です。

問題設定

英語を読むのが苦じゃない方なら原文の
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)$ で飛ばされます

D2 問題の難しさ

D1 問題のちょっとしたマイナーチェンジじゃーん、って思うかもしれませんが、
D1 の解法はストーンのサイズが０であることを前提としていたため、同じような考え方が使えません。

弾き飛ばされるストーンは座標 $s$ から力 $E-(s-1)$ で飛ばされるということは、
最終終着点は（そのあとに他のストーンがなければ） $E+1$ になります。

この点で、最終的なストーンの位置が $E_0, E_1, ... E_{N-1}$ と一致しないことになります。

というわけで、 $G$ に最も近い座標を探すだけでも大変そうだな、ということはぼんやり理解できるかと思います。

…さて、どうしましょう？

おわりに

「いきなり『おわりに』ってなんでやねん」って思われるかもしれませんが、今日の記事はここまでです。

ほら、競技プログラミングの記事って問題と解説を両方乗せてしまいがちだから、
読者が自分で問題を考える余地がない、みたいなところあるじゃないですか。
なので今回は問題を出したとこで終わってみて、次の内容を楽しみにしてもらおうかなと。
（...というのは建前で、本当の目的は冒頭にも書いた通り省エネなんですが）

良ければ考えながら次の記事を待ってもらえたらな、と思います。

ちなみに僕はこの問題をコンテスト時間中に解けませんでしたし、
調べて解法を理解こそしていますが、自力では解けなかったかなぁ、と思っています。
解けた人はめっちゃすごいです。競技プログラマーになろう。

ではまた次回。