hotpepsiの練習帳

Google Code Jam 2016 Round 1C

00:41

https://code.google.com/codejam/contest/4314486/dashboard

Contest Analysis

https://code.google.com/codejam/contest/4314486/dashboard#s=a

A. Senate Evacuation

問題

• 議会場が火事になった
• N個の政党の議員を二人ずつ退避させる
• いかなる瞬間においても、過半数を取る政党がないように保つ必要がある
• 退避させる手順を求める

方針

• priority queueで多い順に1人ずつ取り出す
• https://github.com/firewood/topcoder/blob/master/gcj_2016/R1C_A.cpp

B. Slides!

問題

• 1からB番までのB個のビルがある
• 1からB番への移動経路がちょうどM通りになるよう、B番以外の任意のビルに片方向の移動手段(辺)を追加する

方針

• small
• 閉路があると経路が無限になるので、DAGである必要がある
• 番号が大きなビルへしか行かないようにする
• 辺の有無をbitの有無で全て試す。DPで経路数を求める。
• https://github.com/firewood/topcoder/blob/master/gcj_2016/R1C_B.cpp

C. Fashion Police

問題

• ニューヨークでは同じ恰好をすると逮捕されるので、毎日違う格好をする必要がある
• J枚のジャケット、P枚のパンツ、S枚のシャツを持っている
• 毎日それぞれから一つずつ選ぶ
• J、P、Sの三つが全て同じ組み合わせだと即逮捕
• 二つが同じ組み合わせのときは、K回までは許容される
• 逮捕されない最大日数を求める

方針

• small
• ひたすらランダムで試す
• https://github.com/firewood/topcoder/blob/master/gcj_2016/R1C_C.cpp
• MODを求めるらしい

結果

oox-o- 32pt 1671st/5950

C問題が面白すぎ。

Bの出力を空白区切りにしてしまい、smallも通らなかった。diffを取るようなMakefileを書くのが良さそう。

largeの方針は立たなかったので、いずれにせよ今年は厳しかった。

multiple languagesの部は、最終的に13言語を使って5位タイだった。色々調べるのが楽しいので、来年も10言語くらいは使いたい。

https://www.go-hero.net/jam/16/multilang

http://togetter.com/li/972694