B - 花園の列 / Flower Garden Columns Editorial by admin Editorial for printing
gpt-6-astra-medium概要
各列に咲いている花の数を数え、最も多い列を求めます。同じ数の列が複数ある場合は、最も左の列を選びます。
考察
ある列に咲いている花の数は、その列の各マスを上から下まで調べ、F の個数を数えれば求められます。
この処理をすべての列について行っても、調べるマスは全部で \(H \times W\) 個です。制約では \(H, W \leq 10\) なので、素朴に全マスを調べる方法で十分に間に合います。
注意が必要なのは、花の数が最大の列が複数ある場合です。例えば、各列の花の数が左から順に
[1, 3, 2, 3]
ならば、答えは \(4\) 列目ではなく、最も左にある \(2\) 列目です。
そこで、列ごとの花の数を左から順にリストへ保存し、最大値が最初に現れる位置を求めます。
アルゴリズム
- 花園の情報を文字列のリスト
gに読み込みます。 - 各列について、すべての行を調べて
Fの数を数え、リストcountsに保存します。counts[j]は、左から \(j+1\) 列目の花の数です。
max(counts)で、列ごとの花の数の最大値を求めます。counts.index(max(counts))で、その最大値が最初に現れる位置を求めます。- Python の添字は \(0\) 始まりなので、求めた位置に \(1\) を足して出力します。
すべての列の花の数を正しく数え、その最大値を持つ最初の列を選ぶため、条件を満たす最も左の列が得られます。
計算量
- 時間計算量: \(O(HW)\)
- 全マスの確認に \(O(HW)\)、最大値とその位置の探索にそれぞれ \(O(W)\) かかります。
- 空間計算量: \(O(HW)\)
- 花園の保存に \(O(HW)\)、各列の花の数の保存に \(O(W)\) 使用します。
実装のポイント
sum(1 for i in range(h) if g[i][j] == 'F')は、列jにあるFの個数を数えています。list.index(x)は、値xが最初に現れる添字を返すため、「同数なら最も左」という条件を満たせます。出力は \(1\) 始まりの列番号なので、添字に \(1\) を足すことを忘れないようにします。
花が一つもない場合も、
countsの要素はすべて \(0\) となり、正しく \(1\) 列目が選ばれます。ソースコード
# 問題文から独立に実装: 列ごとの 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)
この解説は gpt-6-astra-medium によって生成されました。
posted:
last update: