Hatena::Grouptopcoder

tsubosakaの日記

2011-07-26

SRM 513

21:55

久々にまともに解けた回

250

英語が読みづらかったけど各platformに対して、おける配置の数を独立にもとめて掛けてやればよい。

50 * 10000 * 50の解法でも間に合う


public class YetAnotherIncredibleMachine {
  long count(int pm , int pl , int[] balls){
    long count = 0;
    for(int left = pm - pl ; left <= pm ; ++left){
      int right = left + pl;
      boolean f = false;
      for(int b : balls){
        if(left <= b && b <= right){
          f = true;
        }
      }
      if(!f)++count;
    }
    return count;
  }
  public int countWays(int[] platformMount, int[] platformLength, int[] balls) {
    long mod = 1000000009;
    long res = 1;
    for(int i = 0 ; i < platformMount.length ; ++i){
      int pmi = platformMount[i];
      int pli = platformLength[i];
      long count = count(pmi , pli , balls);
      res = (res * count) % mod;
    }
    return (int)(res % mod);
  }
}

500

残りのカード枚数と残りのうちすでに開いたものの数をkeyにしたdp


import java.util.*;

public class PerfectMemory {
  double[][] dp;
  double rec(int resCard , int memSymbol){
    if(resCard <= memSymbol * 2){
      return resCard / 2.0;
    }
    if(dp[resCard][memSymbol] >= 0.0){
      return dp[resCard][memSymbol];
    }
    double exp = 1.0;
    int notReveal = resCard - memSymbol;
    double r1 = memSymbol * 1.0 / (double)notReveal;
    if(memSymbol > 0){
      exp += r1 * rec(resCard - 2 , memSymbol - 1);      
    }
    double r2 = 1.0 - r1;
    double rinv = 1.0 / (double)(notReveal - 1);
    exp += r2 * rinv * rec(resCard - 2 , memSymbol);
    exp += r2 * memSymbol * rinv * (rec(resCard - 2 , memSymbol) + 1);
    exp += r2 * (notReveal - 2 - memSymbol) * rinv * rec(resCard , memSymbol + 2);
    return dp[resCard][memSymbol] = exp;
  }
  
  public double getExpectation(int N, int M) {
    dp = new double[N * M + 1][N * M + 1];
    for(int i = 0 ; i < dp.length ; ++i){
      Arrays.fill(dp[i], -1.0);
    }
    return rec(N * M , 0);
  }
}

ArnieArnie2011/08/30 04:49Life is short, and this airtcle saved valuable time on this Earth.

qctsvsirsqctsvsirs2011/08/30 17:05GHubQ8 <a href="http://tqsengcrklhz.com/">tqsengcrklhz</a>

vdbjtprvdbjtpr2011/09/01 16:56mfoJMg , [url=http://tkllhtysxufe.com/]tkllhtysxufe[/url], [link=http://zgmhmyswjjri.com/]zgmhmyswjjri[/link], http://gtccgdeialbq.com/

udkacsjhenjudkacsjhenj2011/09/03 18:14cmyPv6 <a href="http://qwwgebnzylel.com/">qwwgebnzylel</a>

xbsnexjozxbsnexjoz2011/09/04 02:127lBMVO , [url=http://yvnvymkgzodf.com/]yvnvymkgzodf[/url], [link=http://jqqfaxubcgjy.com/]jqqfaxubcgjy[/link], http://qoayefvelzpp.com/