hotpepsiの練習帳

Facebook Hacker Cup 2016 Round 1

01:12

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

A. Coding Contest Creation

問題

• プログラミングコンテストの問題が何問かあり、難易度が数値の配列で与えられる
• 4問を1セットとする
• 各問の難易度は昇順で、難易度の差が10以下である必要がある
• 与えられた問題をすべて使い切るために、配列の任意の位置に問題を追加する
• 追加する問題数の最小値を求める

方針

• 貪欲に処理していく
• 直前と現在の数値が条件を満たさない場合、現在の値は直前の値以下か、差が11以上なので、直前の値+10を追加するのが最善
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2016/R1_A.cpp

B. Laundro, Matt

問題

• 総量Lの洗濯物、N台の洗濯機、M台の乾燥機がある
• i番目の洗濯機はW[i]分かかる
• 乾燥機はD分かかる
• 全ての洗濯物を乾燥させるのに必要な最小の時間を求める

方針

• 2分探索で洗濯に必要な時間Tを求める
• 各洗濯機について、時間TまでにT/W[i]回洗濯できる
• 各洗濯機の全ての洗い終わりの時間W[i],W[i]*2, ...を列挙してソートしておく
• 先頭の洗い終わりの洗濯物から一つずつ乾燥機に入れてシミュレーション
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2016/R1_B.cpp

C. Yachtzee

問題

• 実数[A,B]の間で予算を選ぶ
• できるだけヨットを作る
• ヨットの作成はNステップからなる
• i番目のステップの費用はCiである
• 次のステップが実行できない場合は、そこで打ち切る
• 残りの予算の期待値を求める

方針

• 予算[0,x]のときを考える
• 1台作るのにΣCi = Tかかるとすると、組み立てられる最大台数m = x÷T、端数はr=x % T
• 区間iについて、残存予算の最大値b = Ci×(m + min(r, Ci))
• この区間で予算が尽きる場合の期待値eは、三角形の面積になり、e = Ci×b×0.5
• rからその区間の大きさを減らして次の区間を計算していく
• 各区間の期待値の総和を、区間全体の和xで割ったものが予算[0,x]のときの期待値
• 予算[0,B]の期待値から予算[0,A]の期待値を引いたものが答え
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2016/R1_C.cpp

D. Boomerang Tournament

問題

• N人の競技を行う
• N人は一列に並び、先頭の二人が戦う
• 対戦表Wが与えられる
• Wi,jが1ならiが、そうでなければjが勝つ
• 勝者は列の最後に並び、列が一人になったら終了
• 最初の並びがランダムのとき、各人の最高順位と最低順位を求める

方針

• 一番下のトーナメントから、組み合わせをbitで表現してsetでがんばる
• Passed System Test
• (解き直し)
• BitDP
• 一番下のトーナメントから、組み合わせをbitで表現してDP
• dp[対戦順][組み合わせ][対戦者] = 最高順位
• 同じサイズでビットが重ならないものが対戦相手の候補となる
• 自分がiでk回勝ち残る可能性があるときについて、対戦相手jがk回勝ち残り、かつ、W[i][j]が1なら、自分がk+1回勝つ可能性がある
• 最高順位はN÷2からはじめて、勝てる可能性があるときは半分にしていく
• 最低順位は、全勝なら1、そうでなければN÷2
• setで列挙するのを提出したが、蟻本p.144のサイズkの部分集合を列挙するテクを使えば記憶領域を使わずに列挙できる
• https://github.com/firewood/topcoder/blob/master/fhc_2016/R1_D.cpp

結果

oooo 100pt 302nd

提出ミスがなくて良かった。

http://togetter.com/li/926195