B - 花園の列 / Flower Garden Columns 解説 by admin 印刷ページ
swe-2-high解法
各列に咲いている花の数を数え、最も多い列(同数なら最も左)を答えればよい。
アルゴリズム
- 長さ \(W\) のカウンタ配列
cntを \(0\) で初期化する。 - 各行の文字列 \(S_i\) を読み込み、\(j\) 文字目が
Fならcnt[j]を \(1\) 増やす。行を1つずつ処理するため、グリッド全体を保持する必要はない。 cntを左から走査し、最大値を持つ最左の添字bestを求める。cnt[j] > cnt[best]のときだけ更新すれば、同点の場合に先に現れた(より左の)列が保持される。- 答えは 1-indexed なので
best + 1を出力する。
正しさの証明
補題1: ステップ2の終了時、各 \(j\) について cnt[j] は \(j\) 列目に咲く花の総数に等しい。
証明: cnt[j] は初期値 \(0\) で、\(S_i\) の \(j\) 文字目が F である各行 \(i\) についてちょうど1回インクリメントされる。F のマスは花が咲いているマスそのものなので、cnt[j] は \(j\) 列の花の数と一致する。
補題2: ステップ3の終了時、best は cnt が最大値を取る最小の添字である。
証明: 走査は \(j = 1, 2, \ldots, W-1\) の順に行われる(best は \(0\) で初期化)。cnt[j] > cnt[best] のときのみ best が更新されるため、ループ不変条件「best は添字 \(0, \ldots, j\) の範囲で cnt が最大値を取る最小の添字」が保たれる。等しい場合は更新されないので、最大値を持つ添字のうち最も小さいものが残る。\(j = W-1\) まで処理した時点で best は全列についての最大値を取る最小添字となる。
定理: 出力値 best + 1 は、花が最も多く咲いている列のうち最も左の列番号(1-indexed)である。
証明: 補題1より cnt は各列の花の数、補題2より best は最大値を取る最小の 0-indexed 添字。したがって best + 1 が求める 1-indexed の列番号である。
計算量
- 時間計算量: \(O(HW)\)(入力の読み込みを含む)。
- 空間計算量: C++ は \(O(W)\)、Python は \(O(HW)\)。入力・出力として保持する配列や文字列も含む。
投稿日時:
最終更新: