hotpepsiの練習帳

Facebook Hacker Cup 2013 R1

23:39

A. Card Game (20)

問題

• 数値が書かれたN枚のカードがある
• K枚配り、最大の数が手の強さとなる
• 平均の手の強さを求めるため、手の強さの合計値を求める

方針

• 最大値が含まれている場合=nCk回は最大値になる
• 最大値を含まない場合について考える
• 2番目に大きい数になるのは、N-1枚の中からK枚選んだとき=n-1Ck
• そうでない場合は3番目、4番目...となるが、残りがK枚未満になったら終了
• すなわち、x>=Kについて、xCk回ずつ出現する
• 提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2013/A_CardGame.cpp

B. Security (35)

問題

• 文字列の一部を?で置き換える関数fと、文字列をシャッフルする関数gがある
• 文字列keyは、l文字毎に区切られている
• k1=f(key)、k2=f(g(key))が与えられる
• kとして可能性のある文字列のうち辞書順最小のものを求める

方針

• k2をシャッフルしたものがk1と対応すればよい
• これはいわゆる2部マッチングでは...
• l文字ごとに辺をつないでマッチング
• 文字を決めたい
• ?の文字を1文字ずつaから順番に代入して、マッチするなら固定する
• 提出
• Failed System Test
• (修正)
• https://github.com/firewood/topcoder/blob/master/fhc_2013/B_Security.cpp

C. Dead Pixels (45)

問題

• W×Hの画素の液晶ディスプレイがある
• 不良な画素を求める式が与えられる
• P×Qの範囲で不良な画素を含まない領域の総数を求める

方針

• 区間クエリな気がするが...
• 点の総数が少ないのでsetでいけそう
• set<int>を40000用意して、y座標に対応するsetに点を投入
• 縦幅Qの長さについて処理
• 横幅がP以上ある範囲を進めていく
• 提出
• Failed System Test
• (修正)
• https://github.com/firewood/topcoder/blob/master/fhc_2013/C_DeadPixels.cpp

結果

oxx 20pt 1237th/3617

Bはぼんやりしていて無用なソートを入れてしまった。ソートを消したら通った。

Cは終端の扱いがバグっていた。

だいたい方針が立ったのは良かった。