B - 花園の列 / Flower Garden Columns 解説 by admin 印刷ページ
gpt-6-astra-medium概要
各列に咲いている花の数を数え、最も多い列を求めます。同じ数の列が複数ある場合は、最も左の列を選びます。
考察
列ごとに F の個数を数えれば、花が最も多い列を比較できます。
すべてのマスを調べても、マスの数は最大で \(10 \times 10 = 100\) 個です。そのため、素直に全マスを調べる方法で十分に間に合います。
列ごとの花の数を配列 cnt に保存しましょう。cnt[j] は、左から \(j+1\) 列目の花の数を表します。各行を読み込み、その行の j 番目の文字が F なら cnt[j] を \(1\) 増やします。
注意が必要なのは、花の数が同じときの扱いです。列を左から順に調べ、現在の候補より花の数が多いときだけ候補を更新すれば、同数の場合は左側の列が残ります。
例えば、列ごとの花の数が \([2, 3, 3, 1]\) なら、最大値は \(3\) です。左から調べて同数では候補を更新しないことで、答えは \(2\) 列目になります。逆に、同数でも更新すると右側の列を選んでしまい、誤答になります。
アルゴリズム
- 長さ \(W\) の配列
cntを用意し、すべて \(0\) に初期化します。 - 各行の文字列を読み込みます。
- 各文字を調べ、
s[j]がFならcnt[j]を \(1\) 増やします。
- 各文字を調べ、
- 答えの候補を表す
bestを \(0\) にします。 jを \(1\) から \(W-1\) まで順に調べます。cnt[j] > cnt[best]のときだけ、bestをjに更新します。
best + 1を出力します。
全行の読み込み後、cnt には各列の花の総数が入っています。また、候補の探索では、調べた範囲で花が最も多い列のうち最も左の列が常に best に残ります。したがって、最後に求める列を出力できます。
計算量
- 時間計算量: \(O(HW)\)
全 \(HW\) マスを調べ、その後 \(W\) 列から最大値を探します。 - 空間計算量: \(O(W)\)
列ごとの個数を保存する配列と、読み込み中の \(1\) 行分の文字列を使用します。
実装のポイント
配列の添字は \(0\) 始まりですが、出力する列番号は \(1\) 始まりなので、
best + 1を出力します。最も左の列を優先するため、更新条件は
>=ではなく>にします。花が一つもない場合も、
bestが初期値の \(0\) のままなので、正しく \(1\) 列目が出力されます。各行は読み込んだ直後に集計できるため、花園全体を保存する必要はありません。
ソースコード
// 問題文から独立に実装: 行を読みながら列ごとのカウンタを更新し、最後に最大を探す
#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;
}
この解説は gpt-6-astra-medium によって生成されました。
投稿日時:
最終更新: