主にコーディング: TopCoder

ラベル TopCoder の投稿を表示しています。すべての投稿を表示

2011年9月11日日曜日

TopCoder SRM 517

TopCoder SRM 517 (9/11 1:00~3:00)

■CompositeSmash(Easy)

問題

ある数xをy≧2，z≧2，yz=xを満たす2つの数に分割する．
この分割操作を再帰的に繰り返す．
e.g., x=12ならば，(y,z)=(3,4) or (2,6)など．
1や素数は，それ以上分割できない．

初期値としてNが与えられる．
Nを任意の方法で分割していき，全ての分割が終了するまでにtargetが出現するかを判定せよ．

解法

全探索．念の為メモ化もしたが，無くても通る様子．
SRM 517 Div. 1 Easy CompositeSmash

■Result

o-- +0/-0
191.33pts. 301th

■Rating

1645->1673

2011年9月3日土曜日

TopCoder SRM 513

TopCoder SRM 516(8/31 0:00~2:00)

敗北．

■NetworkXOneTimePad(Easy)

・解法

全探索．
Long.parseLong(str, 2)をLong.parseLong(str)と書いてしまい，終了数分前に直すはめになってしまった．

■Challenge Phase

TLEが狙えるかと思ったが撃墜失敗．むしろ，サンプルの弱さを考慮した撃墜を作っておくべきだった．

■Result

o-- +0/-1
50.0pts. 489th

■Rating

1727 -> 1645
捻挫+打撲．

2011年7月27日水曜日

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

2011年7月4日月曜日

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

2011年6月29日水曜日

TCO Algorithm Round2

TCO Algorithm Round2(6/26 1:00~3:00)

驚異の悪運によりRound1を通過することが出来ていましたが，果してRound2は…．

■GuessTheNumberGame(Easy)

ある数字Mを1~Nまでの数で割り切れるかどうかを表す文字列を考える．例えばM=4，N=5とすると4は1,2,4で割り切れ，3,5では割り切れないので， YYNYN となる．さて，N=5のとき， YNNYN となるようなMは存在しないため，この文字列は無効である（4で割り切れて、2で割り切れないから）．長さMの文字列で，有効なものは何種類あるか． 2種類以上の素数の積からなる合成数は，素因数のY or Nで一意に決まってしまうので，考慮しない．例えば， YYY--XならX=Y YYN--XならX=N YNY--XならX=N YNN--XならX=N となる．次に，ある素数の冪乗を考える．例えば，M=9とすると，2の冪乗は2,4,8まで．この3つに着目した有効な文字列は， NNN YNN YYN YYY の4種類．つまり，p¹, p²,…, p^rについて有効な文字列はr+1種類．あとは，それらを掛け合わせるだけ．

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

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

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

 public int possibleClues(int n) {
  long res=1;
  long mod=1000000007;
  boolean[] isP=new boolean[n+1];
  int[] p=new int[n+1];
  fill(isP,true);
  isP[0]=isP[1]=false;
  int k=0;
  for(int j=0;j<=n;j++){
   if(!isP[j]){
    continue;
   }
   p[k++]=j;
   for(int i=j*2;i<=n;i+=j){
    isP[i]=false;
   }
  }
  // debug(p);
  for(int i=0;i<k;i++){
   int c=0;
   for(long m=1;m<=n;m*=p[i]){
    c++;
   }
   // debug(i,p[i],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);
 }
}

■Challenge Phase

撃墜無し．

■Result

o-- +0/-0
196.11pts. 341th
辛くも逃げきることが出来ました．

■Rating

1431 -> 1530
Round3進出+初YellowCoderです．今年のICPCは国内予選で落ちてしまったので，中々にショックでしたが，代わりにGoogleとTopCoder両方のTシャツをゲットできそうです．

2011年6月19日日曜日

TCO Algorithm Round1

TCO Algorithm Round1(6/19 1:00~3:00)

■TripleStrings(Easy)

キューA，B，Cがある．最初，キューAには'o'と'x'から構成される文字列(=init)が入っており，キューB，Cは空である． Aからポップした文字は，BとCにプッシュできる． B，Cからポップした文字は，Aにプッシュできる．キューA内の文字列をinitからgoalに変更するためのポップの回数の最小値を返せ．

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

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

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

 public int getMinimumOperations(String init, String goal) {
  int n=init.length();
  int max=0;
  for(int j=1;j<=n;j++){
   boolean f=true;
   for(int i=0;i<j;i++){
    f&=init.charAt(n-j+i)==goal.charAt(i);
   }
   if(f){
    max=max(max,j);
   }
  }
  return (n-max)*2;
 }

 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

撃墜無し．Challengeボタンをポチるコンマ数秒前に他の人に撃墜されました．

■Result

o-- +0/-0
232.61pts. 837th

■Rating

1414 -> 1431
残念…．

2011年6月6日月曜日

TopCoder SRM 508

SRM 508(6/3 0:00~2:00)

■DivideAndShift(Easy)

答えをf(n,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 DivideAndShift {
 int INF=1<<28;
 double EPS=1e-9;

 int rec(int n, int m){
  if(m==0){
   return 0;
  }
  HashMap<Integer,Integer> map=primeFactor(n);
  int res=min(m,n-m);
  for(int p:map.keySet()){
   if(p==1){
    continue;
   }
   res=min(res,rec(n/p,m%(n/p))+1);
  }
  return res;
 }

 public int getLeast(int n, int m) {
  return rec(n,m-1);
 }
 
 HashMap<Integer, Integer> primeFactor(int n){
  HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
  for(int i=2; i*i<=n; i++){
   int c=0;
   for(; n%i==0; n/=i)
    c++;
   if(c>0)
    map.put(i, c);
  }
  if(n!=1)
   map.put(n, 1);
  return map;
 }

 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
125.55pts. 406th

■Rating

1365 -> 1414
微増．目標の1500にはいつ到達できるのか…．

2011年5月29日日曜日

TopCoder SRM 507

SRM 507(5/29 1:00~3:00)

黄色くなれませんでした…．

■TheNumbersWithLuckyLastDigit(Easy)

6～50枚の色タイルが与えられる．その中から，6枚を選び出し，立方体に貼り付ける．
どの面についても，辺で接している面とは色が異なっていなければならない．
そのようなタイルの貼り付けたは存在するか．

最初にDFSで全探索しようと思ったのが間違いでした．
実際，色ごとのタイルの枚数を調べて場合分けすれば求まるのです（もっと完結に書くことも出来ます）．

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

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

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

 public String isPossible(String[] ss) {
  HashMap<String,Integer> map=new HashMap<String,Integer>();
  for(String s:ss){
   if(!map.containsKey(s)){
    map.put(s,0);
   }
   map.put(s,map.get(s)+1);
  }
  if(map.size()>=5){
   return "YES";
  }
  if(map.size()==4){
   int c=0;
   for(int e:map.values()){
    if(e>=2){
     c++;
    }
   }
   return c>=2?"YES":"NO";
  }
  if(map.size()==3){
   for(int e:map.values()){
    if(e<2){
     return "NO";
    }
   }
   return "YES";
  }
  return "NO";
 }
 
 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);
 }
}

■CubePacking(Medium)

1辺の長さが1の立方体Ns個と，1辺の長さがLの立方体Nb個とを詰めることが出来る直方体の最小体積を求めよ．
実は結構簡単で，3辺の内の2辺を決めると，もう1辺はすぐ求まります．
ですので，2辺を全探索しつつ，体積を算出し最小値を求めれば良いのです．
本番中は解けませんでした…．

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

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

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

 public int getMinimumVolume(int m, int n, int len) {
  long ans=INF;
  for(long a=1;a*a*a<=INF;a++){
   for(long b=a;a*b*b<=INF;b++){
    long base=(a/len)*(b/len);
    if(base==0){
     continue;
    }
    long c=((n-1)/base+1)*len;
    long rest=m-(a*b*c-len*len*len*n);
    if(rest>0){
     c+=(rest-1)/(a*b)+1;
    }
    ans=min(ans,a*b*c);
   }
  }
  return (int)ans;
 }
 
 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

撃墜無し．SystemTestで落ちた人もRoom内には居ませんでした．

■Result

o-- +0/-0
144.37pts. 683th

■Rating

1442 -> 1365
前々回のレートに戻ってしまいました…．

2011年5月18日水曜日

TopCoder SRM 504.5

SRM 504.5(5/18 0:00~2:00)

多忙でしたが，折角なので参加することにしました．

■TheNumbersWithLuckyLastDigit(Easy)

実際にいくつか試してみると，10で割った余りで"ほぼ"決まることが分かります．

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

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

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

 public int find(int n) {
  int[] a={5,2,3,5,1,3,4,1,2,4};
  boolean[] out=new boolean[20];
  out[1]=out[2]=out[3]=out[5]=out[6]=out[9]=out[10]=out[13]=true;
  if(n<20&&out[n]){
   return -1;
  }else{
   return a[n%10];
  }
 }

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

■TheJackpotDivOne(Medium)

本番ではdoubleを使っていたので，アンダーフロー(?)による精度落ちで撃墜されました．下が修正コード．JavaならばBigIntegerが使えます．

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

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

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

 public long[] find(long[] a, long m) {
  int n=a.length;
  for(;;){
   int k=n-1;
   BigInteger ave=BigInteger.ZERO;
   boolean same=true;
   for(int i=n-1;i>=0;i--){
    if(a[i]<=a[k]){
     k=i;
    }
    same&=a[0]==a[i];
    ave=ave.add(BigInteger.valueOf(a[i]));
   }
   if(same){
    break;
   }
   long x=ave.divide(BigInteger.valueOf(n)).longValue()-a[k]+1;
   if(m>=x){
    a[k]+=x;
    m-=x;
   }else{
    a[k]+=m;
    sort(a);
    return a;
   }
  }
  for(int i=0;i<n;i++){
   a[i]+=m/n;
   if(i<m%n){
    a[i]++;
   }
  }
  sort(a);
  return a;
 }

 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

Easyで一人撃墜．

■Result

ox- +1/-0
241.3pts. 299th
前回の教訓を生かし，1撃墜に止めました．

■Rating

1360 -> 1442
黄色くなれるか…?!

2011年5月15日日曜日

TCO11 Algo Qual1

TCO11 Algo Qual1(5/15 1:00~3:00)

■MinimumLiars(Easy)

考えられる全ケースを試すだけ．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class MinimumLiars {
 int INF=1<<28;
 double EPS=1e-9;

 public int getMinimum(int[] a) {
  int n=a.length;
  for(int j=0;j<=n;j++){
   int s=0;
   for(int i=0;i<n;i++){
    if(a[i]>j){
     s++;
    }
   }
   if(j==s){
    return j;
   }
  }
  return -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);
 }

 public static void main(String[] args) {
  // MinimumLiars temp = new MinimumLiars();
  // System.out.println(temp.getMinimum(int[] claim));
 }
}

■FoxListeningToMusic(Medium)

O(Tn)じゃないとSystem Testで落ちます．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class FoxListeningToMusic {
 int INF=1<<28;
 double EPS=1e-9;

 public double[] getProbabilities(int[] a, int t) {
  int n=a.length;
  double[] dp=new double[t+1];
  dp[0]=1./n;
  for(int k=0;k<t;k++){
   double[] d=new double[n];
   for(int i=0;i<n;i++){
    d[i]+=dp[k]/n;
   }
   for(int i=0;i<n;i++){
    if(k+a[i]<=t){
     dp[k+a[i]]+=d[i];
    }
   }
  }
  // debug(dp);
  double[] res=new double[n];
  for(int i=0;i<n;i++){
   for(int j=t;j>t-a[i]&&j>=0;j--){
    res[i]+=dp[j];
   }
  }
  return 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);
 }

 public static void main(String[] args) {
 }
}

■Challenge Phase

Mediumにて，O(Tn²)の人を狙ったのですが，3回もミスしてしまいました．

■Result

○○× +1 -3
478.98pts. 332th

■Rating

1279 -> 1360
600位以内なので，次のラウンドへ．Round1も残りたいですね．

2011年4月19日火曜日

TopCoder Member SRM 503 Div1 Medium KingdomXCitiesandVillages

■KingdomXCitiesandVillages

問題・解説は，Match Editorial Archiveを参考に．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class KingdomXCitiesandVillages {
 int INF=1<<28;
 double EPS=1e-9;

 int m, n;

 public double determineLength(int[] cx, int[] cy, int[] vx, int[] vy) {
  m=cx.length;
  n=vx.length;
  double sum=0;
  for(int j=0;j<n;j++){
   LinkedList<R> list=new LinkedList<R>();
   for(int i=0;i<n;i++){
    if(i!=j){
     list.add(new R(Math.hypot(vx[j]-vx[i], vy[j]-vy[i]), false));
    }
   }
   for(int i=0;i<m;i++){
    list.add(new R(Math.hypot(vx[j]-cx[i], vy[j]-cy[i]), true));
   }
   R[] rs=list.toArray(new R[0]);
   Arrays.sort(rs);
   for(int i=0;i<rs.length;i++){
    if(rs[i].isCity){
     sum+=rs[i].d/(i+1);
     break;
    }else{
     sum+=rs[i].d/(i+1)/(i+2);
    }
   }
  }
  return sum;
 }

 class R implements Comparable<R>{
  double d;
  boolean isCity;
  R(double d, boolean isCity){
   this.d=d;
   this.isCity=isCity;
  }
  public int compareTo(R r){
   if(d-r.d+EPS<0){
    return -1;
   }else if(d-r.d>0+EPS){
    return 1;
   }else{
    return 0;
   }
  }
 }
}


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

2011年4月17日日曜日

TopCoder Member SRM 503

SRM 503(12/19 1:00~3:00)

■FoxMakingDice(Div1 Easy)

Toastmanは，パンを何枚か焼きたい．パンには幾つかの種類があり，ある種類のパンは，X分未満焼くとunder toasted，X分超過焼くとover toastedとなる．
Toastmanは，パンを焼いたが，m_i分焼いてunder toastedだったもの，また，n_i分焼いてover toastedだったものが出来た．Toastmanは何種類のパンを用いたかを覚えていないが，ある種類のパンを焼いたときにunder toasted・over toastedだったものがそれぞれ少なくとも1枚以上はあったという．
パンの種類の最小数を答えよ．

under toastedだったものをU，over toastedだったものをOとし，それらを焼かれた時間の数直線にプロットする．例えば下図．
UOUOOUOUOUOUO

・パンの種類が1つで良い場合．

UUUUU | OOOOOO
上のような場合．Xは，"|"で表される．

・パンが何種類あっても不可能な場合．

O…………
または，
…………U
の場合．

・パンの種類が2つで良い場合．

上記のどれにも当てはまらない場合．
何故なら，必ずパンの順列は，
U[…………]O
となり，
U | […………]O
で分けると，
[…………]内のOは全て排除され．
[U……U]O
となる．その後，
[U……U] | O
で分ければ終了する．

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

public class ToastXToast {
 int INF=1<<28;
 double EPS=1e-9;

 public int bake(int[] a, int[] b) {
  Arrays.sort(a); // o
  Arrays.sort(b); // x
  boolean f=true;
  for(int j=0;j<b.length;j++){
   for(int i=0;i<a.length;i++){
    f&=a[i]<b[j];
   }
  }
  if(f){
   return 1;
  }
  else if(a[0]>b[0]||a[a.length-1]>b[b.length-1]){
   return -1;
  }
  else if(a.length>=2&&b.length>=2){
   return 2;
  }
  else{
   return -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);
 }

 public static void main(String[] args) {
  ToastXToast temp = new ToastXToast();
 }
}

■Result

○×× 0 0
144.26pt.

■Rating

1243 -> 1279
若干上昇．少しずつRatingを上げていきたいものです…．

2010年12月22日水曜日

TopCoder SRM 491

SRM 491(12/19 2:00~4:00)

悪夢は続く．

■FoxMakingDice(Div1 Easy)
立方体サイコロの各面に1~nまでの数字を割り振る．ある面とその対になる面の和はどの面についても等しく，かつk以上で開ければならない．
nとkが与えられた時，条件を満たすサイコロは何種類あるか．

問題を読み間違えてたので無理ゲーじゃん，と思っていました．

コンテスト後，他の人の回答を見たら，非常に明快に解けることが分かりました．

1. 和sumはk以上2n-1以下．
2. a<bで，a+b=sumとなる対a-bの数waysを数える．
3. ways個から3個を選択する選び方は，_waysC₃
4. ↑の値を全てのsumについて和を取る．
5. (a-b, c-d, e-f)という選び方をするサイコロは(同位体みたいな感じを想像すると)2通りある事が分かるので，最後に2をかける．

これを書くだけです．

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

public class FoxMakingDice {
 int INF=1<<28;
 double EPS=1e-9;

 public long theCount(int n, int k) {
  long res=0;
  for(int sum=k;sum<=2*n-1;sum++){
   long ways=0;
   for(int first=1;first<=n&&first<sum-first;first++){
    if(sum-first<=n){
     ways++;
    }
   }
   res+=ways*(ways-1)*(ways-2)/6;
  }
  res*=2;
  return 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);
 }
}

■Result
××× 0 0
0.0p

■Rating
1348 -> 1266

今年の目標は残念ながら達成出来そうに無いです…．

2010年11月20日土曜日

TopCoder 練習 SumsOfPerfectPowers(SRM 350 Div1 Easy)

SumsOfPerfectPowers(SRM 350 Div1 Easy)

■問題
本家参照．

■解法
chokudaiさんのニコ生を追従して解いた．指数は2以上なので，a^mまたはb^kの候補を先に作っておく．あとは2重ループで条件を満たす数のフラグを立てるだけ．

import java.util.*;

public class SumsOfPerfectPowers{
 public int howMany(int lowerBound, int upperBound){
  boolean[] dp=new boolean[upperBound+1];
  TreeSet<Integer> set=new TreeSet<Integer>();
  set.add(0);
  set.add(1);
  for(int a=2;a*a<=upperBound;a++){
   for(long r=a*a;r<=upperBound;r*=a){
    set.add((int)r);
   }
  }
  for(int a:set){
   for(int b:set){
    if(a+b<=upperBound){
     dp[a+b]=true;
    }
   }
  }
  int ret=0;
  for(int i=lowerBound;i<=upperBound;i++){
   if(dp[i]){
    ret++;
   }
  }
  return ret;
 }
}

TopCoder 練習 KnightsTour(SRM 447 Div1 Easy)

KnightsTour(SRM 447 Div1 Easy)

■問題
本家参照．

■解法
組むだけ．特に高速化の必要もありませんでした．

import java.util.*;
import java.lang.*;

public class KnightsTour{
 int[] dx={1,-1,2,-2,2,-2,1,-1};
 int[] dy={2,2,1,1,-1,-1,-2,-2};
 public int visitedPositions(String[] ss){
  boolean[][] visited=new boolean[8][8];
  int x=0,y=0;
  for(int j=0;j<8;j++){
   for(int i=0;i<8;i++){
    if(ss[j].charAt(i)=='K'){
     x=i;
     y=j;
    }
   }
  }
  visited[y][x]=true;
  int[] num=new int[8];
  for(int c=1;;c++){
   Arrays.fill(num,9);
   for(int j=0;j<8;j++){
    int nx=x+dx[j];
    int ny=y+dy[j];
    if(nx<0||nx>=8||ny<0||ny>=8||visited[ny][nx]||ss[ny].charAt(nx)=='*'){
     continue;
    }
    num[j]=0;
    visited[ny][nx]=true;
    for(int i=0;i<8;i++){ 
     int nnx=nx+dx[i];
     int nny=ny+dy[i];
     if(nnx<0||nnx>=8||nny<0||nny>=8||visited[nny][nnx]||ss[nny].charAt(nnx)=='*'){
      continue;
     }
     num[j]++;
    }
    visited[ny][nx]=false;
   }
   int k=0;
   for(int i=0;i<8;i++){
    if(num[i]<=num[k]){
     k=i;
    }
   }
   if(num[k]>8){
    return c;
   }
   x+=dx[k];
   y+=dy[k];
   visited[y][x]=true;
   // System.out.println(x+","+y);
   // System.out.println("num["+k+"]="+num[k]);
  }
 }
}

2010年11月14日日曜日

TopCoder 練習 CandidateKeys(SRM 386 Div1 Easy)

CandidateKeys(SRM 386 Div1 Easy)

■問題
本家参照．

■解法
ある列群がcandidate superkeyであるかどうかは，以下を判定すれば良い．
・その列群がsuperkeyである
・その列群の真部分集合の全要素がcandidate superkeyでない
superkeyかどうかの判断は，愚直に実装すればOK．
部分集合のビット演算は，「蟻本」の助けを借りました…．

public class CandidateKeys{
 int n, m;
 String[] table;
 public int[] getKeys(String[] table){
  n=table.length;
  m=table[0].length();
  this.table=table;
  boolean[] candidate=new boolean[1<<m];
  int min=-1, max=0;
  for(int sup=0;sup<1<<m;sup++){
   if(isSuperKey(sup)){
    boolean f=true;
    for(int sub=(sup-1)&sup;sub!=0;sub=(sub-1)&sup){
     f&=!candidate[sub];
    }
    candidate[sup]=f;
    if(f){
     int bit=Integer.bitCount(sup);
     if(min==-1||bit<min){
      min=bit;
     }
     if(bit>max){
      max=bit;
     }
    }
   }
   // System.out.println(Integer.toString(sup,2)+":"+isSuperKey(sup)+":"+candidate[sup]);
  }
  if(min==-1){
   return new int[0];
  }
  else{
   return new int[]{min, max};
  }
 }
 
 boolean isSuperKey(int sup){
  if(sup==0) return false;
  String[] ss=new String[n];
  for(int j=0;j<n;j++){
   int s=sup;
   ss[j]="";
   for(int i=m-1;i>=0;i--){
    if((s&1)==1){
     ss[j]=table[j].charAt(i)+ss[j];
    }
    s>>=1;
   }
  }
  for(int j=0;j<n;j++){
   for(int i=j+1;i<n;i++){
    if(ss[i].equals(ss[j])){
     return false;
    }
   }
  }
  return true;
 }
}

TopCoder 練習 PrimeSequences(Member SRM 471 Div1 Easy)

PrimeSequences(Member SRM 471 Div1 Easy)

■問題
ある自然数nについて，
n,[n/2],[[n/2]/2],[[[n/2]/2]/2],…
を考える．数列の第1項から連続した素数の個数が少なくともDである数の内，N以下で最大のものを計算せよ．

■解法
ほぼやるだけ．Nがそれ程大きくないので，素数全列挙で大丈夫でした．

import java.util.*;
import java.lang.*;

public class PrimeSequences{
 public int getLargestGenerator(int N, int D){
  int max=10000000;
  boolean[] ps=new boolean[max+1];
  Arrays.fill(ps,true);
  ps[0]=ps[1]=false;
  for(int i=2;i<=10000000;i++){
   if(ps[i]){
    for(int j=2;i*j<=10000000;j++){
     ps[i*j]=false;
    }
   }
  }
  int[] a=new int[max+1];
  for(int i=2;i<=max;i++){
   //System.out.println(i+":"+ps[i]);
   if(ps[i]&&a[i]==0){
    int k=1;
    for(int j=i;j<=max&&ps[j];j=j*2+1){
     a[j]=k++;
    }
   }
  }
  int ret=-1;
  for(int i=0;i<=N;i++){
   //System.out.println(i+":"+a[i]);
   if(a[i]>=D){
    ret=i;
   }
  }
  return ret;
 }
}

TopCoder 練習 SequenceOfCommands(SRM 473 Div1 Easy)

SequenceOfCommands(SRM 473 Div1 Easy)

■問題
ロボットに命令を与える．命令は，前進，左回転，右回転からなる．与えられた命令列を永遠に実行した場合，ロボットは初期地点から無限に遠ざかるか，そうでないか，を判定せよ．

■解法
ロボットの向きは上下左右の4通りしか無い．よって，命令列を4回実行すれば必ず元の向きを向く．この時初期地点に居なければ，ロボットが無限遠へ行ってしまうのは明らか．

public class SequenceOfCommands{
 public String whatHappens(String[] commands){
  String ss="";
  for(String s:commands){
   ss+=s;
  }
  ss=ss+ss+ss+ss;
  int x=0,y=0,d=0;
  int[] dx={1,0,-1,0};
  int[] dy={0,1,0,-1};
  for(char c:ss.toCharArray()){
   if(c=='S'){
    x+=dx[d];
    y+=dy[d];
   }
   else if(c=='L'){
    d=(d+3)%4;
   }
   else{
    d=(d+1)%4;
   }
  }
  return x==0&&y==0?"bounded":"unbounded";
 }
}

TopCoder 練習 Islands(SRM 477 Div1 Easy)

Islands(SRM 477 Div1 Easy)

■問題
六角セルのフィールドが与えられる．各セルはWaterかLandである．WaterセルとLandセルに挟まれたBeachの合計長は幾らか．

■解法
あるセルに隣接するセルは6つあるので，各セルの右，右下，左下を調べれば良い．

public class Islands{
 public int beachLength(String[] str){
  int ret=0;
  // j:even (i+1,j), (i,j+1), (i-1,j+1)
  // j:odd (i+1,j), (i+1,j+1), (i,j+1)
  int n=str.length;
  int m=str[0].length();
  for(int j=0;j<n;j++){
   for(int i=0;i<m;i++){
    int[] dx, dy;
    if(j%2==0){
     dx=new int[]{1,0,-1};
     dy=new int[]{0,1,1};
    }else{
     dx=new int[]{1,1,0};
     dy=new int[]{0,1,1};
    }
    for(int d=0;d<3;d++){
     int x=i+dx[d];
     int y=j+dy[d];
     if(0<=x&x<m&&0<=y&&y<n&&str[j].charAt(i)!=str[y].charAt(x)){
      ret++;
     }
    }
   }
  }
  return ret;
 }
}

TopCoder SRM 487

SRM 487(11/14 2:00~4:00)

悪夢再び…．

■BunnyComputer(Div1 Easy)

コンピュータのスケジューリングを考える問題．詳細は本家サイトを御参照下さい…．

0，…，kのそれぞれはどう選んでも干渉しないので，それぞれにおいて適当に判定すれば大丈夫，とか思いましたが，ちゃんとDPで最大値を計算しないとダメでした…．

wataさんのコードを参考にしたコードはこちら．

public class BunnyComputer{
 public int getMaximum(int[] pre, int k){
  int n=pre.length;
  int res=0;
  for(int j=0;j<k+1;j++){
   int dp1=0, dp2=0;
   for(int i=j;i+k+1<n;i+=k+1){
    int a1=Math.max(dp1,dp2);
    int a2=dp1+pre[i]+pre[i+k+1];
    dp1=a1;
    dp2=a2;
   }
   res+=Math.max(dp1,dp2);
  }
  return res;
 }
}

仮にk=0，preference={3,1,4,1,5,9,2,6}とします．
隣り合う2項を足し合わせれば，
a={4,5,5,6,14,11,8}
となります．言い換えれば，「数列aより，隣り合う2項を選ばないように抽出した項の総和を最大にしたい」という事ですので，これはシンプルなDPとなるのです．

■Challenge
撃墜しようとしたらされて…．

■Result
××× 0 0
0.0p

■Rating
1399 -> 1348

2連続減少．実に良くないですねえ．

登録: 投稿 (Atom)

SRM	Easy	Normal	Hard
295	o	-	-
296	o	-	-
297	o	-	-
298	o	-	-
350	o	-	-
386	o	-	-
447	o	-	-
451	o	-	-
462	o	-	-
463	o	-	-
464	o	-	-
465	o	-	-
466	o	-	-
469	o	-	-
471	o	-	-
472	o	-	-
473	o	-	-
474	o	-	-
475	o	-	-
476	o	-	-
477	o	-	-
478	o	-	-
479	o	-	-
480	o	-	-
481	o	-	-
482	o	o	-
483	o	-	-
484	o	-	-
485	o	-	-
486	o	-	-
487	o	-	-
503	-	o	-
511	-	o	-

1	hello world	30B
2	echo	31B
3	99 shinichiroes of hamaji	258B
4	example com	451B
5	Smileys Triangle	63B
8	delete blank lines	37B
14	ultimate problem	19B
16	even lines	40B
19	Fibonacci Numbers	46B
34	FizzBuzz	84B
48	google	67B

2011年9月11日日曜日

2011年9月3日土曜日

2011年7月27日水曜日

2011年7月4日月曜日

2011年6月29日水曜日

2011年6月19日日曜日

2011年6月6日月曜日

2011年5月29日日曜日

2011年5月18日水曜日

2011年5月15日日曜日

2011年4月19日火曜日

2011年4月17日日曜日

2010年12月22日水曜日

2010年11月20日土曜日

2010年11月14日日曜日

Label

Blog Archive

Self Introduction

Link

Project Euler

Single Round Match Div1 Practice

anarchy golf

Books

CD/DVD

2011年の目標

買う

Memo