Codeforces Round #597 (Div. 2) C. Constanze's Machine 解説

codeforces.com

DPに関して学びになる問題だったので、メモとして残す．

漸化式

• dp[i] := s[i]まででn or uが連続する区間においていたずらできる回数

この問題で漸化式を上記の様に定義すると、dpテーブルの遷移はフィボナッチ数列と同じになることに気付く．
遷移がフィボナッチと同じになるdpは典型の一種なので、おさえておきたい．

実装

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
using ll = long long;

ll mod = 1e9 + 7;
char u = 'u';
char n = 'n';

const int maxlen = 100010; // 文字列の最大長
ll dp[maxlen];

signed main() {
  string s;
  cin >> s;
  int len = s.size();

  if (s[0] == 'w' || s[1] == 'w' || s[0] == 'm' || s[1] == 'm') {
    cout << 0 << endl;
    return 0;
  }
  
  fill(dp, dp + maxlen, 1);
  
  if ((s[0] == u || s[0] == n) && s[0] == s[1]) dp[1] = 2;
  for (int i = 2; i < len; i++) {
    if (s[i] == 'w' || s[i] == 'm') {
      cout << 0 << endl;
      return 0;
    }
    if (s[i] == u || s[i] == n) {
      if (s[i] == s[i - 1] && s[i - 1] == s[i - 2]) dp[i] = (dp[i - 2] + dp[i - 1]) % mod;
      else if (s[i] == s[i - 1]) dp[i] = 2;
    }
  }

  ll ans = 1;
  rep(i, maxlen - 1) {
    if (dp[i] == 1) continue;
    if (dp[i + 1] == 1) ans = (ans * dp[i]) % mod;
  }

  cout << ans << endl;
}

目の不自由なConstanzeにいたずらするAkkoゆるさねえ。