Hatena::Grouptopcoder

tsubosakaの日記

2009-01-15

SRM 286 Div1 Medium

| 09:33

常にプレイヤー0から始めるとすれば各プレイヤーの勝利数は(green,red,black)の値で一意に定まる.残りの色の数を状態としてメモ付き探索.

public class BallGift {
  long memo[][][][];
  int players;
  long[] rec(int green , int red , int black, int pnum){
    if(memo[green][red][black] != null){
      return memo[green][red][black];
    }
    long res[] = new long[players];
    if(green == 0 && red == 0 && black == 0){
      //player 0 win
      res[0] = 1;
    }else{      
      if(green > 0){
        long next[] = rec(green - 1 , red , black , pnum);
        for(int i = 0 ; i < pnum ; i++){
          res[(i + 1) % pnum] += next[i];
        }
      }
      if(red > 0){
        long next[] = rec(green  , red - 1, black , pnum);
        for(int i = 0 ; i < pnum ; i++){
          res[pnum - 1 - i] += next[i];
        }
      }
      if(black > 0){
        long next[] = rec(green  , red , black - 1, pnum - 1);
        //remove player 0
        for(int i = 1 ; i < pnum ; i++){
          res[i] += next[i - 1];
        }
      }
    }
    return memo[green][red][black] = res;
  }
  public int bestPosition(int players, int green, int red, int black) {
    this.players = players;
    memo = new long[green + 1][red + 1][black + 1][];    
    long winnum[] = rec(green, red, black , players);
    int res = 0;
    for(int i = 1 ; i < winnum.length ; i++)
      if(winnum[res] < winnum[i])
        res = i;
    return res;
  }
}