hotpepsiの練習帳

Facebook Hacker Cup 2017 Round 1

23:23

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

A. Pie Progress (10pt)

問題

• パイを売る店がある
• 一日にM個のパイが売りに出される
• それぞれの価格が与えられる
• 毎日パイを1つずつ食べられるように買う
• まとめ買いしてもよいが、一日にX個買うと、X^2の金額が税として足される
• コストの最小値を求める

方針

• DP
• D日経過したとき、すでに購入した個数はD個からD×M個までのどれかになる
• D+1個から(D+1)×M個までのそれぞれの最小コストを計算していく
• ただしN個より多く買う必要はない
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2017/R1_A.cpp

C. Manic Moving (25pt)

• Wilsonは引っ越し屋をしている
• N個の街があり、M本の道路で結ばれている
• 街Aiと町Biに移動するのにガソリンをGi消費する
• Kの家族が街Siから町Diへ引っ越しをする
• トラックには2家族ぶんまで荷物が積める
• 順番が先の家族の荷物を先に積み込む必要がある
• 順番が先の家族の荷物を先に届ける必要がある
• ガソリンの消費量の最小値を求める

方針

• 考察
  • まず最短経路を求めておく(全頂点についてダイクストラ)
  • DP
  • 状態として、(A)何も積み込んでいない状態、(B)家族kの荷物を積み込んで、家族kの出発地にいる状態、(C)家族kと家族k+1の荷物を積み込んだ状態がある
  • (A)から(B)へ、(B)からは(A)か(C)へ遷移できる
  • (C)のときは、先に積み込んだ家族の目的地へ行く必要があり、分岐はないので、(B')家族kの荷物を積み込んで、家族kの目的地にいる状態、まで遷移させて考えてよい
• 解法
  • あるターンの処理は次の通り
  • 前のターンの(B)か(B')の状態から、(C)を経て(B')に遷移できる
  • (A)にいれば(B)に遷移できる
  • (B)か(B')から次のターンの(A)に遷移できる
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2017/R1_C.cpp

D. Beach Umbrellas (40pt)

問題

• ビーチにN本のパラソルを広げる
• パラソルを固定する穴が等間隔にM個空いている
• 各パラソルの半径はRiである
• パラソルがぶつからないように配置するとき、配置の仕方が何通りあるか求める

方針

• 考察
  • 端のことを考えると、端に置くものによって、端以外の余白が変わる
  • 端を固定して、余白が何通りかを求めて、全ての端のパターンを列挙すればできそう
  • 端以外に使える長さCは、(M－1－端に置くものの半径)
  • Riの合計の2倍が、C以下なら配置できる
  • 余白を配置する場合の数は、重複組合せ
  • Cに配置するのは(N-2)!通り
• 提出
• Time Expired
• nCrを毎回計算するのが遅すぎた
• rは小さいのでメモ化すればよい
• https://github.com/firewood/topcoder/blob/master/fhc_2017/R1_D.cpp

結果

o-o- 35pt

なんとか通過した。

pie chartの次はパイ屋さんときた。予選の問題のアップグレードになっていて、今年は問題文が面白い。

CはN=5000のワーシャルフロイドは間に合わなさそうだと思ったらN<=100だった...

editorial:

https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2017-round-1-solutions/1599716033377625

https://togetter.com/li/1070628