TopCoder SRM188 Div2 250Pts

英語の速読とJavaのトレーニングも習慣になってきたかな?今日の問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

問題を大まかに説明する。入力に3*3の魔方陣が与える（実際の引数としては、要素が9の1次元配列で、魔方陣の左から右、上から下の順でデータを格納している）。魔方陣は縦横斜めで和をとった時に、値が同じになる性質を持つ。いま、魔方陣の1箇所だけ-1が入っている。-1のある場所に本来入るべき値は何かを返すメソッドを作成せよ。ただし、-1以外の値は1から100の正の整数が魔方陣に入っているものとする。

私の解答はこちら。

public class MagicSquare {
 public int missing(int[] square) {
  int rowSum[] = new int[3];
  int negCol = 0;
  int negRow = 0;
  for( int i=0 ; i<3 ; i++ ){
   for( int j=0 ; j<3 ; j++ ){
    rowSum[i] += square[i*3+j];
    if( square[i*3+j]<0 ){
     negRow = i;
     negCol = j;
    }
   }
  }
  int max = Math.max(rowSum[0],rowSum[1]);
  max = Math.max(max,rowSum[2]);
  int exceptNeg = 0;
  for( int j=0 ; j<3 ; j++ ){
   if( j==negCol )continue;
   exceptNeg += square[negRow*3+j];
  }
  return max-exceptNeg;
 }
}

得点は196.97/250。全体の正解率は約90%。他の解答を眺めていると、3行のうち1行だけ値が小さいので、1行目の総和<2行目の総和なら1行目に-1があり、2行目の総和<3行目の総和であれば、2行目に-1、それ以外は3行目に-1が含まれているということになるという性質を利用しているものがあった。返す値は、総和が大きい方-総和が小さい方+1とすればより解答が綺麗になると思われる。私の解答を改良するのであれば、maxに対応して3行の最小値を格納する変数minを用意して、max-(min+1)を返せばよいだろう。つまり、以下のようなコードが良さそうということである。

public class MagicSquare {
 public int missing(int[] square) {
  int rowSum[] = new int[3];
  for( int i=0 ; i<3 ; i++ ){
   for( int j=0 ; j<3 ; j++ ){
    rowSum[i] += square[i*3+j];
   }
  }
  int max = Math.max(rowSum[0],rowSum[1]);
  max = Math.max(max,rowSum[2]);
  int min = Math.min(rowSum[0],rowSum[1]);
  min = Math.min(min,rowSum[2]);
  return max-(min+1);
 }
}

最初の解答と比較して、随分とすっきりとしたコードになった。不明であることを示す値は常に-1であるなどの性質の活用は重要である。