2011-10-06

アルゴリズム問題に効くPython小ネタ

python

今週末の Google Code Jam Japan 2011 の決勝に向けて練習でもしておきたい所ですが、時間がなかなか取れないので、代わりにテクニックを紹介するブログエントリを書くことにしました。(代わりになってない、という意見は却下です)

namedtuple

namedtuple は python の標準ライブラリとして同梱されているクラスの一つです。

2011-10-01

Code Jam Japan 2011 報告

雑記 python

昨日書いた Google Code Jam Japan 2011 の予選が先程おわりました。
問題サイズに対する見積りがあまくて、最初の2問の Large を速攻で落とすという痛い失態をかましてしまい、3問目だけは慎重に解いてなんとか正解して本戦に残ることが出来ました。

Large は提出期限が切れた後も解き続け、予選終了後の演習モードで再提出してみたら、ちゃんと正解できましたので、本番もそのくらい慎重にやれ、ってことですかね。

とりあえず、(ちゃんと解いたんだぞ、という証明代わりに)全3問の解答と解説をこちらに貼っておきます。(あ、昨日貼ったテンプレートを使用しているので、実際に問題を解いているのは solve 関数の中だけですよ。)

あとで解いてみようと思っている人は、以下は読まないように注意!

(2011-10-02 追記：ちゃんとデキる人が書いてくれている解説を見つけたので、参考にする人はそちらをどうぞ → 不確定な Android Blog - Google Code Jam Japan 2011 予選終了 )

2011-09-30

Google Code Jam Japan 2011 明日開催

python

ご無沙汰してます。Over80です。
最後にこのブログにエントリを書いたのは3月頭ですから、半年ぶりの更新になります。
その間の事に関しては、書くと愚痴が多くなってしまうのでやめておきますが、震災の影響はいろいろと大きかったことと、私は直接被災はしておらず無事であること、あと、震災に遭われた方々へお見舞い申しあげます、とだけは言っておきます。

さて、今日の本題は、明日に開催をひかえた Google Code Jam Japan 2011 と、それに向けた Python の自作テンプレートの紹介です。

Google Code Jam Japan 2011 とは?

簡単に言うと、競技プログラミングコンテストで、明日午後1時にWebで公開される問題(複数)に対して、それを解くプログラムを作成して提出すればポイントゲット。沢山、早く解いた人が勝ち。みたいなコンテストです。
問題は比較的典型的なアルゴリズム問題(たとえば「迷路の最短経路を答える」のような)で、Webから問題データ(たとえば「迷路を表現したテキストデータ」)をダウンロードでき、それを作ったプログラムで解いて、答えのデータをアップロードすることで回答になります。

類似のコンテストと比べると以下のような個性的な特徴があります。

予選から決勝までオンラインで開催される。自分の慣れたPCで集中して解けば良い。
プログラミング言語や実行環境に(事実上)制限が無い。事務局や他の参加者が確認できるよう、フリーで実行環境が入手可能なもの、という制限があるだけで、VisualStudio も Express があるので OK となっている。あまつさえ、表計算ソフトのような物で解くことも認められている。("プログラム"の代わりに、そのソフトをどう使ったかを説明するテキストの提出が求められますが。)
今回の Japan 2011 は、日本語で開催される。大抵の大会(通常の google code jamも含む)は英語で開催され、問題文も英語なので、読むのに時間がかかる所が最初からハンデだったりする。

詳しくは Google Code Jam Japan 2011 のサイトを参照してください。(私の説明には誤謬があるかもしれません。)

上位入賞者には賞金や景品がありますので、気楽に参加してみてはいかがでしょうか？

日本語の例題は既に Code Jam Japan のサイトに上がっていますし、英語で良ければ過去問はこちらにあります。試しに解いてみるだけでも勉強になるかもしれません。