Overview

Find the differences in positions between all adjacent boards, and output the number (1-based index) of the gap where this difference is maximized. If there are multiple gaps with the maximum width, choose the leftmost one.

Analysis

The width of the \(i\)-th gap from the left can be calculated as \(A_{i+1}-A_i\) using the positions of the boards on either side. Therefore, we can find the answer by examining all \(N-1\) gaps.

In this problem, a naive approach of checking all gaps is sufficiently fast. However, note that if there are multiple gaps with the maximum width, we must choose the leftmost gap. If we update the answer every time we find a gap with a width equal to the maximum, we would end up choosing a gap further to the right, which would be incorrect.

In our code, we store the widths of the gaps from left to right in a list gaps. Since Python’s index method returns the first occurrence of the specified value, finding the maximum value first and then looking up its position using index allows us to select the leftmost gap.

For example, when the board positions are \([0,3,8,13]\), the gap widths are \([3,5,5]\). The maximum width is \(5\), which occurs at the \(2\)nd and \(3\)rd gaps from the left. Among them, the leftmost one, the \(2\)nd gap, is the answer.

Algorithm

1. Read the number of boards n and the list of positions a.
2. Compute each gap’s width a[i + 1] - a[i] and store them in the list gaps from left to right.
3. Find the maximum width with max(gaps).
4. Find the index of the first occurrence of the maximum width using gaps.index(max(gaps)).
5. Since indices are \(0\)-based and gap numbers are \(1\)-based, add \(1\) and output the result.

gaps contains the widths of all gaps in order from left to right. By choosing the position where the maximum value first appears, we can correctly determine the leftmost gap among those with the maximum width.

Complexity

• Time complexity: \(O(N)\)
  Creating the list of gaps, finding the maximum value, and searching for the first occurrence each take \(O(N)\) time.
• Space complexity: \(O(N)\)
  The board positions and gap widths are stored in lists.

Implementation Notes

• Since there are \(N-1\) gaps, use range(n - 1) in list comprehensions.

• Because index returns the first position found, no extra handling is required even if there are multiple occurrences of the maximum value.

• Don’t forget to add + 1 when printing the answer.

• Since \(N \geq 2\), gaps is guaranteed to contain at least \(1\) element, so max(gaps) can be safely used.

  Source Code

# 問題文から独立に実装: 隙間のリストを作り最大の最初の位置
n = int(input())
a = list(map(int, input().split()))
gaps = [a[i + 1] - a[i] for i in range(n - 1)]
print(gaps.index(max(gaps)) + 1)

---

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