[ABC313] E - Duplicate

本番では問題を読むところまでいかなかった。
すんなり解けたので、n回目の問題先読みしましょうの教訓。
[Q] https://atcoder.jp/contests/abc313/tasks/abc313_e

考察
・問題文通りの処理を行う関数を作って、法則性を見出す。
1. 22など、2以上の値が2つ並ぶと無限処理になり-1
2. 1Xのパターンが来た時に、上昇率がX倍されるようだ。

21:1
212:3
2121:5

12:2
121:4
1212:8
12121:12
121212:20
1212121:28

・1Xのパターンで、昇幅が上がっていそうだ。上がる倍率はX倍。

  S = 1213:10
add = 226 = 10 (2+2+6という加算になっている）

  S = 1312:12
add = 336 = 12 (3+3+6という加算になっている）

・先頭indexから処理していって、1Xのパターンがきたら上昇率をX倍して、都度その時のパターンを加算していけばよさそう。O(N)

実装

int main() {
  cincout();
  
  ll N;
  string S;
  cin >> N >> S;

  // debug用。使わない。
  auto simplesolve = [&](string S)->ll{
    ll cnt = 0;
    while (S.size() > 1){
      cerr << cnt << ":" << S << endl;
      ++cnt;
      if (S.size() >= 100) return cnt;
      string T;
      rep(i, S.size() - 1){
        if (S[i] >= '2' && S[i + 1] >= '2') return -1;
        T += string(S[i + 1] - '0', S[i]);
      }
      swap(S, T);
    }
    return cnt;
  };
  // cout << simplesolve(S) << endl;

  // 22で無限ループ
  rep(i, N - 1){
    if (S[i] > '1' && S[i + 1] > '1'){
      cout << -1 << endl;
      return 0;
    }
  }
  mint ans = 0;
  mint add = 1;
  rep(i, N - 1){
    if (S[i] == '1' && S[i + 1] > '1'){
      add *= S[i + 1] - '0';
    }
    ans += add;
  }
  cout << ans << endl;
}

https://atcoder.jp/contests/abc313/submissions/44368209