Overview

Count the number of empty seats . in each row and find the row with the maximum number of empty seats. If there are multiple rows with the maximum number of empty seats, answer with the topmost row.

Analysis

To decide which row to sit in, it is sufficient to know only how many empty seats there are in each row. There is no need to check the specific positions of the empty seats.

Even with a naive approach of checking every seat, the total number of seats to inspect is at most \(10 \times 10 = 100\), which easily runs well within the time limit.

Care must be taken when multiple rows have the maximum number of empty seats. For example, if the counts of empty seats from top to bottom are \([2, 3, 3]\), the answer is the \(2\)nd row. If you overwrite the answer every time you find a maximum value, you might end up selecting a lower row.

Therefore, we can store the count of empty seats for each row from top to bottom in a list and find the first occurrence of the maximum value. This allows us to select the topmost row.

Algorithm

1. Read \(H, W\).
2. For each row’s string, count the number of empty seats using count('.') and store it in a list empty from top to bottom.
3. Find the maximum number of empty seats using max(empty).
4. Find the position where this maximum value first appears using empty.index(max(empty)).
5. Since list indices are \(0\)-based, add \(1\) to the found position and output it.

Since empty is ordered from top to bottom, the first occurrence of the maximum value corresponds to the topmost row among those with the maximum number of empty seats.

Complexity

• Time Complexity: \(O(HW)\)
  We inspect \(W\) characters for each row, repeated \(H\) times. Finding the maximum value and its position each takes \(O(H)\), resulting in an overall time complexity of \(O(HW)\).
• Space Complexity: \(O(H + W)\)
  \(O(H)\) space is used for the list of empty seat counts, and temporarily \(O(W)\) space is used to store each row’s string while reading input.

Implementation Notes

• The character representing an empty seat is .. Count the number of ., not o.

• Python’s list.index() returns the index of the first occurrence of the specified value, which satisfies the tie-breaking requirement.

• The row number to output is \(1\)-based, so remember to add \(1\) to the index.

• Even if all seats are occupied, the empty seat counts will all be \(0\), and the \(1\)st row will be correctly selected.

  Source Code

# 問題文から独立に実装: 各行の空席数のリストで最大値の最初の位置
h, w = map(int, input().split())
empty = [input().count('.') for _ in range(h)]
print(empty.index(max(empty)) + 1)

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