Google Code Jam 2012 Round1 突破!

今日はコーディングづくしの日でした。Round1 Bに関しては、同日1時に行われましたが、
これは5/5に書きます。

ということで後がなくなった朝から夕方にかけては、タイピングゲームの開発を続行しました。
昨日直しきれなかった部分です。この日は非常に暑かったので、リビングで作業しました。
Google Code Jam 2012 Round1 突破!_f0019846_2371435.jpg

室内は30度オーバー。
更に、Tabキーでのワードの切り替え、Escキーでのカーソル解除、
また、複数ワードがある場合、入力したい先頭のワードを判別する仕組みを導入しました。
苦労したところとしましては、枠を作るところでしょうか。
座標を正確に作らないといけないのが苦しいです。

夕方には天気が一時的に急激に悪化して、ひょうが降って来ました。
つくばに関していえば、竜巻が発生し、甚大な被害をもたらしたようです。

さて、リリース直後に、入力の柔軟性が反映されていない、nullになるなどのバグがありましたが、
18時にGoogle Code Jamを控えているので、後ほど訂正といったところで。

まず、問題を見通す。うーん、A問題はsmallの得点が高くて難しそうだけど、
largeの得点も一緒だから、ここからやるのがよさそうかなー?

ということでAから見る。どうやらダイヤモンドインヘリタンスという関係があって、
AからBへ向かうまでの経路が複数あれば、ダイヤモンドインヘリタンスというらしい。
んで、このダイヤモンドインヘリタンスが有るかどうかに関して判別するという問題でした。
最初はこれ、再帰使わないと無理じゃない・・・。と思い、絶望していました。
そして、その後にこれ、Queue使えばいけるんじゃないかと思いたち、
昔の記憶をたどってプログラミングする。
つまり、スタートの状態をpushして、ゴールに行くまでに、
既に通った(フラグをtrue)にした経路があればYesを返せば良いということ。
これで組んでみたらなんとかできました。
と思い、提出してみるとwrong answer。
なぜだー!と思い、問題文を確認。別にスタートが1からというふうに決まっているわけではなく、
これはただのCase:#1からですよということだったので、
全てに関してpushして判定してみればいいんじゃないかということで、for文増やす。
無事correctして、歓喜。Largeは時間大丈夫かなーという不安もありましたが、
まー1000ノードぐらいなら実験やったことあるしなんとでもなるでしょうという自信があったので、
そのまま実行。これがうまくいって、提出終了。

import java.util.*;
import java.io.*;

public class Test {

public static void main(String args[]) throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/A-small-attempt1.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int n = input.nextInt();
for(int i = 0 ; i < n ; i++){
int n2 = input.nextInt();
boolean[][] con = new boolean[n2][n2];
for(int j = 0 ; j < n2 ; j++){
int r = input.nextInt();
for(int k = 0 ; k < r ; k++){
int l = input.nextInt();
con[j][l-1] = true;
}
}
pw.println("Case #"+(i+1)+": "+num(n2,con));
}
input.close();
pw.flush();
pw.close();
}

public static String num(int n2,boolean[][] con){
Queue q = new PriorityQueue();
for(int k = 0 ; k < con.length ; k++){
q.add(k);
boolean[] isok = new boolean[n2];
isok[k] = true;
while(!q.isEmpty()){
int st = q.poll();
for(int i = 0 ; i < con[st].length ; i++){
if(con[st][i] == true){
if(isok[i] == true){
return "Yes";
}
q.add(i);
isok[i] = true;
}
}
}
}
return "No";
}
}

これは結構綺麗に書けたなーと自分でも思っています。

次にB問題を見る。文章長いし、なんか物理系の問題そう・・・。
だるい、無理!ということでC問題に移動。

C問題は、箱が数種類あって、順番に連続で何個か流れる。
商品が数種類あって、順番に連続で何個か流れる。

使える操作は以下のとおり
・箱を捨てる
・商品を捨てる
・箱と商品の番号が一致したときにのみ格納できる

格納できる最大数を求めよ

という問題。ちなみにsmallはかなり条件が緩く、流れてくるものは最大でも3区分だけです。
これはどうやって解けばいいんだろうと、相当悩みました。
そして何度もwronganswerを出しました。
時間が刻々と過ぎていき、順位は1200位後半。もうだめか・・・と思っていたが、
smallは全探索でも十分いけそうということで、すべての状態に関してQueueを使って
網羅していった。結果、correctし、700位代へ。後25分といったところ。

import java.util.*;
import java.io.*;

public class Test {

public static void main(String args[]) throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/C-small-attempt2.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int n = input.nextInt();
for(int i = 0 ; i < n ; i++){
int n2 = input.nextInt();
int m = input.nextInt();
long a[] = new long[n2];
int A[] = new int[n2];
long b[] = new long[m];
int B[] = new int[m];
for(int j = 0 ; j < n2 ; j++){
a[j] = input.nextLong();
A[j] = input.nextInt();
}
for(int j = 0 ; j < m ; j++){
b[j] = input.nextLong();
B[j] = input.nextInt();
}
pw.println("Case #"+(i+1)+": "+num(n2,m,a,A,b,B));
}
input.close();
pw.flush();
pw.close();
}

public static long num(int n2,int m,long[] a,int[] A,long[] b,int[] B){
long max = 0;
Queue q = new PriorityQueue();
q.add(0+","+0+","+0+","+a[0]+","+b[0]);
while(!q.isEmpty()){
String[] sl = q.poll().split(",");
int aindex = Integer.parseInt(sl[0]);
int bindex = Integer.parseInt(sl[1]);
long sum = Long.parseLong(sl[2]);
long rest = Long.parseLong(sl[3]);
long restb = Long.parseLong(sl[4]);
if(aindex == a.length || bindex == b.length){
max = Math.max(max,sum);
}else{
if(A[aindex] == B[bindex]){
if(rest > restb){
if(bindex+1 != b.length){
q.add(aindex+","+(bindex+1)+","+(sum+restb)+","+(rest-restb)+","+b[bindex+1]);
}else{
q.add(aindex+","+(bindex+1)+","+(sum+restb)+","+(rest-restb)+","+0);
}
}else{
if(aindex+1 != a.length){
q.add((aindex+1)+","+bindex+","+(sum+rest)+","+a[aindex+1]+","+(restb-rest));
}else{
q.add((aindex+1)+","+bindex+","+(sum+rest)+","+0+","+(restb-rest));
}
}
}else{
if(aindex+1 != a.length){
q.add((aindex+1)+","+bindex+","+sum+","+a[aindex+1]+","+restb);
}else{
q.add((aindex+1)+","+bindex+","+sum+","+0+","+restb);
}
if(bindex+1 != b.length){
q.add(aindex+","+(bindex+1)+","+sum+","+rest+","+b[bindex+1]);
}else{
q.add(aindex+","+(bindex+1)+","+sum+","+rest+","+0);
}
}
}
}
return max;

}
}

Largeもダメ元でやってみましたが、さすがに状態数が多すぎて、とてもじゃないですが
8分内に終わることはありませんでした。時間切れ。(Time Expired)
これを通したことで、相当満足してしまったのと、疲れきってしまったので、
B問題はほとんど読む気力がありませんでした。

それよりかは、順位をきにし始め、どこまで落ちるか、1000位以内に入ってくれ・・・と願うばかり。
結局残り0分のときには945位でした。
その後、状態を確認したところ、AのLargeが通っていました!
結構な人数が落ちていて、最終的に821位でした。

Google Code Jam Round 1突破!
これは、世界上位3000人に残ったことを意味します。嬉しすぎる。
次回R2で1000位以内を取ると、Tシャツをゲットとなります。
500位以上で予選通過です(かなり厳しい)

Google Code Jam 2012についておさらい
Qualification Round 15193/17802 日本人610/696
Round 1 3000/15193 日本人 208/610

倍率3倍を通過した気分です。この日は非常に満足したため、
もはや夜は遊んでいました。(バグは修正した上で。)

Google Code Jam 2012 Round1 突破!_f0019846_238122.jpg

中華急行 hard のフルコンとか。

  by ddrer-yossi | 2012-05-06 23:04 | 日常生活

<< GWなんてなかった。マルチスレ... TODやったりプログラミングしたり >>

SEM SKIN - DESIGN by SEM EXE