スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Google Code Jam Japan予選

Google Code Jam Japanの予選に参加した。

のんびり昼食をとっていたら13時を過ぎていた。とりあえずAから取りかかることにする。問題を読んで把握。制約を見るとLargeの場合が1≤M≤109とか書いてあったので、まともに配列を作っていては時間が足りないと判断(実際どうなんだろうか)。求めたいのは1枚のカードだけだったので、そのカードだけに注目して考えることにした。取りかかってから15分程度でクリア。

次にBを見る。面倒そう。貪欲法でいけるかと思ったが、満足度がコーヒーごとに違うのに気づいて考え直す。Smallの規模なら全探索で大丈夫そうなので、とりあえず全探索する。30分程でSmallをクリア。

BのLargeは後回しにして、Cに取り組む。Smallは全探索で行けそう。10分足らずでSmallをクリア。

CのLargeについて考える。1018は64ビット整数で表現できるようだ。一定のビットパターンをビットがなるべく多く立つような組み合わせで分割するには、と考えて解いた。考え過ぎだった面もあるようだが…30分ちょいでクリア。

BのLargeは、満足度も考えて貪欲法をしたら通った。最終日から逆に考えて、その日飲めるコーヒーのうちもっとも満足度の高いものを飲む。

結果は、54点で上位50位以内に入った。ただ、予選だからといって1問しか解かなかった人やのんびり時間をかけて解いた人がいるかもしれないので、決勝ではどうなるか分からない。

スポンサーサイト

テーマ : プログラミング | ジャンル : コンピュータ

プロフィール

minoki

Author:minoki
好きなプログラミング言語:
Haskell,Lua
GitHubアカウント
Twitter

最新記事
月別アーカイブ
カテゴリ
検索フォーム
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。