B - 花園の列 / Flower Garden Columns Editorial by admin Editorial for printing
gpt-6-astra-mediumOverview
Count the number of flowers blooming in each column and find the column with the most flowers. If there are multiple columns with the same maximum count, choose the leftmost one.
Analysis
The number of flowers blooming in a given column can be found by inspecting each cell in that column from top to bottom and counting the number of Fs.
Even if we perform this process for all columns, the total number of cells to inspect is \(H \times W\). Since the constraints are \(H, W \leq 10\), a naive approach that checks all cells easily runs within the time limit.
A point of caution is when there are multiple columns with the maximum number of flowers. For example, if the flower counts for each column from left to right are
[1, 3, 2, 3]
then the answer is not the \(4\)-th column, but the leftmost one, which is the \(2\)-nd column.
Therefore, we store the flower counts for each column in a list from left to right and find the first position where the maximum value appears.
Algorithm
- Read the garden information into a list of strings
g. - For each column, check all rows to count the number of
Fs and store them in a listcounts.counts[j]is the number of flowers in the \((j+1)\)-th column from the left.
- Find the maximum number of flowers among the columns using
max(counts). - Find the first index where that maximum value appears using
counts.index(max(counts)). - Since Python uses \(0\)-based indexing, add \(1\) to the resulting index and output it.
Since we correctly count the number of flowers in all columns and choose the first column achieving the maximum, we obtain the leftmost column that satisfies the condition.
Complexity
- Time Complexity: \(O(HW)\)
- Inspecting all cells takes \(O(HW)\), and finding the maximum value and its position takes \(O(W)\) each.
- Space Complexity: \(O(HW)\)
- Storing the garden grid takes \(O(HW)\), and storing the flower counts for each column takes \(O(W)\).
Implementation Notes
sum(1 for i in range(h) if g[i][j] == 'F')counts the number ofFs in columnj.list.index(x)returns the first index where the valuexappears, naturally satisfying the condition “if there is a tie, choose the leftmost column”.The output requires a \(1\)-based column index, so be sure to add \(1\) to the index.
Even if there are no flowers at all, all elements in
countswill be \(0\), and the \(1\)-st column will be correctly selected.Source Code
# 問題文から独立に実装: 列ごとの F の数のリストで最大値の最初の位置
h, w = map(int, input().split())
g = [input() for _ in range(h)]
counts = [sum(1 for i in range(h) if g[i][j] == 'F') for j in range(w)]
print(counts.index(max(counts)) + 1)
This editorial was generated by gpt-6-astra-medium.
posted:
last update: