インクリメント [yukicoder No.539] - はまやんはまやんはまやん

解説放送

解法

まず、1行毎に取得するときはgetline関数を使う。
数のまとまりを探す時は尺取り法のようなやり方で探していくとO(N)でできる。
Lで全探索するが、[L,R]の範囲が全て数であるようなRを探すときに、[L,R]の範囲が確定したら、[L,R]の範囲はもう考える必要は無くなるため、Lの次はR+1から探索する。
このようにやっていくとO(N)

次に3つの文字列に分ける。
A := 数の前の文字列
B := 数部分の文字列
C := 数の後の文字列
これはstringのsubstrメソッドを使うと、もし結果が空文字列になっても上手くやってくれるので便利。

あとは、Bをインクリメントするが、文字列のインクリメントは筆算のように自力でやるしか無い。
文字列の下の桁から、筆算の要領で繰り上がりを考慮しながら、計算していこう。

string S;
string incriment(string s) {
    int d = 1;
    int n = s.length();
    rep(i, 0, n) {
        int c = s[n - 1 - i] - '0' + d;
        d = c / 10;
        c = c % 10;
        s[n - 1 - i] = char('0' + c);
    }

    if (0 < d) s = char('0' + d) + s;
    return s;
}
void solve() {
    getline(cin, S);

    pair<int, int> p = {-1, -1};
    rep(L, 0, S.length()) if('0' <= S[L] && S[L] <= '9') {
        int R = L + 1;
        while ('0' <= S[R] && S[R] <= '9') R++;
        p = { L, R - 1 };
        L = R - 1;
    }

    if (p.first < 0) {
        printf("%s\n", S.c_str());
        return;
    }

    string A = S.substr(0, p.first);
    string B = S.substr(p.first, p.second - p.first + 1);
    string C = S.substr(p.second + 1);

    B = incriment(B);
    printf("%s%s%s\n", A.c_str(), B.c_str(), C.c_str());
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    string S; getline(cin, S);
    rep(i, 0, T) solve();
}