【AtCoder】F - Substrings / AtCoder Beginner Contest 214 - あめんばーどのバーチャル日記

解説とそこまで変わりませんが一応此方の解き方をば

F - Substrings

要は「連続した文字を採用しない部分文字列は何通りありますか」

$\displaystyle dp[i] = {i文字目を最後にした部分文字列の数}$

DPとしてはシンプルですね。遷移方法なんですが、まずいろいろ考えないと末尾にその文字を加えればいいので

$\displaystyle dp[i] = \sum_{k=0}^{i-2}dp[k]$

勿論こんなことしたら下記を一切考えてないです

遷移先は無数にある
重複した文字列は考えない

といったことを考えると、実は文字種ごとに一番左からだけ選んで遷移すれば良いです。

f:id:amentorimaru:20210815020805p:plain

図の通り、一番左の部分だけ取ればいいのである。

右の文字を取ってもできる文字は左で取った場合と重複をしてしまう
左の文字から取った場合でしか遷移できない文字先はあるが、右からしか遷移がカバーできない部分はない

f:id:amentorimaru:20210815020808p:plain

制約の通り、隣には遷移できないのでそちらには気を付けよう。こうすると文字列は高々26個しかないので遷移は26個しかなく $O(N)$ で書ける

  string s;
  cin >> s;
  ll n = s.size();

  vector<vector<ll>> nv(26);
  vector<ll> ni(26);
  REP(i, n)
    nv[s[i] - 'a'].push_back(i);

  vector<mint> dp(n);
  REP(i, 26)
    if (!nv[i].empty())dp[nv[i][0]]++;
  ni[s[0] - 'a']++;

  mint ans = 0;
  REP(i, n) {
    ans += dp[i];
    if (i < n - 1) {
      ni[s[i + 1] - 'a']++;
    }
    REP(v, 26) {
      if (ni[v] >= nv[v].size())continue;
      dp[nv[v][ni[v]]] += dp[i];
    }
  }

  cout << ans.val();
  return 0;

あと、逆に遷移を式で表すと

$\displaystyle dp[i] = \sum_{k=前のs[i]と同じ文字の位置-1}^{i-2}dp[k]$

なので、累積和を持っておくと文字の種類がめちゃくちゃ増えても $O(N)$ 対応できる下記は1文字目のカウント用に、2つ分の余分なスペースを確保したDP。

  string s;
  cin >> s;
  ll n = s.size();

  vector<vector<ll>> nv(26);
  vector<ll> ni(26);
  REP(i, n)
    nv[s[i] - 'a'].push_back(i);

  vector<mint> dp(n + 2);
  vector<mint> sum(n + 2);
  dp[0] = sum[0] = sum[1] = 1;
  
  REP(i, n) {
    ll v = s[i] - 'a';
    dp[i + 2] = sum[i];
    if (ni[v] > 0)
      dp[i + 2] -= sum[nv[v][ni[v] - 1]];
    ni[v]++;
    sum[i + 2] = sum[i + 1] + dp[i + 2];
  }

  cout << (sum[n + 1] - 1).val();
  return 0;

うーん、ちゃんと書いたら「ほぼ同じ」じゃなくて「まったく同じ」だったなぁ。
累積和若干ややこしかったので終わった後組むの難しかったです。