2004年09月21日

Google Code Jam Round 1

Round 1終了!
250点と500点を解いて暫定79位300位.1000点問題はむずかった.ミスってなければ通過できるけど….500点問題を撃墜されてたのでだめっぽい.ルール読み落としかー.

予選RoundはJavaばっかりだったけど,Round 1はC++が多い.上位はほとんどC++だ.

問題の概要はいなばくんの日記へ.
1000点問題のデフラグはDPか….


(10/8追記)
Round 1は結局ぎりぎり(236/250)で通過してたんだけど,Round 2の日程が旅行と重なっていて参加できず.Round 2の一番難しい問題もDPだったみたい.

ルール概要:
日本時間で火曜の午前10時から.3問で75分.5分休憩後に,15分間の撃墜タイム開始.他人のソースをみて間違いを見つけたら,間違った結果を返すテストケースを作成してsubmit.撃墜に成功したら50点獲得,失敗したら50点減点.順位がぎりぎりだったら頑張る価値あり?

リビングデザインセンターOZONE

新宿にあるリビングデザインセンターOZONEというところでやってる展示を見に行ってきた.南口から20分くらい歩いたところにあるパークタワーというビルの中の数フロア分を占めている.基本的には住居や家具を扱ってる場所で,ショールームがあったり,何十万の椅子が売ってたり,つまみやドアノブのサンプルがずらっと並んでたりとそんな場所.雑貨屋もそうだけど,こういう風にいろんなものがごった煮で詰め込まれてる感じの場所が僕は好きみたい.それから,よかったのが建築やらインダストリアル・デザインやらの面白そうな本・雑誌が自由に閲覧できるスペース.時間がなかったのでほとんど読めず残念.新宿が行動範囲にある人は一度行ってみると面白いかも.

2004年09月17日

Google Code Jam 2004 Qualification Round

Google主催のプログラミングコンテストの予選に参加。1時間で問題を2問解いて、得点が高いほうから次のRound 1に進めるというルール。問題は難易度に差があって、それぞれ400点満点と1000点満点。submitまでにかかった時間に応じて減点されるという仕組み。

5パターン用意されている問題セットから一つにランダムで割り当てられて、その問題セットの中で上位100人が通過。

僕は1000点問題を18分くらい、400点問題を6分ぐらいで解いてsubmitしたものの、1000点問題が試合後のシステムによる自動テストにひっかかってrejectされてしまい、400点問題の得点だけに。

で、結果。なんとか通過できたっぽい。

20040917_googlecodejam_result.PNG


400点問題は間違えようが無いほど簡単なのでタイプ速度勝負になってしまった様子…。僕もあと数分遅かったら、落とされていたと思う。
1000点問題がシステムテストを通らなかった原因は、実装したアルゴリズムが富豪的すぎて入力サイズが大きな場合に実行時間の制限を超えてしまったせいかもしれない。

僕が書いた1000点問題のコード。提出速度重視で一番最初に思いついたナイーブなアルゴリズムをそのまま実装したのがいかんかった…。4重ループ…。

public class DropRocks
{
    public int maxWave(String[] rocks) {
        int max = 0;
        // "WEIGHT TIME X Y"
        int n = rocks.length;
        int[] w  = new int[n];
        int[] t  = new int[n];
        int[] x  = new int[n];
        int[] y  = new int[n];
        
        int mt = 0, mx = 0, my = 0;
        
        for(int i =0 ; i < n ; i ++) {
            String[] ss = rocks[i].split(" ");
            w[i] = Integer.parseInt(ss[0]);
            t[i] = Integer.parseInt(ss[1]);
            x[i] = Integer.parseInt(ss[2]);
            y[i] = Integer.parseInt(ss[3]);
            
            if(w[i] + t[i] > mt) mt = w[i] + t[i];
            if(x[i] > mx) mx = x[i];
            if(y[i] > my) my = y[i];
        }
  
        for(int time = 0 ; time  <= mt ; time++) {
            for(int i = 0 ; i  <= mx ; i++) {
                for(int j = 0 ; j  <= my ; j++) {
                    int level = 0;
 
                    for(int k = 0 ; k  < n ; k++) {
                        if(time  < t[k]) continue;
                        int dx = Math.abs(x[k] - i);
                        int dy = Math.abs(y[k] - j);
                        int d = Math.max(dx, dy);
                        if(d >= w[k]) continue;
                        if(time == t[k] + d) level += w[k] - d;
                    }
                
                    if(level > max) max = level;
                }
            }
        }
        
        return max;
    }
}

2004年09月15日

BlogなんとかConference

御茶ノ水であったBlog Hacksの発売記念イベントを覗いてきた。本買ってないけど。思いついたアイデアをさっと実装して動かしちゃうってのがすごい。コーディングしてる本人が一番楽しいんだろうなぁ。

2004年09月13日

リハビリ

インターン終わって大分たったのにいつまでも呆けてちゃいかん!ということで、少々プログラミング。気の赴くままに作ったら、MemoriumとInformationFishingとVisualQueryをくっつけたようなものができた。

candybox

研究室ミーティングでみせたら反応がわれた…。僕としても、ものすごく役に立つものだとは思っていないので、見た目がきれいなだけだと言われたら反論のしようがない。役に立たないものを五十嵐研でやるべきじゃないなら、どこか別のところにこっそりだすしかないなぁ。