概要

隣り合う板の位置の差をすべて求め、その差が最大になる隙間の番号を出力します。最大の幅の隙間が複数ある場合は、最も左にあるものを選びます。

考察

左から \(i\) 番目の隙間の幅は、両端の板の位置を使って \(A_{i+1}-A_i\) と計算できます。したがって、\(N-1\) 個の隙間をすべて調べれば答えが求まります。

この問題では、すべての隙間を調べる素朴な方法で十分高速に解けます。ただし、最大の幅が複数あるときは、最も左の隙間を選ぶことに注意が必要です。最大値と同じ幅を見つけるたびに答えを更新すると、右側の隙間を選んでしまい、誤答になります。

今回のコードでは、隙間の幅を左から順にリスト gaps に格納します。Python の index は指定した値が最初に現れる位置を返すため、最大値を求めてから index でその位置を調べれば、最も左の隙間を選べます。

例えば、板の位置が \([0,3,8,13]\) のとき、隙間の幅は \([3,5,5]\) です。最大の幅は \(5\) で、左から \(2\) 番目と \(3\) 番目にあります。そのうち最も左の \(2\) 番目が答えです。

アルゴリズム

1. 板の枚数 n と、位置のリスト a を読み込みます。
2. 各隙間の幅 a[i + 1] - a[i] を計算し、左から順にリスト gaps に格納します。
3. max(gaps) で最大の幅を求めます。
4. gaps.index(max(gaps)) で、最大の幅が最初に現れる添字を求めます。
5. 添字は \(0\) 始まり、隙間の番号は \(1\) 始まりなので、\(1\) を加えて出力します。

gaps にはすべての隙間の幅が左から順に入っています。その最大値が最初に現れる位置を選ぶため、最も広い隙間のうち最も左のものを正しく求められます。

計算量

• 時間計算量: \(O(N)\)
  隙間のリストの作成、最大値の取得、最初の位置の探索がそれぞれ \(O(N)\) です。
• 空間計算量: \(O(N)\)
  板の位置と隙間の幅をリストに保存します。

実装のポイント

• 隙間は \(N-1\) 個なので、リスト内包表記では range(n - 1) を使います。

• index は最初に見つかった位置を返すため、同じ最大値が複数あっても追加の処理は不要です。

• 出力時の + 1 を忘れないようにしましょう。

• \(N \geq 2\) なので、gaps には必ず \(1\) 個以上の要素があり、max(gaps) を使用できます。

  ソースコード

# 問題文から独立に実装: 隙間のリストを作り最大の最初の位置
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)

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