hotpepsiの練習帳

Google Code Jam 2014 Round 1C

02:24

Problem A. Part Elf (8pts/12pts)

問題

• 40代前のご先祖様は100%の人間またはエルフのどちらかである
• 混血度合いが分数で与えられる
• 100%のエルフが何世代目なのかを求める

方針

• どのように足しても分母は2の倍数になる
• 分子をビットで見るとき、血が濃いほうが上のビットに残る
• すなわち最上位ビットの位置が最短世代数に等しい
• が、最初に約分する必要がある
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1C_A.cpp

Problem B. Reordering Train Cars (10pts/25pts)

問題

• いくつかの文字列があり、一つの文字列に連結する
• 同じ文字は連続している必要がある
• 連結のしかたが何通りあるか求める

方針

• smallはnext_permutationで全て試す
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1C_B_s.cpp
• 文字が途切れている場合、それらは一体に連結する必要があるので、それらをunion findで連結して、グループの数Gを求める
• グループ単位の並べ方は自由なので、G!通りに並べることができる
• 同じ文字だけでできた文字列がN個あるときは、それらの連結のしかたはN!通り
• それらの積が答え
• あとはどうつなげても同じ文字が連続できないパターンをはじく
• 実際に書いたコードでは連結済みかどうかの判定を簡略化するため、先に同じ文字だけでできたものを別カウントした
• もっと簡単に書ける
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1C_B.cpp

結果

oooo-- 55pts 349th/4309

ひどいソースだけど通過した。別の方法でsmallが解けるとlargeの検証に使えるので助かった。