TopCoder SRM 687 (Div. 2) Medium. Quacking
問題概要
quack, quack と鳴く鳥が何匹かいて、その鳴き声を録音した結果が文字列 S として与えられる。
複数の鳥が同時に鳴いているため quqacukqauackck のように混ざった音として録音される。
録音している場所には少なくとも何匹の鳥がいるだろうか。
解法
以下のような変数を用意する。
- num[0] := q まで鳴いている鳥の数
- num[1] := qu まで鳴いている鳥の数
- num[2] := qua まで鳴いている鳥の数
- num[3] := quac まで鳴いている鳥の数
これを地道に更新していく。途中で num[i] が負になったり、最終的に num[i] が 0 でなかったりすると -1 になる。求める答えは sum(num[i]) の最大値。
TopCoder SRM 687 (Div. 2) Medium. Quacking
最後に num[i] が 0 になっていないケースを忘れていたので systest で落ちた。