B - 花園の列 / Flower Garden Columns Editorial by admin Editorial for printing
swe-2-highSolution
Count the number of flowers in each column and answer the column with the most flowers (the leftmost in case of a tie).
Algorithm
- Initialize a counter array
cntof length \(W\) with zeros. - Read each row string \(S_i\); if its \(j\)-th character is
F, incrementcnt[j]. Rows are processed one at a time, so the whole grid is never stored. - Scan
cntfrom left to right to find the smallest indexbestattaining the maximum. Updating only whencnt[j] > cnt[best]keeps the leftmost column among ties. - Since the answer is 1-indexed, print
best + 1.
Proof of Correctness
Lemma 1: After step 2, for every \(j\), cnt[j] equals the total number of flowers in column \(j\).
Proof: cnt[j] starts at \(0\) and is incremented exactly once for each row \(i\) whose \(j\)-th character of \(S_i\) is F. Since F cells are precisely the cells with flowers, cnt[j] equals the flower count of column \(j\).
Lemma 2: After step 3, best is the smallest index at which cnt attains its maximum.
Proof: The scan proceeds in the order \(j = 1, 2, \ldots, W-1\) (with best initialized to \(0\)). Because best is updated only when cnt[j] > cnt[best], the loop invariant “best is the smallest index among \(0, \ldots, j\) where cnt attains its maximum over that range” is preserved. Equal values never trigger an update, so the smallest maximizing index is retained. After processing \(j = W-1\), best is the smallest index maximizing cnt over all columns.
Theorem: The output best + 1 is the leftmost column (1-indexed) with the maximum number of flowers.
Proof: By Lemma 1, cnt holds each column’s flower count; by Lemma 2, best is the smallest 0-indexed index attaining the maximum. Hence best + 1 is the required 1-indexed column number.
Complexity
- Time: \(O(HW)\), including reading the input.
- Space: \(O(W)\) for C++ and \(O(HW)\) for Python, including stored input and output arrays or strings.
posted:
last update: