TopCoder SRM 513

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

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

■YetAnotherIncredibleMachine(Easy)

・解法

全探索．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class YetAnotherIncredibleMachine {  
10.  // long INF=1L<<48;  
11.  int INF=1<<28;  
12.  double EPS=1e-9;  
13.   
14.  public int countWays(int[] mount, int[] length, int[] balls) {  
15.   int n=length.length;  
16.   int m=balls.length;  
17.   long res=1;  
18.   long mod=1000000009;  
19.   for(int j=0;j<n;j++){   
20.    int c=0;  
21.    for(int x=-length[j];x<=0;x++){  
22.     boolean f=true;  
23.     for(int i=0;i<m;i++){  
24.      if(mount[j]+x<=balls[i]&&balls[i]<=mount[j]+x+length[j]){  
25.       f=false;  
26.      }  
27.     }  
28.     if(f){  
29.      c++;  
30.     }  
31.    }  
32.    res=(res*c)%mod;  
33.   }  
34.   return (int)res;  
35.  }  
36.   
37.  void debug(Object...os){  
38.   System.err.println(Arrays.deepToString(os));  
39.  }  
40.   
41.  void print(String s){  
42.   System.out.print(s);  
43.  }  
44.   
45.  void println(String s){  
46.   System.out.println(s);  
47.  }  
48. }  
49.   
50.   
51. // Powered by FileEdit  
52. // Powered by TZTester 1.01 [25-Feb-2003]  
53. // Powered by CodeProcessor  

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テーブルを更新していきます．初期値の与え方が面倒なので，メモ化再帰でもいいかも知れません．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class PerfectMemory {  
10.  // long INF=1L<<48;  
11.  int INF=1<<28;  
12.  double EPS=1e-9;  
13.   
14.  public double getExpectation(int N, int M) {  
15.   int n=N*M;  
16.   double[][] dp=new double[n+1][n+1];  
17.   for(int j=2;j<=n;j+=2){  
18.    for(int i=j;i>=j/2;i--){  
19.     dp[j][i]=j/2;  
20.    }  
21.    for(int i=j/2-1;i>=0;i--){  
22.     double p1=(double)(j-2*i)/(j-i);  
23.     double p2=(double)i/(j-i);  
24.     double q1=(double)i/(j-i-1);  
25.     double q2=(double)(j-2*i-2)/(j-i-1);  
26.     double q3=(double)1/(j-i-1);  
27.     dp[j][i]+=(2+dp[j-2][i])*p1*q1;  
28.     dp[j][i]+=(1+dp[j][i+2])*p1*q2;  
29.     dp[j][i]+=(1+dp[j-2][i])*p1*q3;  
30.     if(i>0){  
31.      dp[j][i]+=(1+dp[j-2][i-1])*p2;  
32.     }  
33.    }  
34.   }  
35.   for(int i=0;i<=n;i+=2){  
36.    // debug(i, dp[i]);  
37.   }  
38.   return dp[n][0];  
39.  }  
40.   
41.  void debug(Object...os){  
42.   System.err.println(Arrays.deepToString(os));  
43.  }  
44.   
45.  void print(String s){  
46.   System.out.print(s);  
47.  }  
48.   
49.  void println(String s){  
50.   System.out.println(s);  
51.  }  
52. }  
53.   
54.   
55. // Powered by FileEdit  
56. // Powered by TZTester 1.01 [25-Feb-2003]  
57. // Powered by CodeProcessor  

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
大幅上昇．

TopCoder SRM 511

TopCoder SRM 511(7/3 1:00~3:00)

YellowCoderとしては初のSRM．

■Zoo(Easy)

・問題

うさぎと猫がN匹いる．きつねは，うさぎと猫の区別が分からない．
そこで，N匹のそれぞれに「自分と同じ種類でかつ自分より背の高い動物は何匹いますか？」と尋ねた．
この情報のみを用いて，N匹へのうさぎと猫の割り当て方の総数を求めよ．

・解法

N匹の答えをa[0],…,a[N-1]とし，
配列countを配列aに出てきた数字の個数とする．
例えば， a={0,1,0,1,2,3}
だったら，
count={2,2,1,1,0,0,…}
となる．
上の例では，一方が2匹，もう一方が4匹いると分かる．
まず，うさぎが2匹，猫が4匹とする．
このとき，a[i]が0または1のときに関しては，うさぎと猫をどのように割り当てても良い．
具体的には，
RRCC|CC
CCRR|CC
RCCR|CC
CRRC|CC
こんな感じ（2²通り）．
逆に，うさぎが4匹，猫が2匹としても，上と同じよう構成ができるので，
結局2*2²=8通り．
これは，5匹と2匹，6匹と2匹，…でも変わらない．
そのため，N=m+nと分かれる場合，
m≠nならば，2*2^min(m,n)通り，
m=nならば，2^m通り．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Zoo {  
10.  // long INF=1L<<48;  
11.  int INF=1<<28;  
12.  double EPS=1e-9;  
13.   
14.  public long theCount(int[] a) {  
15.   int n=a.length;  
16.   int[] count=new int[n];  
17.   for(int i:a){  
18.    if(i>=n){  
19.     return 0;  
20.    }  
21.    if(++count[i]>2){  
22.     return 0;  
23.    }  
24.   }  
25.   int p=0, q=0;  
26.   int k=0;  
27.   // debug(count);  
28.   for(int i=n-1;i>=0;i--){  
29.    if(count[i]==k+2){  
30.     p=q=i+1;  
31.    }  
32.    else if(count[i]==k+1){  
33.     if(k==0){  
34.      p=i+1;  
35.     }else if(k==1){  
36.      q=i+1;  
37.     }  
38.    }  
39.    else if(count[i]==k){  
40.    }  
41.    else{  
42.     return 0;  
43.    }  
44.    k=count[i];  
45.   }  
46.   // debug(p,q);  
47.   long ret=1;  
48.   for(int i=0;i<min(p,q);i++){  
49.    ret*=2;  
50.   }  
51.   return ret*(p!=q?2:1);  
52.  }  
53.   
54.  void debug(Object...os){  
55.   System.err.println(Arrays.deepToString(os));  
56.  }  
57.   
58.  void print(String s){  
59.   System.out.print(s);  
60.  }  
61.   
62.  void println(String s){  
63.   System.out.println(s);  
64.  }  
65. }  

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

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

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

 public long theCount(int[] a) {
  int n=a.length;
  int[] count=new int[n];
  for(int i:a){
   if(i>=n){
    return 0;
   }
   if(++count[i]>2){
    return 0;
   }
  }
  int p=0, q=0;
  int k=0;
  // debug(count);
  for(int i=n-1;i>=0;i--){
   if(count[i]==k+2){
    p=q=i+1;
   }
   else if(count[i]==k+1){
    if(k==0){
     p=i+1;
    }else if(k==1){
     q=i+1;
    }
   }
   else if(count[i]==k){
   }
   else{
    return 0;
   }
   k=count[i];
  }
  // debug(p,q);
  long ret=1;
  for(int i=0;i<min(p,q);i++){
   ret*=2;
  }
  return ret*(p!=q?2:1);
 }

 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);
 }
}

■FiveHundredElevenAdd(Medium)

本番は解けませんでしたので，simezi_tanさんの記事を参照下さい．
SRM 511 Div1 Medium FiveHundredEleven - simezi_tanの日記

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class FiveHundredEleven {  
10.  // long INF=1L<<48;  
11.  int INF=1<<28;  
12.  double EPS=1e-9;  
13.   
14.  int[][] memo; // 0:win, 1:lose  
15.  int[] cards;  
16.  int n;  
17.   
18.  int rec(int step,int mem){  
19.   if(memo[step][mem]>=0){  
20.    return memo[step][mem];  
21.   }  
22.   if(mem==511){  
23.    // former player loses.  
24.    return memo[step][mem]=0;  
25.   }  
26.   if(step==n){  
27.    // the player can't choose a card.  
28.    return memo[step][mem]=1;  
29.   }  
30.   int not=0;  
31.   for(int i=0;i<n;i++){  
32.    if((mem|cards[i])==mem){  
33.     not++;  
34.    }  
35.   }  
36.   boolean win=false;  
37.   // search : not-step cards that don't affect mem are not used  
38.   if(not>step){  
39.    win|=rec(step+1,mem)==1;  
40.   }  
41.   // search : cards that affect mem.  
42.   for(int i=0;i<n;i++){  
43.    if((mem|cards[i])!=mem){  
44.     win|=rec(step+1,mem|cards[i])==1;  
45.    }  
46.   }  
47.   return memo[step][mem]=win?0:1;  
48.  }  
49.   
50.  public String theWinner(int[] cards) {  
51.   this.cards=cards;  
52.   n=cards.length;  
53.   memo=new int[n+1][512];  
54.   for(int i=0;i<n+1;i++){  
55.    fill(memo[i],-1);  
56.   }  
57.   return rec(0,0)==0?"Fox Ciel":"Toastman";  
58.  }  
59.   
60.  void debug(Object...os){  
61.   System.err.println(Arrays.deepToString(os));  
62.  }  
63.   
64.  void print(String s){  
65.   System.out.print(s);  
66.  }  
67.   
68.  void println(String s){  
69.   System.out.println(s);  
70.  }  
71. }  

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

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

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

 int[][] memo; // 0:win, 1:lose
 int[] cards;
 int n;

 int rec(int step,int mem){
  if(memo[step][mem]>=0){
   return memo[step][mem];
  }
  if(mem==511){
   // former player loses.
   return memo[step][mem]=0;
  }
  if(step==n){
   // the player can't choose a card.
   return memo[step][mem]=1;
  }
  int not=0;
  for(int i=0;i<n;i++){
   if((mem|cards[i])==mem){
    not++;
   }
  }
  boolean win=false;
  // search : not-step cards that don't affect mem are not used
  if(not>step){
   win|=rec(step+1,mem)==1;
  }
  // search : cards that affect mem.
  for(int i=0;i<n;i++){
   if((mem|cards[i])!=mem){
    win|=rec(step+1,mem|cards[i])==1;
   }
  }
  return memo[step][mem]=win?0:1;
 }

 public String theWinner(int[] cards) {
  this.cards=cards;
  n=cards.length;
  memo=new int[n+1][512];
  for(int i=0;i<n+1;i++){
   fill(memo[i],-1);
  }
  return rec(0,0)==0?"Fox Ciel":"Toastman";
 }

 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);
 }
}

■Challenge Phase

撃墜無し．撃墜しようと準備していましたが，他の人のコードが中々読めませんでした．

■Result

o-- +0/-0
144.29pts. 491th

■Rating

1532 -> 1527
微減．次は，TCO Round3ですが，個人的には気楽に挑戦したいと思っています．