C. Periodic integer number ～コーナーケースは端っこを攻めろ！～

1700
  • Quiz
  • AC
  • 解説
    • ...はeditorialの通りなので書きません
    • 解法は簡単に思いつきますが、コーナーケースがあります。与えられる文字列sの長さをNとして、N%K==0の時、かつsがすべて'9'の時です
    • これはかなり思いつきづらいと感じたのですが、繰上りを考えると9に注意しないといけないことは分かり、その1番極端な例として999999などがあり、これは極端な例の端っこです
    • まとめると、自分でサンプルを増やすときは、「ランダムな例」「極端な端っこの例」どちらも足すのが良い
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll L;cin>>L;
    string s;cin>>s;
    ll N = s.size();

    if(N%L){
      // 桁を上げる必要がある
      // L桁の10000を数セット
      string a(L,'0');
      a[0]='1';

      ll num = N/L + 1;
      stringstream ss;
      rep(i,num){
        ss << a;
      }
      p(ss.str()); return 0;
    }

    // N%L==0

    // まずは先頭コピーを試してみる。それで満たすなら終了 (1)
    {
      string t = s;
      FOR(i,L,N){
        t[i] = t[i-L];
      }
      if(t>s){
        p(t);
        return 0;
      }
    }

    // 全部999999というコーナーケース...
    ll nine_cnt=0;
    rep(i,N){
      if(s[i]=='9') nine_cnt++;
    }
    if(nine_cnt==N){
      // 桁自体を増やす必要
      string a(L,'0');
      a[0]='1';
      ll num = N/L + 1;
      stringstream ss;
      rep(i,num) ss<<a;
      p(ss.str()); return 0;
    }

    // 先端に9じゃない数字が1つはある (なぜなら(1)が通ってないので)
    for(int i=L-1; i>=0; i--){
      if(s[i]!='9'){
        s[i]++;
        FOR(j,i+1,L) s[j]='0';
        break;
      }
    }
    FOR(i,L,N){
      s[i] = s[i-L];
    }
    p(s);

    return 0;
}