JOI難易度６ スタンプラリー ２

問題原文

atcoder.jp

問題要旨

長さ の J, O, I からなる文字列 が与えられる。
文字列のある１箇所に J, O, I の文字を差し込むことで、変化後の文字列 に含まれる JOI という部分文字列のとりかたの通り数を最大化せよ。

• 

解法

基本はdp。 文字目までみたときの Jの数, JO の数, JOI の数 を数えながら遷移すればOK。

この問題特有の、「１文字差し込む」という操作については、
J は の先頭につけて損しない。 → J + についてdp。
I は の末尾につけて損しない。 → + I についてdp。
O は差し込んだ場所について、（左側にある J の数）× （右側にある I）の数だけ通り数が増える。
→ についてのdpの計算結果に付け加える。J の数と I の数は累積和をとっておけば高速に求められるので、差込場所を全探索できる。

でOK！

実装

制約やさしいので、辞書でdpまわしても余裕でまにあう。
直感的になってすき。

from itertools import accumulate
N = int(input())
S = input()


def calc(X):
    dp = {'J': 0, 'JO': 0, 'JOI': 0}
    for x in X:
        if x == 'J':
            dp['J'] += 1

        elif x == 'O':
            dp['JO'] += dp['J']

        elif x == 'I':
            dp['JOI'] += dp['JO']

    return dp['JOI']


ans1 = calc('J' + S)
ans2 = calc(S + 'I')
ans3 = calc(S)

J_cnt = list(accumulate([int(s == 'J') for s in S]))
I_cnt = list(accumulate([int(s == 'I') for s in S]))
ans3_add = 0
for i in range(N):
    ans3_add = max(ans3_add, J_cnt[i] * (I_cnt[-1] - I_cnt[i]))

print(max(ans1, ans2, ans3 + ans3_add))

感想

We Love ABC DPってこころの中で言ってる。（たぶんあっちのほうがむずかしい）

atcoder.jp