読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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 で落ちた。