hotpepsiの練習帳

Google Code Jam 2011 Round 1B

23:20

A. RPI (8pt + 12pt)

問題

• NCAA男子バスケットボールトーナメントが毎年開かれている。
• 350の学校のうちRPIが高い学校が推薦される。
• RPIは0.25 * WP + 0.50 * OWP + 0.25 * OOWPで計算される。
• WPは勝率である。
• OWPは全対戦チームの、自チームとの勝負を除いた勝率の平均である。
• OOWPは全対戦チームのOWPの平均である。
• 全チームの対戦成績から、各チームのRPIを求める。

方針

• 読解できれば書くだけ
• 去年は一時間くらいかかって提出
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1B_A.cpp

B. Revenge of the Hot Dogs (15pt + 20pt)

問題

• ホットドッグ屋が水平方向のみに伸びる道路上にいる。
• それぞれのホットドッグ屋は、少なくとも距離Dだけ離れる必要がある。
• ホットドッグ屋の移動速度は毎時1である。
• 地点の水平座標と、その地点のホットドッグ屋の個数が与えられる。
• 全てのホットドッグ屋の移動が完了する時間を求める。

方針

• 去年は解けなかった
• 今年も解けない
• ぐぐる
• にぶんたんさく
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1B_B.cpp

C. House of Kittens (20pt + 25pt)

問題

• 柱がN本ある猫屋敷がある。
• 柱と柱の間にM個の間仕切りを設置して部屋を作った。
• それぞれの柱は異なる種類のマタタビが使ってある。
• ある部屋にあるマタタビの種類が別の部屋にないと猫は機嫌を損ねる。
• マタタビの種類を最大化した上で、それぞれの柱に使用する種類を求める。

方針

• さっぱりわからない
• 彩色問題?
• 色数=最小の頂点数
• 壁から部屋を生成する
• 最初の部屋を塗る
• 2頂点以上塗られている部屋を次々塗る
• https://github.com/firewood/topcoder/blob/master/gcj_2011/1B_C.cpp

感想

一年かかって1Bまで復習。本番はAのみで20pt、2589位。

Aはこの評価式微妙だよねみたいな説明が面白い。

Bは冗長に書いたら納得できた。

Cはだいぶ無駄があるけどlargeまで通った。ちょっと嬉しい。