TopCoder SRM 513

TopCoder SRM 513(7/26 20:00~22:00)

珍しい時間帯のSRM．夕飯後は眠くなるので辛い．

■YetAnotherIncredibleMachine(Easy)

・解法

全探索．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class YetAnotherIncredibleMachine {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public int countWays(int[] mount, int[] length, int[] balls) {
  int n=length.length;
  int m=balls.length;
  long res=1;
  long mod=1000000009;
  for(int j=0;j<n;j++){ 
   int c=0;
   for(int x=-length[j];x<=0;x++){
    boolean f=true;
    for(int i=0;i<m;i++){
     if(mount[j]+x<=balls[i]&&balls[i]<=mount[j]+x+length[j]){
      f=false;
     }
    }
    if(f){
     c++;
    }
   }
   res=(res*c)%mod;
  }
  return (int)res;
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

■PerfectMemory(Medium)

n(：偶数)枚のカードで神経衰弱を行う．一度めくったカードを全て記憶しておくことができるとしたとき，最適な戦略を用いた場合のゲーム終了までにめくる回数の期待値を求めよ．

解法

(残り枚数, 既に知っているカードの枚数)で期待値のDP．
既に知っているカードには，ペアは含まれない（=どの2枚も異なる）とする．
状態が(n, m)の時，n-mから1枚引く．

図では，暗い赤が知っているm枚（引かれないカード）， 明るい赤は暗い赤のカードに対応するペアの片割れ．

1.明るい赤を引いた時(m枚)

対応するカードを暗い赤から選ぶ． つまり，1ターンで，状態が(n-2,m-1)になる． よって，この時の期待値は1+dp(n-2,m-1)．

2.青を引いた時(n-2m枚)

引いたカードを暗い紫とする．この時対応するカードは青にある（明るい紫）． 次に，n-m-1(青+明るい赤+明るい紫)から1枚引く．

2.1.明るい赤を引いたとき(m枚)

次のターンで，対応する赤のペアを引く． この時の期待値は，2+dp(n-2,m)．

2.2.青を引いたとき(n-2m-2枚)

既に知っているカードが2枚増えるだけなので， この時の期待値は，1+dp(n,m+2)．

2.3.明るい紫を引いたとき(1枚)

紫ペアがなくなるので，この時の期待値は，1+(n-2,m)．

これらからDPテーブルを更新していきます．初期値の与え方が面倒なので，メモ化再帰でもいいかも知れません．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class PerfectMemory {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public double getExpectation(int N, int M) {
  int n=N*M;
  double[][] dp=new double[n+1][n+1];
  for(int j=2;j<=n;j+=2){
   for(int i=j;i>=j/2;i--){
    dp[j][i]=j/2;
   }
   for(int i=j/2-1;i>=0;i--){
    double p1=(double)(j-2*i)/(j-i);
    double p2=(double)i/(j-i);
    double q1=(double)i/(j-i-1);
    double q2=(double)(j-2*i-2)/(j-i-1);
    double q3=(double)1/(j-i-1);
    dp[j][i]+=(2+dp[j-2][i])*p1*q1;
    dp[j][i]+=(1+dp[j][i+2])*p1*q2;
    dp[j][i]+=(1+dp[j-2][i])*p1*q3;
    if(i>0){
     dp[j][i]+=(1+dp[j-2][i-1])*p2;
    }
   }
  }
  for(int i=0;i<=n;i+=2){
   // debug(i, dp[i]);
  }
  return dp[n][0];
 }

 void debug(Object...os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }
}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

■Challenge Phase

撃墜無し．

■Result

oo- +0/-0
429.5pts. 104th
おそらくDiv.1では過去最高の成績です．加えてMediumを解けたのが初めてです．

■Rating

1620 -> 1727
大幅上昇．