【C++入門】2つの異なる区間から相異なる2点を見つけるプログラム

問題概要

x軸上の2本の線分を表す2つの区間 (l1, r1) と (l2, r2) が与えられます。ここで l1 < r1、l2 < r2 が成り立ちます。これらの線分は互いに交差したり、部分的に重なったり、完全に一致したりする可能性があります。

この問題では、a が区間 (l1, r1) 内に含まれ、b が区間 (l2, r2) 内に含まれ、かつ a と b が異なる値となるような2つの数 a、b を見つけることが求められます。

たとえば、l1 = 2、r1 = 6、l2 = 3、r2 = 4 が入力された場合、a = 2、b = 3 を出力できます。もちろん、条件を満たす他の組み合わせも正解として成立します。

解法のアルゴリズム

この問題は非常にシンプルな発想で解くことができます。各区間の左端（始点）に注目し、以下の手順に従います。

もし l1 と l2 が等しい場合：
    l1 を 1 増やす
l1 と l2 を出力する

なぜこれで正しいのか考えてみましょう。l1 と l2 が等しい場合でも、l1 < r1 という前提条件があるため、l1 を 1 増やした値は依然として区間 (l1, r1) の中に含まれます。また、l1 + 1 と l2 は必ず異なる値になります。一方、l1 と l2 が最初から異なる場合は、そのまま出力すればよいだけです。

実装例（C++）

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void solve(int l1, int r1, int l2, int r2) {
    if (l1 == l2)
        l1++;
    cout << l1 << ", " << l2;
}
int main() {
    int l1 = 2;
    int r1 = 6;
    int l2 = 3;
    int r2 = 4;
    solve(l1, r1, l2, r2);
}

入力

2, 6, 3, 4

出力

2, 3

まとめ

このアルゴリズムの計算量は O(1) であり、定数時間で答えを求められる非常に効率的な手法です。区間の左端同士を比較するだけで、必ず相異なる2点を見つけられる点がポイントです。競技プログラミングにおいても、こうした端点の性質を利用したシンプルな考察は頻出テクニックなので、ぜひ覚えておきましょう。