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

AOJ 0571 JJOOII (正規表現解法)

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