TopCoder SRM197 Div2 250Pts

今日のTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

問題について説明する。

ガーデニングにおける水やりを考える。縦にn、横にn箇所植物を格子状に配置する。植物の間隔はrowDist、colDistで定義されている。また、泥で汚れるのが嫌なので、水やりは離れたところから行う。hoseDist離れた場所まで水をやることができるものとする。このとき、何ヶ所の植物に水をやることができないかを返すメソッドを作成せよ。なお、植物周りにも泥があるため、踏みこめない領域は、植物の周囲にもrowDist、colDistの分だけ存在する。

例えば、n=3、rowDist=2、colDist=1、hostDist=1とすると、2行目の3つの植物には水をやれないので、3が返される(1、3行目は上下から水をやればcolDist=1、hoseDist=1なので水が届く)。

私の解答は以下の通り。

public class GardenHose {
 public int countDead(int n, int rowDist, int colDist, int hoseDist) {
  boolean watered[][] = new boolean[n][n];
  for( int i=0 ; i<n ; i++ ){
   for( int j=0 ; j<n ; j++){
    watered[i][j] = false;
   }
  }
  for( int i=0 ; i<n ; i++ ){
   for( int j=0 ; j<n ; j++ ){
    if( hoseDist >= colDist*(i+1) ){
     watered[i][j] = true; // 列方向から水が届く
     watered[n-1-i][j] = true; // 反対側も同じく届く
    }
    if( hoseDist >= rowDist*(j+1) ){
     watered[i][j] = true; // 行方向から水が届く
     watered[i][n-1-j] = true;
    }
   }
  }
  int dry = 0;
  for( int i=0 ; i<n ; i++ ){
   for( int j=0 ; j<n ; j++ ){
    if( watered[i][j] == false ){
     dry++; // 水をやれなかった場所をカウント
    }
   }
  }
  return dry;
 }
}

得点は192.34/250。正解率は約72%。対称性を利用すると、問題が簡単になる。楽に実装するために、プログラマは怠惰であるべきですな。後から調べて分かったことだが、boolean変数はfalseで初期化されているので、実はwatered[i][j]にfalseを代入する作業は不要であった。