概要

隣り合う板の位置の差から隙間の幅を求め、最も広い隙間の番号を出力します。同じ最大幅の隙間が複数ある場合は、最も左にあるものを選びます。

考察

左から \(i\) 番目の隙間の幅は、\(A_{i+1}-A_i\) です。それぞれの隙間について、「この隙間が答えになるか」を、ほかのすべての隙間と比較して判定します。

注目している隙間の幅を \(g\) とすると、答えになるための条件は次のとおりです。

• 左側に幅が \(g\) 以上の隙間がないこと
• 右側に幅が \(g\) より大きい隙間がないこと

左側と右側で条件が異なるのは、同じ幅なら左の隙間を優先するためです。左側に同じ幅の隙間があれば、注目している隙間は答えにはなりません。一方、右側に同じ幅の隙間があっても問題ありません。

例えば、板の位置が \([0,3,8,13]\) の場合、隙間の幅は \([3,5,5]\) です。最大幅は \(5\) ですが、答えは左側の \(2\) 番目の隙間になります。

最大幅と等しい隙間を見つけるたびに答えを上書きすると、最も右のものを選んでしまい、誤答になります。同幅の場合の扱いに注意が必要です。

なお、すべての隙間同士を比較する素朴な方法でも、比較回数は高々 \((N-1)^2\) 回です。\(N \leq 100\) なので、提示されたコードの全探索で十分間に合います。

アルゴリズム

コードでは配列を \(0\) 始まりで扱います。添字 \(i\) に対応する隙間は、左から \(i+1\) 番目の隙間です。

1. 板の位置を配列 a に読み込みます。
2. \(i=0,1,\ldots,N-2\) の順に、各隙間を答えの候補として調べます。
   • 幅を \(g=a[i+1]-a[i]\) とします。
   • 候補として有効かを表す ok を true にします。
3. すべての隙間 \(j\) について、幅 \(h=a[j+1]-a[j]\) を計算します。
   • \(j<i\) かつ \(h \geq g\) なら、ok を false にします。
   • \(j>i\) かつ \(h>g\) なら、ok を false にします。
4. 比較後も ok が true なら、\(i+1\) を出力して終了します。

ok が true の隙間には、それより広い隙間が左右のどちらにもなく、同じ幅の隙間が左側にもありません。したがって、これは「最大幅の隙間のうち最も左のもの」です。

また、最大幅の隙間のうち最も左のものは必ずこの条件を満たすので、答えは必ず見つかります。

計算量

• 時間計算量: \(O(N^2)\)
  各隙間について、すべての隙間と比較します。
• 空間計算量: \(O(N)\)
  板の位置を配列に保存します。配列以外の追加領域は \(O(1)\) です。

実装のポイント

• 板は \(N\) 枚ですが、隙間は \(N-1\) 個です。ループ条件を i + 1 < n とすることで、a[i + 1] が配列の範囲外にならないようにします。

• 左側との比較は h >= g、右側との比較は h > g です。この違いが、同幅なら最も左を選ぶ条件を表しています。

• 配列の添字は \(0\) 始まりですが、出力する番号は \(1\) 始まりなので、i + 1 を出力します。

• ok は、候補の隙間を変えるたびに true に初期化します。

  ソースコード

// 問題文から独立に実装: 隙間ごとに「これより広い隙間が他にないか、左により狭くない同幅がないか」を確認
#include <iostream>
#include <vector>
int main() {
    int n; std::cin >> n;
    std::vector<int> a(n);
    for (int& x : a) std::cin >> x;
    for (int i = 0; i + 1 < n; ++i) {
        int g = a[i + 1] - a[i];
        bool ok = true;
        for (int j = 0; j + 1 < n; ++j) {
            int h = a[j + 1] - a[j];
            if (j < i && h >= g) ok = false;
            if (j > i && h > g) ok = false;
        }
        if (ok) { std::cout << i + 1 << std::endl; return 0; }
    }
}

---

この解説は gpt-6-astra-medium によって生成されました。