B - 花園の列 / Flower Garden Columns 解説 by admin 印刷ページ
gpt-6-astra-medium概要
各列に咲いている花の数を数え、最も多い列を求めます。同じ数の列が複数ある場合は、最も左の列を選びます。
考察
各マスを調べ、F があればその列の花の数を増やせば、列ごとの花の数を求められます。
\(H, W\) はともに最大 \(10\) なので、すべてのマスを調べても最大 \(100\) マスです。この素朴な方法で十分高速に解けます。
注意が必要なのは、花の数が同じ列が複数ある場合です。例えば、各列の花の数が次のようになったとします。
列番号: 1 2 3 4
花の数: 2 3 1 3
最大値は \(3\) で、該当するのは \(2\) 列目と \(4\) 列目です。答えは、そのうち左側にある \(2\) 列目です。
この条件を満たすには、列を左から順に調べ、現在の候補より花が多い場合だけ候補を更新するようにします。同じ数のときは更新しなければ、左側の列が候補として残ります。
アルゴリズム
コードでは、列の添字を \(0\) から \(W-1\) とします。
- 各列の花の数を記録する配列
cntを、長さ \(W\)、すべての要素が \(0\) の状態で用意します。 - 各行の文字列を左から順に調べます。
- 添字
jの文字がFなら、cnt[j]を \(1\) 増やします。
- 添字
- 答えの候補となる列の添字
bestを \(0\) にします。 - 添字 \(1\) から \(W-1\) の列を順に調べます。
cnt[j] > cnt[best]なら、bestをjに更新します。- 同じ数の場合は更新しません。
- 問題の列番号は \(1\) 始まりなので、
best + 1を出力します。
各列を調べた時点で、best は「そこまでに調べた列のうち、花が最多で最も左の列」を指します。したがって、すべての列を調べ終えたときに正しい答えが得られます。
計算量
- 時間計算量: \(O(HW)\)
- 全 \(HW\) マスの集計と、\(W\) 列の比較を行います。
- 空間計算量: \(O(HW)\)
- 提示コードでは入力全体を
dataに保持します。入力の保持を除く追加の作業領域は、配列cntの \(O(W)\) です。
- 提示コードでは入力全体を
実装のポイント
比較には
>を使います。>=にすると、同数の場合にも候補を更新してしまい、最も右の列を選ぶ原因になります。Python の添字は \(0\) 始まりなので、出力時に \(1\) を足します。
花が一つもない場合、
cntはすべて \(0\) です。この場合もbestは初期値の \(0\) のままとなり、正しく \(1\) 列目が出力されます。ソースコード
import sys
def main():
data = sys.stdin.read().split()
H, W = int(data[0]), int(data[1])
cnt = [0] * W
for i in range(H):
S = data[2 + i]
for j, c in enumerate(S):
if c == 'F':
cnt[j] += 1
best = 0
for j in range(1, W):
if cnt[j] > cnt[best]:
best = j
print(best + 1)
main()
この解説は gpt-6-astra-medium によって生成されました。
投稿日時:
最終更新: