B - 花園の列 / Flower Garden Columns 解説 by admin 印刷ページ
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 number of flowers, choose the leftmost one.
Analysis
By counting the number of F’s in each column, we can compare which column has the most flowers.
Even if we inspect every cell, the total number of cells is at most \(10 \times 10 = 100\). Therefore, a straightforward approach that checks all cells is well within the time limit.
Let us store the number of flowers in each column in an array cnt. Here, cnt[j] represents the number of flowers in the \((j+1)\)-th column from the left. We read each row, and if the j-th character of that row is F, we increment cnt[j] by \(1\).
One thing to be careful about is how to handle ties when the number of flowers is the same. If we inspect the columns from left to right and update the candidate only when the count is strictly greater than the current candidate, the leftmost column will be kept in case of a tie.
For example, if the counts of flowers per column are \([2, 3, 3, 1]\), the maximum count is \(3\). By checking from left to right and not updating on ties, the answer will be the \(2\)nd column. Conversely, updating on ties would select the column to the right, resulting in a wrong answer.
Algorithm
- Prepare an array
cntof length \(W\) and initialize all elements to \(0\). - Read the string for each row.
- Inspect each character; if
s[j]isF, incrementcnt[j]by \(1\).
- Inspect each character; if
- Initialize
best, which represents the candidate for the answer, to \(0\). - Iterate over
jfrom \(1\) to \(W-1\) in order.- Update
besttojonly whencnt[j] > cnt[best].
- Update
- Output
best + 1.
After reading all rows, cnt contains the total number of flowers in each column. Furthermore, during the search for the candidate, best always retains the leftmost column among those with the maximum count within the checked range. Therefore, we can correctly output the desired column at the end.
Complexity
- Time complexity: \(O(HW)\)
We inspect all \(HW\) cells and then find the maximum among the \(W\) columns. - Space complexity: \(O(W)\)
We use an array to store the counts for each column and a string to read one row at a time.
Implementation Notes
Array indices are \(0\)-based, but the column numbers in the output must be \(1\)-based, so output
best + 1.To prioritize the leftmost column, the update condition must be
>, not>=.Even if there are no flowers at all,
bestremains its initial value of \(0\), correctly outputting the \(1\)st column.Since each row can be tallied immediately after it is read, there is no need to store the entire flower garden in memory.
Source Code
// 問題文から独立に実装: 行を読みながら列ごとのカウンタを更新し、最後に最大を探す
#include <iostream>
#include <string>
#include <vector>
int main() {
int h, w; std::cin >> h >> w;
std::vector<int> cnt(w, 0);
for (int i = 0; i < h; ++i) {
std::string s; std::cin >> s;
for (int j = 0; j < w; ++j) if (s[j] == 'F') cnt[j]++;
}
int best = 0;
for (int j = 1; j < w; ++j) if (cnt[j] > cnt[best]) best = j;
std::cout << best + 1 << std::endl;
}
This editorial was generated by gpt-6-astra-medium.
投稿日時:
最終更新: