Overview

Find the row with the most empty seats. If there are multiple rows with the same maximum number of empty seats, choose the topmost row among them.

Analysis

Since every row has \(W\) seats, the following relation holds for each row:

\(\text{Number of empty seats} = W - \text{Number of occupied seats}\)

Therefore, the row with the most empty seats is the row with the fewest occupied seats. In the provided code, we count the number of os in each row and find the row where this count is minimized.

For example, consider the following seating arrangement:

o.o.
....
.o..
....

The number of os in each row is \(2, 0, 1, 0\), respectively. The minimum occurs in rows \(2\) and \(4\), so the topmost one, row \(2\), is the answer.

Even if we examine all seats, there are at most \(10 \times 10 = 100\) seats, so a naive brute-force search is sufficiently fast.

One detail to be careful about is how to handle ties. When checking rows from top to bottom, if we update the answer even when the count equals the current minimum, we would select a lower row, resulting in a wrong answer. By updating only when the count is strictly less than the current minimum, we can keep the topmost row.

Algorithm

1. Initialize bestSeated, the minimum number of occupied seats found so far, to a sufficiently large value. Record the answer row index in idx.
2. For each row \(i = 1, 2, \ldots, H\) from top to bottom, perform the following:
   • Read the string for that row.
   • Count the number of os in the string, and let this count be seated.
   • Only when seated < bestSeated, update bestSeated to seated and idx to \(i\).
3. Output idx.

Through this process, after inspecting each row, idx represents “the topmost row among all rows checked so far that has the minimum number of occupied seats.” Therefore, idx after checking all rows is the desired answer.

Complexity

• Time complexity: \(O(HW)\)
  We inspect \(W\) characters for each of the \(H\) rows.
• Space complexity: \(O(W)\)
  We only store a string of length \(W\) and a constant number of variables at any given time.

Key Implementation Points

• The initial value of bestSeated must be strictly greater than the maximum possible number of occupied seats, \(W\). The code uses 1 << 30, ensuring it is guaranteed to be updated on the first row.

• The update condition must be seated < bestSeated. Using <= would cause ties to be overwritten by lower rows.

• Since the required row index is \(1\)-based, the loop iterating over the rows in the code also starts from \(1\).

• Even if there are no empty seats at all, all rows will have the same number of occupied seats, so row \(1\) will be correctly chosen.

  Source Code

// 問題文から独立に実装: 着席数が最も少ない行（同数なら最初）を探す
#include <iostream>
#include <string>
int main() {
    int h, w; std::cin >> h >> w;
    int bestSeated = 1 << 30, idx = 0;
    for (int i = 1; i <= h; ++i) {
        std::string s; std::cin >> s;
        int seated = 0;
        for (int j = 0; j < w; ++j) if (s[j] == 'o') seated++;
        if (seated < bestSeated) { bestSeated = seated; idx = i; }
    }
    std::cout << idx << std::endl;
}

---

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