スポンサーサイト

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

Google Code Jam Japan 2011 予選

GoogleCodeJamJapan2011の予選に参加しました。

A
Largeはカードの数が多いので素直にシャッフルをシミュレートするのは難しそう。 というわけで、x枚目がカット前は何枚目だったかを順に逆算することで解を求めました。
実装にものすごく時間がかかってしまいました。
・正解

B
問題文を読んでまず思ったのは、"ヘインさん長生き"。 Largeの最大2*10^12日は、およそ54.8億年です。 ヘインさんは宇宙人でしょうか?
まあ、それはどうでもいいので、私の思考過程を書いておきます。
1.欲ばり法:単純にその日に飲める最大価値のコーヒを飲むのは、先に消費期限がくるコーヒーを飲まないといけない場合があってダメ。
2.動的計画法:直感的に動的計画法だろうと思いました。 が、漸化式も複雑になりそうでしたし、日数が長すぎて無理そうでした。
3.二分探索:もしかして満足度を二分探索するのかとも思いましたが、ある満足度を達成する計画の有無の判定が効率的にできそうにありませんでした。
4.欲ばり法:時間を逆向きにしてその日に飲める最大満足度のコーヒーを飲む。これで解けるはず。
・正解

C
小さい数でいくつか手計算。 Nを超えない最大の2^k-1と表せる数と残りに分けるのが最善と気づきました。
・正解

感想
全問正解で、無事に予選を通ってほっとしました。
しかし、今回は時間がかかりました。アルゴリズムの正当性や時間量を丁寧に検討したせいもありますが、コーディングの手間取りもひどかったです。
決勝の目標はTシャツ獲得ですが、達成は難しそうな気がします。

コメントの投稿

非公開コメント

カテゴリ
最新記事
最新コメント
最新トラックバック
RSSリンクの表示
広告
Amazon.co.jpアソシエイト
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。