📑

[AtCoder ABC214 F Substrings] 部分列DP。自己流かも

2021/08/16に公開

Python

競技プログラミング

tech

(問題ページ) AtCoder ABC214 F Substrings

部分列DPの問題。
公式解説とは違った形でDPした解答です。

とりあえずACしましたが、このやり方が正しいことを、数学的に証明するスキルが、自分には無いので、ちょっと不安。詳しい人にお墨付きもらいたい気分・・・

実行時間は、Pythonで267 ms、PyPy3で148 msくらいでした。

1.考え方

2次元のDPテーブルを用意します。
　dp[i][j]　(j=0,1)
　文字列Sのi番目の文字を「選択する(j=1)」場合の数
　　　〃　〃　　　　　　「選択しない(j=0)」場合の数
(ここで書いたi番目とは、文字列Sに対して1-indexed。dp[i]のiは0-indexed)

i=0の時、dp[0][j]は、文字が無い(何も選んでない)状態となります。
そのため初期値として、
　dp[0][1] = 0 (文字が無いため、「選択した」場合の数は0通り)
　dp[0][0] = 1 (文字が無いため、「選択しない」場合の数は1通り)
を設定します。

重複無しの場合

まず、文字列Sに重複した文字が無い場合、を考えてみます。
文字列Sを1文字目から順番に見ていった時、
漸化式(iは0-indexed)は、

文字S[i]を「選択する」場合、ひとつ前の(隣り合った)文字は選択できない。
　dp[i+1][1] += dp[i][0]
文字S[i]を「選択しない」場合、ひとつ前の(隣り合った)文字は「選択する・しない」どちらでもOK。
　dp[i+1][0] += dp[i][0] + dp[i][1]

となります。

重複ありの場合

文字S[i]が、文字S[j] (j<i)と重複していた場合、dp[i+1][1] からdp[j+1][1]を引く。
(iは0-indexed)

重複文字が複数個所ある場合(S[j] (j<i), S[k] (k<i) ... )は、それぞれの値(dp[j+1][1], dp[k+1][1] ... )を全部引く。

この「重複分を引く」処理は、
文字列を探索していく際に、文字をキーとしたHash(連想配列)に、場合の数を足していくことで、計算量を抑えられます。

Hash(連想配列)をcntとすると、
　dp[i+1][1] -= cnt[S[i]]　　・・・重複分を引く処理
　cnt[S[i]] += dp[i+1][1]　　・・・cntの更新
といった感じで更新できます。

3.code

# -*- coding: utf-8 -*-
import sys


def main():
    S = sys.stdin.readline().rstrip()


    dp = [ [0]*2 for _ in range(len(S) + 1) ]
    # dp[i][0]: the number of pattern, where not select S[i]
    # dp[i][1]: the number of pattern, where select S[i]
    dp[0][0] = 1

    mod = 10**9 + 7
    cnt = { chr(ord("a") + i) : 0  for i in range(26) }

    for i in range(len(S)):
        dp[i+1][0] += dp[i][0] + dp[i][1]
        dp[i+1][1] += dp[i][0] - cnt[S[i]]
        cnt[S[i]] += dp[i+1][1]

        dp[i+1][0] %= mod
        dp[i+1][1] %= mod
        cnt[S[i]] %= mod


    ans = 0

    for i in range(1, len(dp)):
        ans += dp[i][1]
        ans %= mod
    
    print(ans)


if __name__ == "__main__":
    main()

1.考え方

重複無しの場合

重複ありの場合

3.code

Discussion