Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

[C23]

強かった。。。

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/581-7437dd78
この記事にトラックバックする(FC2ブログユーザー)

Google Code Jam 2009 - Round 1A (この記事を編集する[管理者用])

2009年09月12日10時から2時間30分,3問.
上位1000人が2回戦に進出,それ以外はRound 1Bへ.
[ Link ]

2時間半もあるんだから,てっきり4~5問だと思ってたのに3問だった.
去年と比べて問題間の難易度差がなくなってて,難しい問題はなかった.
でも,少しずつ捻りを入れつつ,基本的で,バランスのとれた問題セットだったと思います.
人によって感じ方は違うと思うけど,個人的にはCが一番簡単で,Bが一番面倒だった.
無事通過予定.

A. Multi-base happiness

数字が与えられたとき,各桁の二乗和で置き換える,といった操作を続けていったとき,最終的に1になる数がハッピー.
2~10の中から,いくつか基数が与えられるので,その基数全てでハッピーな数のうち最小のものを求める問題.

全部調べるだけ.
勿論,ハッピーかどうか1度判明した数はその結果を覚えておく.

B. Crossing the Road

碁盤の目の道路で,各信号が周期的に変わっているとき,左下から右上に辿り着く最小時間を求める問題.
縦横の道路の数は20以下.信号の周期は大きい.

ダイクストラするだけ.ただし,現在の時刻によって,枝の重みが変わることに注意.
なんだけど,サイズが小さすぎて,ダイクストラ書くのが面倒だったので,ベルマンフォードした.

C. Collecting Cards

あるトレーディングカードは全部でC種類あって,1個ブースターパックを買うとランダムでN枚入っている.
ただし,N枚の中に重複はない.
C種類全部集めるために,買わなければいけないブースターパックの数の期待値を求める問題.
CもNも40以下.

単純なDP + 数学(組み合わせの数).
ただし,ループする場合,適当に解決してやらなければいけない.
 x(n) = a + b x(n) → x(n) = a / (1-b)

コメント

[C23]

強かった。。。

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/581-7437dd78
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。