AtCoder ABC 313 E - Duplicate (青色, 600 点)

こういうの詰めるの時間かかる。サンプルも弱いので、愚直シミュレーション解も実装して、それとの一致を確かめたりなどした！

• 問題へのリンク

問題概要

'1'〜'9' のみからなる文字列 が与えられる。この文字列に対して文字列を返す関数 がある。 は次の操作を実施する。

• 最初、 を空文字列とする
• に対して、 の末尾に を 個付け加える

たとえば、 となる。

与えられた文字列 (サイズ ) に を繰り返し適用したときに、 が 1 桁の数値を表す文字列になるまでの回数を求めよ。ただし、永遠にそうはならない場合は -1 と出力せよ。

制約

• 

考えたこと

まず、'1' 以外の文字が連続する箇所があると、桁数が減少することはなく、1 桁の数値とはなり得ないことがわかった。

よって、 のように、1 以外の数値が連続しない場合のみ考えればよい。色々実験していくうちに、次のように求めればよいことがわかった。考え方としては、最終的に 1 が何個展開されるのかを求めるという感じだ。

---

に対して、次を実行する。

• 文字目以降において、すでに '1' が 個分生えているとする
• の表す数値を としたとき、 を で置き換える

---

計算量は となる。

コード

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;
using mint = atcoder::modint998244353;

int main() {
    int N;
    string S;
    cin >> N >> S;
    
    // '1' 以外が連続していないかをチェック
    for (int i = 0; i+1 < S.size(); ++i) {
        if (S[i] != '1' && S[i+1] != '1') {
            cout << -1 << endl;
            return 0;
        }
    }
    
    // 何個分の 1 が生えるかを求める
    mint res = 0;
    for (int i = N-1; i >= 1; --i) {
        res += 1;
        res *= (S[i]-'0');
    }
    cout << res.val() << endl;
}