hotpepsiの練習帳

Facebook Hacker Cup 2017 Qualification Round

23:22

https://www.facebook.com/hackercup/round/1760504744276109/

A. Progress Pie (25pt)

問題

• 中心座標(50,50)、半径50、90度からはじまり時計回り、100%で一周するP%の円グラフが与えられる
• 円グラフがない場所は白、ある場所は黒
• 座標(x,y)が白か黒かを答える

方針

• xとyを逆にすると、0度から反時計回りになるので、普通のラジアンが使える
• atan2(x,y)で角度が(ラジアンで)わかる
• 中心から50以内で角度がP以内なら黒
• P=0がコーナーケース
• https://github.com/firewood/topcoder/blob/master/fhc_2017/QR_A.cpp

B. Lazy Loading (30pt)

問題

• Wilsonは荷運びをしている
• 荷運びに使う袋は不透明なので、一番上の品物しかわからない
• ボスは、一番上の品物の重さと、品物の個数だけがわかる
• ボスは、一番上の荷が一番軽いという想定で、一番上の品物の重さ×品物の個数が50を超えればOKを出す
• 時給なので、運ぶ回数を最大化したい
• N個の品物の重さが与えられる
• 運ぶ回数の最大値を求める

方針

• 一番上は重い順に使い、下は一番軽いのから貪欲に取る
• https://github.com/firewood/topcoder/blob/master/fhc_2017/QR_B.cpp

C. Fighting the Zombie (45pt)

問題

• ゾンビに与えるダメージがxdy+zの形式で与えられる
• y面ダイスをx回振ってzを足す

方針

• 1～20面ダイスの20回までのテーブルを作っておく
• x×y+zがHを超える部分の確率を足す
• https://github.com/firewood/topcoder/blob/master/fhc_2017/QR_C.cpp

結果

ooo 100pt

Aのコーナーケースを考慮していなかったが、EPSを足してずらして判定していたので通った。

Cの問題文は好き。

editorial:

https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2017-qualification-round-solutions/1593063774042851

https://togetter.com/li/1067912