hotpepsiの練習帳

Google Code Jam 2014 Round 1B

22:15

A. The Repeater

問題

• いくつかの文字列が与えられる
• 同じ文字を隣に追加するか、連続する文字のうち1文字削れる
• 全部同じ文字列にするのに必要な操作回数を求める

方針

• それぞれの文字列について、連続する文字は1文字にする
• 同じにならなければ不可能
• 各文字について、長さ1～100を全部試して最小操作回数を求める
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1B_A.cpp

B. New Lottery Game

問題

• くじ用の乱数生成器が二つある
• 二つの出力の論理積が当選番号になる
• K未満を出力するのは何通りか求める

方針

• smallのみ、全探索
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1B_B_s.cpp

C. The Bored Traveling Salesman

問題

• N個の都市を飛行機で最低1回訪問する
• フライトチケットは行きと帰りがあり、行きを使ってからでないと帰りが使えない
• 行きのチケットはN枚で、出発地は任意だが行き先は全て異なる
• 都市には郵便番号が設定されている
• 訪問順に郵便番号を結合していく
• 結合した数値の最小値を求める

方針

• next_permutationで訪問都市の順番を生成して全て試す
• 可能かどうかを探索
• https://github.com/firewood/topcoder/blob/master/gcj_2014/R1B_C_s.cpp

結果

ooo--- 31pts 1316th/7381

Bは桁DPらしい。要復習。