公式

B - 花園の列 / Flower Garden Columns 解説 by admin 印刷ページ

gpt-6-astra-medium

Overview

Count the number of blooming flowers in each column and find the column with the most flowers. If there are multiple columns with the same maximum number, choose the leftmost column.

Analysis

We can find the number of flowers in each column by inspecting each cell and incrementing the flower count for that column whenever we find an F.

Both \(H\) and \(W\) are at most \(10\), so there are at most \(100\) cells to inspect in total. This naive approach is sufficiently fast.

Care is needed when multiple columns have the same number of flowers. For example, suppose the number of flowers in each column is as follows:

Column number:     1  2  3  4
Number of flowers: 2  3  1  3

The maximum value is \(3\), which appears in the \(2\)nd and \(4\)th columns. The answer is the leftmost one among them, which is column \(2\).

To satisfy this condition, iterate through the columns from left to right and update the candidate column only when the current column has strictly more flowers than the current candidate. By not updating on ties, the leftmost column will remain as the candidate.

Algorithm

In the code, we use \(0\)-based indices from \(0\) to \(W-1\) for the columns.

  1. Initialize an array cnt of length \(W\) with all elements set to \(0\) to record the number of flowers in each column.
  2. Iterate through each row’s string from left to right.
    • If the character at index j is F, increment cnt[j] by \(1\).
  3. Initialize the candidate index for the answer, best, to \(0\).
  4. Iterate through columns with indices from \(1\) to \(W-1\):
    • If cnt[j] > cnt[best], update best to j.
    • Do not update if they are equal.
  5. Since the problem uses \(1\)-based column numbering, output best + 1.

At any point during the iteration, best points to the leftmost column with the maximum number of flowers among the columns checked so far. Therefore, once all columns have been examined, we obtain the correct answer.

Complexity

  • Time complexity: \(O(HW)\)
    • We aggregate across all \(HW\) cells and compare \(W\) columns.
  • Space complexity: \(O(HW)\)
    • In the provided code, the entire input is stored in data. Excluding the storage for the input, the auxiliary space used is \(O(W)\) for the array cnt.

Key Implementation Points

  • Use > for the comparison. If you use >=, the candidate will be updated on ties, resulting in selecting the rightmost column.

  • Since Python uses \(0\)-based indexing, add \(1\) when printing the answer.

  • If there are no flowers at all, all elements in cnt will be \(0\). Even in this case, best remains its initial value of \(0\), correctly outputting column \(1\).

    Source Code

import sys

def main():
    data = sys.stdin.read().split()
    H, W = int(data[0]), int(data[1])
    cnt = [0] * W
    for i in range(H):
        S = data[2 + i]
        for j, c in enumerate(S):
            if c == 'F':
                cnt[j] += 1
    best = 0
    for j in range(1, W):
        if cnt[j] > cnt[best]:
            best = j
    print(best + 1)

main()

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

投稿日時:
最終更新: