SRM281 に挑戦．今年，最初の SRM です．例のごとく日本時間の深夜 1:00 スタートという，ありがたいんだが，ありがたくないんだがよくわかりませんが，やはり眠いなかでの参戦となりました．まあ，平日昼間だと参加できないので，ありがたいんでしょうが．．

IntegerGenerator (code)

250 点問題．

int[] allowed: 使用が許されている数字(0-9 のいずれか)のリスト
String current: 現在の数 (整数)

が与えられます．この時，

与えられた数 current の各桁が許可数字だけを使用しているかどうかをチェック
1 が OK なら，許可数字だけを使用して current より大きい次の数字を生成して返しなさい

という問題です．たとえば，

allowed: {1, 2, 3}
current: "2133"

ならば，current: 2133 の各桁は，許可数字{1, 2, 3}に含まれているものだけを使用しているので OK です．また，current より大きい，許可数字だけを使用した次の数は，"2211" になります．

最初は，ただ単に current を 1 ずつ increment して OK かどうかチェックするという単純な方法で十分と思い込み，8 分ほどで Submit しました． Submit 後に，いくつかチェックしていると，入力条件によってはこれではタイムアウトすることに気づきました．入力が

{9}, "9999999999" (10 桁)

でタイムアウトです．この場合の正解は"99999999999" (11 桁) ですが，1 ずつ increment していては，とてもじゃないが 2 秒以内には終わりません．

慌ててやり直しましたが．．．はまりました．．完全に方針を誤り右往左往でした．最終的になんとか完成させ再提出したのですが (提出時点ではポイント 75 と最低点でした ...），それでもバグがひとつ入っていたため，System Test に落ちました．入力の int 配列: allowed が空のケースで，ArrayIndexOutOfException が発生させてしまっています．

初歩的な入力条件のチェックミス．．空かどうかチェックを一行いれておけば，SystemTest に通っていましたね．

SRM 後に，冷静になって，コードを書き直してみました．使用できる数字が限られたケースで，1 を足す動作を，シミュレートするだけです．

public class IntegerGenerator {
  public String nextInteger(int[] allowed, String current) {
      Arrays.sort(allowed);
      char[] ca = current.toCharArray();
      if (ca[0] == '0') return "INVALID INPUT";
      for (char c : ca) {
          if (Arrays.binarySearch(allowed, c - '0') < 0) return "INVALID INPUT";
      }
      for (int i = ca.length - 1; i >= 0; i--) {
          int index = Arrays.binarySearch(allowed, ca[i] - '0');
          if (index == allowed.length - 1) {
              ca[i] = (char) ('0' + allowed[0]);
          } else {
              ca[i] = (char) ('0' + allowed[index + 1]);
              return new String(ca);
          }
      }
      return ((allowed[0] == 0) ? allowed[1]: allowed[0]) + new String(ca);
  }
}

こうしてみるとそんなに難しい問題ではなかったですね．やっぱり 250 点問題です．本番中は，頭が回りませんでした．．．

BallBouncing

600 点問題．Open しませんでした．

Equidistance

1000 点問題．Open しませんでした．

結果

System Test の結果です． ( Room Statistics )

Room Statistics

今日は，惨敗です．チャレンジタイムも，ターゲットが次々とほかの人にさらわれてしまい，結局，チャレンジゼロでした．．

レーティングは 1630 -> 1542 と，100 近く低下しました．

今日の教訓

当たり前ですが，入力条件をよく読むように．