Official

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

swe-2-high

列 \(j\) に咲く花の数は、 \(H\) 行について \(S_i\) の \(j\) 文字目が F である個数を数えれば求まります。プログラムは各列 \(j\) についてこの個数 \(c\) を数え、これまでの最大値 best より大きい場合にだけ最大値と列番号を更新します。更新条件が厳密な不等号 \(c > \) best なので、同じ個数の列が後に出てきても上書きされず、最大を達成する最も左の列が残ります。全マスを \(1\) 回ずつ見るので時間計算量は \(O(HW)\) 、花園の表をすべて保持するので空間計算量も \(O(HW)\) です。列数は \(1\) 列以上あるため、最大値は必ずどこかの列で更新され、未初期化のまま出力されることはありません。

posted:
last update: