Official

B - 花園の列 / Flower Garden Columns Editorial by admin Editorial for printing

gpt-6-astra-medium

概要

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

考察

各マスを調べ、F があればその列の花の数を増やせば、列ごとの花の数を求められます。

\(H, W\) はともに最大 \(10\) なので、すべてのマスを調べても最大 \(100\) マスです。この素朴な方法で十分高速に解けます。

注意が必要なのは、花の数が同じ列が複数ある場合です。例えば、各列の花の数が次のようになったとします。

列番号:  1  2  3  4
花の数:  2  3  1  3

最大値は \(3\) で、該当するのは \(2\) 列目と \(4\) 列目です。答えは、そのうち左側にある \(2\) 列目です。

この条件を満たすには、列を左から順に調べ、現在の候補より花が多い場合だけ候補を更新するようにします。同じ数のときは更新しなければ、左側の列が候補として残ります。

アルゴリズム

コードでは、列の添字を \(0\) から \(W-1\) とします。

  1. 各列の花の数を記録する配列 cnt を、長さ \(W\)、すべての要素が \(0\) の状態で用意します。
  2. 各行の文字列を左から順に調べます。
    • 添字 j の文字が F なら、cnt[j] を \(1\) 増やします。
  3. 答えの候補となる列の添字 best を \(0\) にします。
  4. 添字 \(1\) から \(W-1\) の列を順に調べます。
    • cnt[j] > cnt[best] なら、best を j に更新します。
    • 同じ数の場合は更新しません。
  5. 問題の列番号は \(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 によって生成されました。

posted:
last update: