けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

AtCoder AtCoder600点 ABC-E 青色diff 考察：場合分けして考える ほとんどのところで値が一定値に決まる 順序の工夫：後ろから見る DP 文字列 収束性に着目する 操作 操作:隣接要素の和や差をとる 最小回数・最小個数を求める 最適化問題

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

問題概要

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

  • 最初、 T を空文字列とする
  • i = 0, 1, \dots, |S|-1 に対して、 T の末尾に S_{i} を S_{i+1} 個付け加える

たとえば、 f(313) = 3111 となる。

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

制約

  • 2 \le N \le 10^{6}

考えたこと

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

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

i = |S|-1, |S|-2, \dots, 1 に対して、次を実行する。

  • i+1 文字目以降において、すでに '1' が m 個分生えているとする
  • S_{i} の表す数値を s としたとき、 m を (m + 1) \times s で置き換える

計算量は O(N) となる。

コード

#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;
}