Google Code Jam 2010 Round1 感想

無事通りました。とりあえず今年の目標は達成。

Round 1A

Aだけ通って1710位。

他の方の解答(1Aまとめて)

A: Rotate

時計回りに90度回転→右に落とせばいいんじゃね?というのはすぐにわかった。
はじめ全座標について判定しようとか考えたけど、すぐに面倒なことになりそうだと思ったのでやめた。
縦と横はそのまま文字列に直しちゃって正規表現で一発判定。
で、斜めだけ座標ごとに判定してた。
よく考えたら斜めも文字列に直せばいいじゃん、と終わってから思った。
50分ぐらい。最初に解いていれば通ってたかもしれない。

他の方の解答

B: Make it Smooth

なぜかこれから着手。
DPで解こうと思ったけど経験値低すぎて部分最適問題見つけられなかった。
そこで考えたのが、各ポイントの値をノードに見立てて最短経路問題に落とし込んで解こうという方法。
例えばa,b,cと3つの値が並んでいたときに、a→bの重みは「aとbの間で挿入・値の変更だけで条件を満たすためのコスト」となる。
一方a→cの重みは、「a〜c間の全てのノードを削除した上で、a,cで条件を満たすためのコスト」となる。
これで最短経路の総コストを求めれば答えが出るはず、と思ったら Small すら通らず。
後で他の人の解答と比較してみると、この方法では以下のケースについて解くことができないことが判明。
例えば 100,1,100 という並びのときに、差分を50にするには1→50にすればいい(値の変更コスト49)。ところが上記の方法だと100,1のコストと1,100のコスト両方を計算してしまう。つまりコスト98とみなしてしまうということ。
もしかしたら何か方法があるのかもしれないが、思いつかなかった。
1時間かけてもSmallすら通らず。これが敗因。

他の方の解答

C: Number Game

問題読んだ段階で残り20分しかなかったので、コンテスト中はほとんど着手していない。
多分やっててもわからなかった。
必勝条件は答え見ないとわからなかった。他の人たちの考え方を見て色々と勉強になった。

他の方の解答

Round 1B

A,B通して874位。後20分提出が遅れたらアウトだった。危なかった。
1A は明らかに勝負にこだわり過ぎて固くなって失敗してたので、妄想することなかれとブツブツつぶやきつつコンテスト開始。

他の方の解答(1Bまとめて)

A: File Fix-it

既にあるディレクトリ一覧を配列に押し込み、必要なディレクトリ一覧も別の配列に押し込み、差分とってカウントして終了。
18分。

他の方の解答

B: Picking Up Chicks

それぞれのにわとりが、単体だけいるときに時間Tの時点でどの位置まで到達できるか計算。
そのままでゴールできるにわとりは、カウントだけして後は無視。
あとは遅いにわとりに邪魔されてるにわとりを、必要な分だけ前から順に先頭にずらしていけばいい。
ここまでで1時間5分くらい。

他の方の解答

C: Your Rank is Pure

きっとこれもDPなんだろうなー。今年なんかDP多いなー。あーDPとか全然わかんないなー。
なんて余裕でいたのも、上2つをそこそこいいタイムで解いて油断してしまったから。
慢心以外の何者でもない。
あーでもないこーでもないとやっているうちに1時間経過。
みるみるうちに順位下がってきて焦る。
とりあえず力技でSmallだけでも通すかー。2**23 とはいえ、ギリギリいけるんじゃない?
なんて思って突撃してみたらやっぱり全然話にならない。n=21のケースだけで1分かかった。
最後はもう祈るしかなかった。

他の方の解答

Round 1C

多分出てたら通ってなかった。

他の方の解答(1Cまとめて)

A: Rope Internet

さすがにこのくらいは見ただけで解き方がわかるようになった。
入力データそのままの配列×2と、それらをソートした配列×2の計4つ。
後者における、前者の対応データのインデックスの差分の和がそのまま答えになる。
……日本語で書いててあまりのややこしさにびっくりした。
ソースコード見ればわかる。

他の方の解答

B: Load Testing

大半の参加者の例に漏れず、私も英語がよくわからなかった口。
「ヒントよこせってやつがたくさんいたが、問題を読み解くのも問題のうちじゃ」
と、何とも冷たい解説がついてた。
まだちゃんと解説読んでない。

C:Making Chess Boards

これもDPじゃね?ていうか今回DP多すぎじゃね?
とか思っただけでまだ解いてもいない。

他の方の解答

まとめ

去年は全くわけがわからなかったのですが、今年は簡単な問題なら理解できるようになったし、答えを読んでもかなりのスピードで理解できるようになりました。
とりあえず、間違いなく自分が成長してるとわかったのはうれしいです。
Round 2 はさすがに歯が立たないだろうけどもうちょっと頑張ろうと思います。

おまけ

今回も GCJ の ML から。

今回初めてプログラミングコンテストに参加しました。QRは通ったんですけどRound 1は通りそうにないです。ちゃんと勉強し練習しないと通らないんだろうと思ってます。私はコンピュータサイエンスの学士を取得していて、今修士も取ろうとしているのですが、そうした背景を踏まえた上で何かいい本やチュートリアル、あるいは勉強法はないでしょうか?

よくある質問なのですが、色々面白い発言がありました。

第一に、あなたの研究に関係のある領域での修士取得を目指すべきであって、このコンテストのためだけの勉強をしちゃいけない。このコンテストの練習をすることは脳を刺激し、あなたの作業効率を上げることになるだろう。しかし、自分が働きたい職業領域に関係のある修士号を選択することが、あなたのキャリアをより豊かなものにするはずだ。

「このコンテストの練習をすることは脳を刺激し、あなたの作業効率を上げることになるだろう」
そんな科学的根拠ねえよ、嘘いうな
http://www.bbc.co.uk/labuk/results/braintestbritain/1_results_summary.html
http://web.me.com/adrian.owen/site/Home.html

まあ脳云々はさておき、言ってることは正しいかなと思います。
仕事してるとどうしても「これ手作業でやるより自動化した方が早くね?」と思うことがあって、実際その方が早いのですが、以前は「これ1時間でできますよ」と言っていたのを「これ5分でできますよ」と言えるようになったのは大きな進歩なのかなと思います。
1時間かかると、手作業でやった方が早いという仕事もそこそこあるのですが、5分や10分で済んでしまうのであれば、手作業の方が早いなんてことはまずありません。
あるいは、口にコードを突っ込んで黙らせるなんてことも、より簡単にできるようになり、そうするチャンスも増えます。
別に実業務に活かすつもりは何もなかったのですが、結果としてそうなってしまいましたね。

上位陣を見てると、一生かかっても追いつけそうにないし、とてもこのコンテスト「だけ」に命かけるのはできそうにないです。でも、ここで得た知識・経験・技術は確かに他の分野とつながっている。
もちろんこのコンテスト自体がとっても楽しいのですが、実際に仕事の現場のあちこちでこの「武器」を振るえるというのもとても楽しいことです。

このコンテストはとっても楽しいのに、ほとんどのプロのプログラマはこういう問題を解こうとしないんだ。
悲しい現実?だけど、90%のソフトウェアエンジニアリングはただ従業員の合意をとりつけるだけの仕事なんだ。


どこの世界も似たようなものですね。

一応まともな回答もあります。ご参考までに。

topcoder、 imagin cup、code jamの過去問、あと codechef。そこ見りゃ練習用の問題がたくさんあるよ。

一番重要なのは、これらのサイトのフォーラムを覗くことだ。それと、速くて正確なコードを読むこと。これが私の勉強方法だよ。

練習したいなら以下のサイトに行けばいい。

www.topcoder.com/tc
codeforces.net
www.spoj.pl
uva.onlinejudge.org

Topcoder アルゴリズムチュートリアルは勉強には非常にいい
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index

過去問はここにある
http://www.topcoder.com/tc?module=ProblemArchive

And practice them on Arena, where you can read others solutions, challenge and run system tests.
Go through TopCoder forums, there are brilliant ideas on solutions.
Arena では他の人の解答を見ることができるし、練習することもできる。
Topcoder のフォーラムにいけば、ブリリアントなアイデアが書いてある。

codeforces.com。これしかないよ