JOI本選の問題です。GCCのバージョンによっては、もしかすると本番でも使えるかも??
解法
J, O, I の3種類の文字から成る文字列Sは、どんな文字列であっても (J*)(O*)(I*)
の繰り返しによって表されます。
正規表現を利用し、文字列Sをこのパターンにそって分割します。
- 例
OJJOOIIOJOI
↓
[('', 'O', ''), ('JJ', 'OO', 'II'), ('', 'O', ''), ('J', 'O', 'I')]
次に、分割したそれぞれの組がJOI文字列であるかどうかの判定、JOI文字列であるならそのレベルの判定を行います。
JJJJOOOIIIのような組がJOI文字列であるかどうか判定するとき、最も大切なのは'O'の個数です。'O'をX個持つ組があったとき、もしもそれがJOI文字列であるならば、その組のレベルは'O'の個数X以外になることはありません。
レベルXのJOI文字列は'O'の左にX個以上の'J'、そして'O'の右にX個以上の'I'をもつ必要があります。
これで、それぞれの組がJOI文字列であるかどうかの判定、およびそのレベルの判定ができました。
ソースコード (Python)
import re s = raw_input() joi_pattern = '(J*)(O*)(I*)' ans = 0 for joi_group in re.findall(joi_pattern, s): j = len(joi_group[0]) o = len(joi_group[1]) i = len(joi_group[2]) if j >= o and o <= i: ans = max(ans, o) print ans