数直線上で出会う2人の疲労を最小限に抑えるC++コード

問題の概要

2つの整数 a と b が与えられます。2人の友人が数直線（OX軸）上の位置 x = a と x = b にそれぞれ立っており、各友人は直線に沿って任意の方向へ1ずつ移動できます（移動回数に制限はありません）。移動による疲労は次のルールで増加します。1回目の移動で疲労が1増え、2回目の移動で2増え、以降も同様に1ずつ増えていきます。2人はOX軸上の同じ整数点で会いたいと考えています。このとき、2人の疲労の合計が最小になる値を求めましょう。

例えば、入力が a = 5、b = 10 の場合、出力は 9 になります。最適な移動方法の一つは次のとおりです。1人目の友人が右へ3歩、2人目の友人が左へ2歩移動すると、疲労の合計は 1 + 2 + 3 + 1 + 2 = 9 となります。

解法のアプローチ

この問題は数式を使えば O(1) で解くことができます。手順は以下のとおりです。

ans := |a - b|
sum := ans / 2
return (sum + (ans mod 2)) * (sum + 1)

考え方のポイント

2人の距離を d = |a - b| とすると、最適な出会いの地点は2人の中間付近です。ここで、1 + 2 + ... + k = k × (k + 1) / 2 という等差数列の和の公式を利用します。

• d が偶数の場合： 両者がそれぞれ d / 2 歩ずつ移動するのが最適です。疲労の合計は 2 × (d/2)(d/2 + 1) / 2 = (d/2) × (d/2 + 1) になります。
• d が奇数の場合： 片方が ⌈d/2⌉ 歩、もう片方が ⌊d/2⌋ 歩移動します。この場合、(⌊d/2⌋ + 1) × (⌊d/2⌋ + 1) となります。

式 (sum + (ans mod 2)) × (sum + 1) は、これら2つの場合を1つの式で統一的に表現しています。

実装例

理解を深めるために、C++での実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(int a, int b){
    int ans = abs(a - b);
    int sum = ans / 2;
    return (sum + (ans % 2)) * (sum + 1);
}
int main(){
    int a = 5;
    int b = 10;
    cout << solve(a, b) << endl;
}

入力

5, 10

出力

9

計算量

この解法は絶対値と整数演算のみを使用するため、時間計算量・空間計算量ともに O(1) です。入力の値が大きくなっても即座に答えを求められる点が大きな利点です。