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通り．

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の日記

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ですが，個人的には気楽に挑戦したいと思っています．