三井住友信託銀行プログラミングコンテスト2019F - Interval Running

問題概要

問題文

高橋くんと青木くんが同じ方向に向かって走っている。

• 高橋くんは最初の$T _ 1$分間は分速$A _ 1$メートルで走り、続く$T _ 2$分間は分速$A _ 2$メートルで走る。
• 青木くんは最初の$T _ 1$分間は分速$B _ 1$メートルで走り、続く$T _ 2$分間は分速$B _ 2$メートルで走る。

二人は同時に同じ位置からスタートし、上記の動きを繰り返す。

高橋くんと青木くんが同じ位置に来る回数を求めよ。 無限回同じ位置に来る場合は、その旨を報告せよ。 ただし、スタート地点はカウントしない。

制約

• $1 \leq T _ i \leq 100000$
• $1 \leq A _ i \leq 10^{10}$
• $1 \leq B _ i \leq 10^{10}$
• $A _ i \neq B _ i$

解法

高橋くんと青木くんの速度によっては同じ位置に来る回数がかなり多くなるため、二人の位置をトレスして答えるのは間に合いません。 うまく計算する必要があります。

典型的な考え方として、複数物体の動きを追う問題に対して、相対値を考えるとうまく行くことがあります。 今回は、一方から見たもう一方の運動の相対速度を考えることで問題がシンプルになります。

$V _ i \coloneqq A _ i - B _ i$を考えます。 この値は、青木くんがスタート地点で静止しているとみなしたときの高橋くんの速度になります。

これにより、問題は次のように変化します。

高橋くんは、次の動きを繰り返す。

• 最初の$T _ 1$分間は分速$V _ 1$メートルで走り、続く$T _ 2$分間は分速$V _ 2$メートルで走る。

何回スタート地点に戻ってくるだろうか。

ここで、変更された問題においては高橋くんが負の座標に来ることがあることに注意してください。

まず、無限回になる条件は、最初の$T _ 1 + T _ 2$分間動いたあと、スタート地点に戻っていることです。 そうでない場合、1周期分のズレが十分な回数積み重なると、スタート地点に戻ってこれなくなるからです。

以降、有限回戻ってくるような場合について考えます。 このとき、「ある周回でスタート地点に戻ってこられるか」という問題を考えると、これは単調性があります。

これがなぜかと言われると、かっちり論理的に理由を説明できないです。(すみません) しかし、感覚的には次のような感じです。

• 高橋くんがスタート地点に戻ってこられるとき、振り子のような運動をする必要がある。ただし、この振り幅は右方向と左方向で差があるため、周回するごとにどんどん原点から離れていく。振り幅の差は一定であるから、一回原点に戻れなくなったら、それ以降も戻れない。

よって、戻ってこれなくなる周回がどこかを二分探索することで答えを求めることができます。

「振り子のような動きをしている」と言ったように、普通、高橋くんは1周期で2回スタート地点に戻ることになります。 2回戻ってくるというのは、すなわち次のようなことです。

• 元いた座標から最初の$T _ 1$分移動した座標を$X _ 1$、そこから$T _ 2$分移動した座標を$X _ 2$とする。このとき、$X _ 1$が$0$でなく、$X _ 1$と$X _ 2$の符号が異なる。

$X _ 1$が$0$であるとき、1周期で1回しかスタート地点に戻ってきていないことに注意してください。 上記のように、1周期で1回しかスタート地点に戻ってきていないときは、スタート地点に戻ってこられる最後の1回になります。 また、最初の1回目の移動では1回しかカウントされませんが、上記の判定では「2回戻ってくる動きである」と判定され、特別扱いする必要がなくなります。

具体的な実装としては、次のようになります。

bool f (long x) {
    x--;
    BigInt cur = one_cycle;
    cur *= x;
    cur += v[0] * T[0];

    BigInt nex = cur + v[1] * T[1];

    if (cur == 0) return false;

    int p = (0 <= cur) ? 0 : 1;
    int q = (0 <= nex) ? 0 : 1;

    return 0 < (p ^ q);
}

$f(x)$は「$x$周目の動きで2回戻ってこられるか？」を判定しています。 符号判定はxorでうまく処理しています。

実装例

import std;

void main () {
    int[2] T;
    long[2] A, B;
    T = readln.split.to!(int[2]);
    A = readln.split.to!(long[2]);
    B = readln.split.to!(long[2]);

    solve(T, A, B);
}

void solve (int[2] T, long[2] A, long[2] B) {
    long[2] v = [A[0] - B[0], A[1] - B[1]];

    long one_cycle = v[0] * T[0] + v[1] * T[1];

    if (one_cycle == 0) {
        writeln("infinity");
        return;
    }

    bool f (long x) {
        x--;
        BigInt cur = one_cycle;
        cur *= x;
        cur += v[0] * T[0];

        BigInt nex = cur + v[1] * T[1];

        if (cur == 0) return false;

        int p = (0 <= cur) ? 0 : 1;
        int q = (0 <= nex) ? 0 : 1;

        return 0 < (p ^ q);
    }

    long ok = 0, ng = 10L^^18;

    while (1 < abs(ok - ng)) {
        long mid = (ok + ng) / 2;
        if (f(mid)) {
            ok = mid;
        }
        else {
            ng = mid;
        }
    }

    long ans = 0;
    if (0 < ok) ans = 2 * ok - 1;

    // 最後ピッタリ踏むか？
    BigInt last = one_cycle;
    last *= ok;
    last += v[0] * T[0];
    if (last == 0) ans++;

    writeln(ans);
}

最初の余分なカウントを引いていること、最後に1回だけ戻ってくるケースを処理していることに注意してください。

終わりに

一回目にスタート地点にいるせいで、かなり誤答しました。 とてもむずかしかったです。 相対値を利用する問題はたくさんあるので、慣れていけたらいいと思います。