Google Code Jam 2017 Qualification Round B問題 - Tidy Numbers

Source

Google Code Jam 2017 Qualification Round B問題
Problem Statement

問題概要

(10進数において)左から右に見たときに,各桁の数字が減らない正整数を tidy と呼ぶ.
例えば,$1122334455, 7889$ は tidy だが,$213, 778899990$ は tidy でない.
$N$ 以下の整数の中で tidy な整数の最大値を求める問題.

解法

色々な解き方があるが以下のようにやった.
$i$ 桁目の数字が $i+1$ 桁目の数字より大きいような $i$ を見つけてきて,
$i$ 桁目の数字を $1$ 減らし,$i+1$ 桁以降の数字を $9$ に置き換える.
これを繰り返して,$i$ が見つからなくなったらそれが答え.
この方法だと時間計算量は $O( (\log N)^2 )$.

cLayversion 20170408-3)のコード

C++に変換後のコードはこちら

{
  int test = 0, TEST;
  rd(TEST);
  while(TEST--){
    printf("Case #%d: ", ++test);
    fprintf(stderr, "r=%d\n", TEST);

    char N[20];
    int i, j, len, fg;

    rd(N);
    len = strlen(N);

    rep(i,len) N[i] -= '0';
    for(;;){
      fg = 0;
      rep(i,1,len) if(N[i-1] > N[i]){
        N[i-1]--;
        N[i..len-1] = 9;
        fg = 1;
        break;
      }
      if(!fg) break;
    }

    if(N[0]==0){
      len--;
      N[0..len-1] = N[1..];
      N[len] = '\0';
    }
    N[0..len-1] += '0';
    wt(N);
  }
}

Current time: 2017年09月22日15時19分25秒
Last modified: 2017年04月14日00時52分48秒 (by laycrs)
Tags: Competitive_Programming Google_Code_Jam GCJ_2017 GCJ_2017_Qualification_Round
トップページに戻る

Logged in as: unknown user (not login)

ログイン: