SRM318 div2 - Set::prototype

easy

//やるだけ。
  int findArea(int N) {
    int aplb = N/2;
    int a = (aplb&1) ? aplb/2+1 : aplb/2;
    int b = aplb-a;
    return a*b;
  }

medium

//3種類のゴールの仕方がある．
//1:(jump+)walk_forward
//2:jump+walk_backward
//3:寄り道jump
min(1, 2, 3)　三つを考慮しながら実装すると良い．必ずしも最短距離を通ってjumpする必要はないことを考慮すること．
自分で実装したコードは汚かったので、あとで。

difficult

２つのコースを１回ごとに自由に選べて、W Point達成すればよいという問題．
ここで、自由選択可能だというのが、大きなポイントとなる．

ひとまず、自由に選択できない方から見てみよう．問題とは反れちゃうけど．

//W=5 N=2 P1=50 P2=25
のとき、無作為に種類が選ばれるなら、
[2 3] [2 2] [3 2] [3 3]の４通りあるはずで、1通りにつき1/4のはずである。
2Pointのコースと3Pointのコースは同様に確からしい確率で登場するので、1/2となる。

それをふまえた上でのソースコードは次のようになる．
  double tryToWin(int W, int N, int P1, int P2) {
    double dp[N+1][W+1];
    memset(dp,0, sizeof dp);
    //trigger
    dp[0][0] = 1;
    double p1 = P1*1.0/100; double p2 = P2*1.0/100;
    for(int i = 0; i < N; i++) {
      for(int j = W; j >= 0; j--) { //--なのはiが１増えるごとに１回限りの試行だから．
	int m = (j+3 < W) ? j+3 : W;
	int n = (j+2 < W) ? j+2 : W;
        //Be careful to devided by 2
	dp[i+1][m] += dp[i][j]*p2/2; //long distance//2Points
	dp[i+1][n] += dp[i][j]*p1/2; //short distance//3Points
	dp[i+1][j] += dp[i][j]*((1-p2)+(1-p1) )/2;
      }
    }
    return dp[N][W]*100;
  }

今回は自由に選択できるという条件がある．なので、W点をギリギリ超える位を最後の試行までに達成しさえすればよい。
自由に選択可能ということは最善を尽くしてGoalできる、もっといえば戦略を立てることができるということ．

//2) W=6 N=3 P1=90 P2=10のとき。 
Make your first throw in the short distanceとあるように、最初に2Pointsを狙う．
なぜ、3Pointsじゃだめなんだろう．

(1, 4) --> (2, 4)になったときはだめになっちゃうけど。

    j-3  j-2  j-1  j+0
i    a    b         c
i+1                 [a*p2+c*(1-p2),b*p1+c*(1-p1)]

0付近
     0               1               2                  3
i    a               b
i+1 a*p+a*(1-p) a*p+b*(1-p)

dpは再帰関数と併用しない方が分かりやすく書けると思うんだけどなぁ。
というか、流れを分かりやすくするためにメモ化をするんであって、再帰関数とともにメモ化したらわかりやすくならへんやん（笑）

//
  double tryToWin(int W, int N, int P1, int P2) {
    double p1 = P1*1.0/100; double p2 = P2*1.0/100;
    double dp[N+1][W+1];
    memset(dp, 0, sizeof dp);
    //trigger
    dp[0][0] = 1.0;
    for(int i = 0; i < N; i++) {
      for(int j = W; j >= 0; j--) {
        //when j = 0, 1, 2 also operate.That's I want to do.//max(j-3, 0)
        //左辺はdp[i+1][j]で統一した方がよい。
        dp[i+1][j] = max(dp[i+1][j], dp[i][max(j-3, 0)]*p2+dp[i][j]*(1-p2) );
        dp[i+1][j] = max(dp[i+1][j], dp[i][max(j-2, 0)]*p1+dp[i][j]*(1-p1) );
      }
    }
    return dp[N][W]*100;
  }
//結局、選択自由かそうでないかのソースコード上の違いはj = 0の扱いをどうするか、かな。
上はdp[i+1][0] += dp[i][0]*((1-p2)+(1-p1) )/2;としているけど、
下はdp[i+1][0] += dp[i][0]*p2+dp[i][0]*(1-p2) = dp[i][0]
となっている。上の方はn回試行して正確にjとなる確立を求めているのに対し、
下の方はn回試行してj以上の確立を求めている。だから、j=0とか、j=1とかは確立0にならない。

つまり、いまだよくわかっていないｗ

2)はこういう感じになる。
j = 0のときすべてのiで1.00になってるが、W=0のときは当然確率は1だから直観的にも正しそうだということが分かる。
 1.00 0.00 0.00 0.00 0.00 0.00 0.00
 1.00 0.90 0.90 0.20 0.00 0.00 0.00 // j = 1のとき0.90になっているが、2Pointsを獲得したときのW=1の確立と一致する
 1.00 0.99 0.99 0.83 0.81 0.18 0.04
 1.00 1.00 1.00 0.97 0.97 0.77 0.73

//左辺をそろえないとこうなるが、どの処理がどういっているのかかなり分かりにくくなっているし、間違ってしまってる。
    for(int i = 0; i < N; i++) {
      for(int j = W; j >= 0; j--) {
        int pos2 = min(j+3, W);
        int pos1 = min(j+2, W);
        dp[i+1][pos2] = max(dp[i+1][pos2], dp[i][j]*p2+dp[i][pos2]*(1-p2) );
        dp[i+1][pos1] = max(dp[i+1][pos1], dp[i][j]*p1+dp[i][pos1]*(1-p1) );
      }
    }