hotpepsiの練習帳

Google Code Jam 2016 Round 1B

21:03

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

A. Getting the Digits

問題

• 数値を桁毎に桁名の英単語(ONE,TWO,...)に置換し、結合し、順序をばらばらにしたものが与えられる
• 桁を復元し、昇順にしたものを求める

方針

• 一つしか出てこない英文字を含むものはそれで確定(ZEROのZなど)
• 確定したものは、それに関連する文字を取り除く(Zが2回出てきたらZ,E,R,Oを2個取り除く)
• SIXを取り除いたあとのSはSEVENの個数なので...というように一位に決まる
• Pythonで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/R1B_A.py

B. Close Match

問題

• Coders対Jammersの試合が行われた
• スコアボードにスコアが表示されている
• 何桁かのスコアボードは破損している
• スコアの差が最小になるときのスコアを求める
• 同じ差であれば、Codersのスコアが最小のもの
• 同じCodersのスコアであれば、Jammersのスコアが最小のもの

方針

• Smallは全部試すだけ
• Rubyで
• https://github.com/firewood/topcoder/blob/master/gcj_2016/R1B_B.rb

C. Technobabble

問題

• 前の単語と後ろの単語、二つの単語からなるトピックがある
• 偽トピックは、既存のいずれかのトピックを2つ選び、それらの前の単語と後ろの単語をセットにしたものである
• N個のトピックが与えられる
• 偽トピックの最大値を求める

方針

• Small
• 単語に通し番号をふっておく
• 使用するトピック(使う・使わない)の組み合わせをビットで全列挙
• 使う組み合わせで、単語が網羅されているかどうかをビットで調べる
• 全部の単語が網羅されているものの最小値が答え
• (終了後)
• 少なくとも前の単語の総数Aと後ろの単語の総数Bだけ必要
• 前の単語と後ろの単語とで2部マッチングすると、マッチした数Cは、前の単語と後ろの単語の両方を使っている
• ので、N－(A+B-C)が答え
• 全ての頂点を通る辺の最小数=最小辺カバーらしい
• https://github.com/firewood/topcoder/blob/master/gcj_2016/R1B_C.cpp

結果

ooo-o- 47pt 1405th/7886

数値の桁を操作する問題が苦手。

http://togetter.com/li/969380