Overview

Find the width of each gap from the differences between adjacent board positions, and output the index of the widest gap. If there are multiple gaps with the maximum width, choose the leftmost one.

Analysis

The width of the \(i\)-th gap from the left is \(A_{i+1}-A_i\). For each gap, we can determine whether “this gap is the answer” by comparing it with all other gaps.

Letting \(g\) be the width of the gap currently under consideration, the conditions for it to be the answer are as follows:

• There is no gap to its left with a width greater than or equal to \(g\).
• There is no gap to its right with a width strictly greater than \(g\).

The conditions differ between the left and right sides because when gaps have the same width, the leftmost one takes priority. If there is a gap with the same width to its left, the gap under consideration cannot be the answer. On the other hand, it is fine if there is a gap with the same width to its right.

For example, when the board positions are \([0,3,8,13]\), the gap widths are \([3,5,5]\). The maximum width is \(5\), but the answer is the \(2\)nd gap from the left.

If we overwrite the answer whenever we find a gap equal to the maximum width, we would end up choosing the rightmost one, resulting in an incorrect answer. Care must be taken when handling gaps of the same width.

Furthermore, even with the naive approach of comparing all pairs of gaps, the number of comparisons is at most \((N-1)^2\). Since \(N \leq 100\), an exhaustive search as presented in the code runs well within the time limit.

Algorithm

In the code, arrays are 0-indexed. The gap corresponding to index \(i\) is the \((i+1)\)-th gap from the left.

1. Read the board positions into an array a.
2. In the order \(i=0,1,\ldots,N-2\), check each gap as a candidate for the answer:
   • Let its width be \(g=a[i+1]-a[i]\).
   • Initialize a boolean flag ok to true, indicating whether it is a valid candidate.
3. For every gap \(j\), compute its width \(h=a[j+1]-a[j]\):
   • If \(j<i\) and \(h \geq g\), set ok to false.
   • If \(j>i\) and \(h>g\), set ok to false.
4. If ok is still true after the comparisons, print \(i+1\) and terminate.

For a gap where ok remains true, there is no strictly wider gap to either side, and no gap of equal width to its left. Therefore, this is the “leftmost gap among those with the maximum width.”

Moreover, the leftmost gap with the maximum width always satisfies this condition, so an answer is guaranteed to be found.

Complexity

• Time Complexity: \(O(N^2)\)
  For each gap, we compare it with all gaps.
• Space Complexity: \(O(N)\)
  We store the board positions in an array. The additional memory besides the array is \(O(1)\).

Implementation Notes

• While there are \(N\) boards, there are only \(N-1\) gaps. By setting the loop condition to i + 1 < n, we prevent a[i + 1] from going out of bounds.

• The comparison with the left side uses h >= g, while the comparison with the right side uses h > g. This difference enforces the condition of choosing the leftmost gap in case of ties.

• Array indexing is 0-based, but the output index is 1-based, so output i + 1.

• Reinitialize ok to true each time we check a new candidate gap.

  Source Code

// 問題文から独立に実装: 隙間ごとに「これより広い隙間が他にないか、左により狭くない同幅がないか」を確認
#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; }
    }
}

---

This editorial was generated by gpt-6-astra-medium.