C++で解く：複数の時計の時刻から可能な限り最小の時間差を見つけるプログラム

問題概要

N個の要素を持つ配列Dがあるとします。あるコードフェスティバルには、Amalを含めて合計N+1人の参加者がいます。Amalが調べたところ、自分の街の地元時刻とi番目の人の街の地元時刻との時差はD[i]時間であることが分かりました。

2つの都市AとBの時差は、次のように定義されます。都市Aの地元時刻が0時である瞬間に、都市Bの地元時刻がd時だった場合、この2つの都市の時差は「d」と「24−d」のうち小さい方の値となります。ここでは24時間表記を使用します。

Amalは、N+1人の中から任意の2人を選んだすべてのペアについて、それぞれの都市間の時差を書き出しました。これらの中で最も小さい時差をs時間とするとき、sとしてあり得る最大値を求めるのが本問題の目的です。

たとえば、入力が D = [7, 12, 8] のとき、出力は4になります。これは、2番目と3番目の人の都市間の時差が4時間になるためです。

解法の考え方

この問題は、24時間を1周とする「円環」上に各都市の時刻を配置する問題として捉えることができます。基準となるAmalの都市は0時の位置に固定し、残りの各都市はD[i]または24−D[i]の位置に置けます。全ペアの中の最小時差sを最大化するには、配列Dをソートしたうえで、差を円環の両側に交互に振り分けて配置し、隣接する時刻同士の最小間隔を求めます。

アルゴリズムの手順

以下の手順に従って問題を解きます。

n := D のサイズ
配列 D をソートする
配列 t を定義する
t の末尾に 0 を挿入する
i := 0 で初期化し、i < n の間 i を 1 ずつ増やしながら繰り返す：
   i mod 2 が 0 の場合：
      t の末尾に D[i] を挿入する
   そうでない場合：
      t の末尾に 24 - D[i] を挿入する
配列 t をソートする
ans := 無限大
i := 1 で初期化し、i < t のサイズ の間 i を 1 ずつ増やしながら繰り返す：
   ans := ans と t[i] - t[i - 1] の最小値
ans を返す

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> D) {
    int n = D.size();
    sort(D.begin(), D.end());
    vector<int> t;
    t.push_back(0);
    for (int i = 0; i < n; i++){
        if (i % 2 == 0)
            t.push_back(D[i]);
        else
            t.push_back(24 - D[i]);
    }
    sort(t.begin(), t.end());
    int ans = 1e9;
    for (int i = 1; i < t.size(); i++){
        ans = min(ans, t[i] - t[i - 1]);
    }
    return ans;
}
int main(){
   vector<int> D = { 7, 12, 8 };
   cout << solve(D) << endl;
}

入力

{ 7, 12, 8 }

出力

4

動作の解説

入力 D = {7, 12, 8} を使って処理を追ってみます。まずDをソートすると {7, 8, 12} になります。次に、t は 0 で初期化され、偶数インデックスには D[i]、奇数インデックスには 24−D[i] を順に追加していきます。

• i = 0（偶数）→ 7 を追加 → t = {0, 7}
• i = 1（奇数）→ 24 − 8 = 16 を追加 → t = {0, 7, 16}
• i = 2（偶数）→ 12 を追加 → t = {0, 7, 16, 12}

t をソートすると {0, 7, 12, 16} となり、隣接要素間の差はそれぞれ 7、5、4 です。したがって最小値は4となり、これが正解として出力されます。

まとめ

本記事では、複数の都市間の時差情報から、全ペアの中の最小時差としてあり得る最大値を求める問題をC++で解きました。ポイントは、(1) 配列をソートする、(2) 時差を円環上に交互に配置する、(3) ソート後の隣接差の最小値を答えとする、という3点です。計算量はソートが支配的となり、O(N log N) で効率よく求解できるのが特徴です。