TopCoder SRM358 Div2 500Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題についておおまかに説明する。

あなたはteletextのページ(テレビの情報サービスのこと。番号を入力して情報を参照する。)をみたいと思っている。不幸なことに、リモコンの番号がいくつか壊れてしまっている。そこでいい考えを思いついた。もし、見たいページの番号が入力できなければ別の番号を入力して"+"あるいは"-"を入力してほしい番号へ行けばよいではないか。ここでいう"+"は番号を1増やし、"-"は番号を1減らすという操作である。

あなたは最初に100というページを見ている。別の番号に向かうために、壊れていない番号を用いてページ番号を入力する。そして"+"と"-"で目的の番号へ移動する。pageという目的のページ番号(整数)とbroken[]という壊れた数字の一覧が与えられたとき、目的のページ番号へ向かうのに必要なボタンの押下回数の最小値を求めよ。なお、"+"と"-"のボタンは壊れていないものとする。

例えば、5457に向かいたいときに{6, 7, 8}のボタンが故障している場合、6回ボタンを押すことになる。5455++、5459--という順でボタンを押すことになるからである。

私の解答はこちら。

public class BrokenButtons {

 public int minPresses(int page, int[] broken) {
  if( page == 100 ) return 0; // 初期状態の番号ならボタンを押す必要なし
  if( broken.length == 10 ){ // 全部壊れているなら"+"と"-"を押すしかない
   return page >= 100 ? page - 100 : 100 - page;
  }
  int smallNearest = -1; // broken[]の要素を含まないpage以下でpageに最も近い数
  int bl = broken.length;
  for( int i=0 ; i<=page ; i++ ){
   boolean isUsable = true;
   int num = i;
   while( true ){
    int n = num % 10;
    for( int j=0 ; j<bl ; j++ ){
     if( n == broken[j] ){
      isUsable = false;
      break;
     }
    }
    num /= 10;
    if( num == 0 ) break;
   }
   if( isUsable ) smallNearest = i;
  }

  int largeNearest = 1000000;// broken[]の要素を含まないpage以上ででpageに最も近い数
  for( int i=1000000 ; i>=page ; i-- ){
   boolean isUsable = true;
   int num = i;
   while( true ){
    int n = num % 10;
    for( int j=0 ; j<bl ; j++ ){
     if( n == broken[j] ){
      isUsable = false;
      break;
     }
    }
    num /= 10;
    if( num == 0 ) break;
   }
   if( isUsable ) largeNearest = i;
  }
  // 比較では100からの"+"、"-"による移動も考慮する。
  // 例えば、101は再入力よりも+だけがボタン押下回数が少なくなる
  int ret = page >= 100 ? page-100 : 100-page;
  if( smallNearest >= 0){ // page=0のときの対処が特殊
   int sNType = page - smallNearest + ("" + smallNearest).length();
   ret = Math.min(sNType, ret);
  }
  int lNType = largeNearest - page + ("" + largeNearest).length();
  ret = Math.min(lNType, ret);

  return ret;
 }

}

得点は150/500、3回目のsubmitでようやくシステムテストクリア。大きな方針としては、page以下で入力可能な最大値とpage以上で入力可能な最小値を入れて、そこから+と-の入力回数を加えてどちらが近いか比較するというものである。システムテストには通るが、500msecぐらいかかるのでひどい実装ではある。largeNearestの評価は実は1000000(問題の設定上とりうる最大値)からではなく、page+(page-smallNearest)でよいので、そうすれば多少の計算量削減が期待できる(100万程度なら全部回しても2秒という実行時間の制限はクリアできるとは思っておりましたが)。また、利用可能かどうかを判定するロジック(boolean isUsable～ if(isUsable)の行)は2回コードに現れているので、可読性向上のためにモジュール化した方が良いでしょう。2部の提出者正解率は8%程度でした。場合分けで漏れが生じやすいので、難しいと思います。