Long Beautiful Integer [Codeforces Round #609 (Div. 1) A]

https://codeforces.com/contest/1268/problem/A

解説

https://codeforces.com/contest/1268/submission/67379463

適当に解説を書いておく。
B[i] = A[i % K]としてまず置く。
先頭から大小関係を比較していく。
Bの方が既に大きいなら、答え。
Aの方が大きくなったら、その添字をメモっておく。
B[0]～B[K-1]はAと同じなので、その添字badは、K以上になる。
これを解消するにはB[bad % K]を+1すればいい。
だが、これが最適とは限らず、bad % K < badであることは確実なので、
bad % Kよりもbad % K + 1を+1する方が最適になる場合がある。
なので、後ろから順に+1できたらする。
より小さくするために、+1できた場合は、後ろを0埋めしておく。

int N, K;
string A;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> A;
    
    string B = "";
    rep(i, 0, N) B += A[i % K];

    int bad = -1;
    rep(i, 0, N) {
        if (A[i] < B[i]) break;
        else if (A[i] > B[i]) {
            bad = i;
            break;
        }
    }
    if (0 <= bad) {
        bad %= K;
        rrep(k, K - 1, bad) {
            if (B[k] != '9') {
                int i = k;
                while (i < N) {
                    B[i]++;
                    i += K;
                }
                rep(kk, k + 1, K) {
                    i = kk;
                    while (i < N) {
                        B[i] = '0';
                        i += K;
                    }
                }
                break;
            }
        }
    }

    printf("%d\n%s\n", N, B.c_str());
}