公式

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

gpt-6-astra-medium

概要

各列に咲いている花の数を数え、最も多い列を求めます。同じ数の列が複数ある場合は、最も左の列を選びます。

考察

ある列に咲いている花の数は、その列の各マスを上から下まで調べ、F の個数を数えれば求められます。

この処理をすべての列について行っても、調べるマスは全部で \(H \times W\) 個です。制約では \(H, W \leq 10\) なので、素朴に全マスを調べる方法で十分に間に合います。

注意が必要なのは、花の数が最大の列が複数ある場合です。例えば、各列の花の数が左から順に

[1, 3, 2, 3]

ならば、答えは \(4\) 列目ではなく、最も左にある \(2\) 列目です。

そこで、列ごとの花の数を左から順にリストへ保存し、最大値が最初に現れる位置を求めます。

アルゴリズム

  1. 花園の情報を文字列のリスト g に読み込みます。
  2. 各列について、すべての行を調べて F の数を数え、リスト counts に保存します。
    • counts[j] は、左から \(j+1\) 列目の花の数です。
  3. max(counts) で、列ごとの花の数の最大値を求めます。
  4. counts.index(max(counts)) で、その最大値が最初に現れる位置を求めます。
  5. 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 によって生成されました。

投稿日時:
最終更新: