TopCoder練習 SRM425 DIV2

250
問題文（要ログイン）

import java.util.Arrays;

public class InverseFactoring {
 public int getTheNumber(int[] factors) {
  if(factors.length == 1) return factors[0]*factors[0];
  Arrays.sort(factors);
  return factors[0]*factors[factors.length-1];
 }

}

問題読めたもん勝ち。最初のif文は別に書かなくてもいい。
とても簡単。

500
問題文

public class CrazyBot {
 private boolean point[][] = new boolean[30][30];
 private double _east;
 private double _west;
 private double _north;
 private double _south;
 private double result = 0.0;
 
 public double getProbability(int n, int east, int west, int south, int north) {
  for(int i = 0; i < 30; i++) {
   for(int j = 0; j < 30; j++) {
    point[i][j] = false;
   }
  }
  _east = (double)east;
  _west = (double)west;
  _north = (double)north;
  _south = (double)south;
  dfs(n, 0, 0, 1.0);
  return result;
 }
 
 private void dfs(int n, int x, int y, double p) {
  if(point[y+15][x+15]) {
   return;
  }
  if(n == 0) {
   result += p;
   return;
  }
  point[y+15][x+15] = true;
  dfs(n-1, x+1, y, p*_east/100.0);
  dfs(n-1, x-1, y, p*_west/100.0);
  dfs(n-1, x, y+1, p*_north/100.0);
  dfs(n-1, x, y-1, p*_south/100.0);
  point[y+15][x+15] = false;
 }
}

この問題は時間内に解けなくて、人の回答を参考にした。
問題文読んでDFS（深さ優先探索）使えばいいんだなーって思ったけどどう実装していいかわからなかった。明らかな実力不足。勉強になりました。