Google Code Jam 2011 Round 1B - simezi

Result

28:17, 29:35 / (未提出) / 2:17:21, (未提出)
40点 708位

ギリギリ予選通過……

A. RPI

問題

リーグ戦の勝敗結果の表が与えられる。
（ただし表には未試合の場所がある）

この時各チームについて 0.25*WP + 0.5*OWP + 0.25*OOWP
を計算せよ。それぞれの数値の意味は次の通り
WP: 自分のチームの対戦した数における、勝利数の割合。
OWP: 自分の対戦したチームの、「自分のチームとの試合を除いた試合でのWPの値」の平均
OOWP: 自分と対戦したチームのOWPの平均

チーム数≦100を満たす。

試行錯誤

問題読解に手間取る。
自分の対戦したチームの、「自分のチームとの試合を除いた試合でのWPの値」の平均ってややこしすぎるorz
読み取れた後は適当に実装。サンプル合ったのでsmall.
smallも合ったのでlargeも提出。

B.Revenge of the Hot Dogs

問題

数直線上のp[i]の位置にv[i]人のホットドッグ売りがいる。
彼らはどの二人も最低距離D[m]だけ離れていないといけないので、移動しなければならない。
移動速度は一律1m/sである。
全員が最低D[m]離れるまでにかかる時間の最小値を求めよ。

v[i]の合計は10^6以下

試行錯誤

同じ場所にいる人たちはばらける。あんまり遠いとはばらけた結果は重ならなさそう。。。
しばらく悩むけどわからず。
このままだと予選落ちなのでCのsmallだけ通そうとしてみる。

C. House of Kittens

問題

正N角形をした小屋がある。
小屋はM本の辺により区切られている。
辺は小屋の頂点と頂点を結んでいて、なおかつ交差しない。

N角形の頂点を以下の条件を満たすように塗る。
全ての部屋の頂点が、全ての色の頂点を最低一個以上ずつ含む。
この条件を満たすような塗り方のうち、色数が最大のものを一つ求めよ。

試行錯誤

smallはN≦8以下
8角形なら部屋の頂点は4つ以下。すなわちsmallは4色で塗れるので、
8^4通り試せばよい。

バグにハマりながらなんとか書いた。
small通った！！
1010位くらい。ギリギリいけるはず！