yukicoder No.1171 Runs in Subsequences

writer解説とは少し違うかもしれない

yukicoder.me

問題概要

文字列Sが与えられる。 全ての部分文字列の「同一の文字が連続する非空かつ極大な区間（以下「連」と言う）」の個数の総和を1e9+7で割った余りを求めよ。

記法

面倒なので、記法を定義する。

• S[i..j] i番目からj番目までの連続部分文字列

戦略

• S[0..i-1] の状態と解が分かっているとき、S[0..i]の状態と解が容易に求まるようなアルゴリズムを考える
• 全ての部分文字列を列挙しつつ、効率的に管理したい。
• 文字列の末尾と異なる文字を加えた場合のみ、連が増加する。それ以外の場合は増加しない。
• つまり、「末尾がcであるような部分文字列の数=:dp[c]」を状態として管理すれば、解が求まりそうである。

入力がabaの時の、全ての部分文字列を例に挙げる。

i	0	1	2
S[i]	a	b	a
substr	S[0..0]	S[0..1]	S[0..2]
部分 文字列	a _	ab _b a_ __	aba _ba a_a __a ab_ _b_ a__ ___
dp[a]	1	1	5
dp[b]	0	2	2

観察すると、1(ab) -> 2(aba) の遷移では以下が言える。

• dp[not a] は、変化しない。
• dp[a] は、空を含むS[0..1]の部分文字列の個数だけ増加する。

他にも同様に言えるので、これでdpの求め方は分かった。しかし、解を未だ求めていない。

説明の為、ans[i] を S[0..i]を入力とした時の解とする。最終的に求めたいのは、ans[N-1]である。

S[0..i-1]部分文字列にS[i]か虚無を加えたものがS[0..i]部分文字列なので、
ans[i] = ans[i-1]*2 + (連が増加した部分文字列の個数)
となる。

末尾がS[i]以外の文字列にS[i]を加えた時連が増加するので、 「連が増加した部分文字列の個数」とは「S[0..i-1]部分文字列の中で末尾がS[i]でない文字列」 であり、これは先程求めたdpから総和を取るだけで求まる。

よって、ans[N-1]まで求まった。

コード

int N;
string S;

//

int main() {
  scanner >> S;
  N = S.size();
  
  // dp1[c] :=
  // 最後の文字がcであるようなS[0..i]の部分文字列の数。
  vector<ll> dp1(26);
  
  // 答え
  ll total = 0;
  
  // 2のi乗、つまり、S[0..i-1]部分文字列の個数
  ll pow2 = 1;
  repeat(i, N) {
    int c = S[i] - 'a';
    
    // 末尾がc以外の文字列にcを加えると連が増加する
    total = total*2 + (pow2 - dp1[c]);
    total += MD;  // 負になり得るので
    total %= MD;

    // 全てのS[0..i-1]部分文字列の末尾にcを付加したものを、
    // dpに加える。
    dp1[c] += pow2;
    dp1[c] %= MD;
    
    pow2 *= 2;
    pow2 %= MD;
  }
  
  printer << (total%MD) << '\n';
  
  return 0;
}

#530956 (C++17(1z)) No.1171 Runs in Subsequences - yukicoder