2015-06-07
Facebook Hacker Cup 2015 Qualification Round
A. Cooking the Books
問題
- 数字が与えられる
- 2つの桁を交換して、最小と最大を作る
- ただし先頭が0にならないこと
方針
B. New Year's Resolution
問題
- 3つの栄養素を目標量だけきっちりとりたい
- N種類の食べ物と、3つの栄養素の量が与えられる
- 食べるか食べないかを選ぶ
- 目標量にできるかどうかを求める
方針
- 半分全列挙した
- が、ふつうに全列挙で良かった
- https://github.com/firewood/topcoder/blob/master/fhc_2015/QR_B.cpp
C. Laser Maze
問題
- スタート地点とゴール、いくつかのレーザー砲台からなる迷路がある
- レーザー砲台は1ターンに時計回りに90度回転する
- ゴールまで到達できるかどうかを求める
方針
- 周期があるので、到達フラグをターンを4で割った余り毎に用意してDFS
- レーザーの軌跡も4ターンぶん生成しておく。4で割った余り毎に方向が異なる
- https://github.com/firewood/topcoder/blob/master/fhc_2015/QR_C.cpp
結果
ooo 100pt
レーザー砲台みたいなアレンジは好き。
半年遅れだけど埋めていく予定。
コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150607
2015-04-14
SRM 647
Div1 Easy (250) BuildingTowersEasy
問題
- N個の建物を建てる
- 位置x[i]にある建物の高さはt[i]以下であること
- 1番目の建物の高さは0であること
- 隣り合う建物の高さの差は1以下であること
- 建物の高さの最大値を求める
方針
- それぞれのt[i]について、位置yの最大値はt[i]+|x[i]-y|
- それを制約条件として全部の位置の最大値を求める
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_647/BuildingTowersEasy.cpp
- 結果
o-- 161.34pts 219th/511 1410 -> 1460 (+50)
ぎざぎざの山頂のイメージ。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150414
2015-02-15
SRM 646
Div1 Easy (250) TheConsecutiveIntegersDivOne
問題
- いくつかの数が与えられる
- 任意の数を+1または-1して、k個の連続した数を作る
- 最小の操作回数を求める
方針
- 単純に平均に集めればいいかなと思ったらどうも違う
- 平均付近をひたすら試す
- Failed System Test
- 中央の値に合わせるのが正解っぽい
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_646/TheConsecutiveIntegersDivOne.cpp
結果
x-- 0pts 250th/352 rating 1492 -> 1410 (-82)
平均に合わせるとかえって移動量が多くなってしまうようだ。
参加者少ない。やばい。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150215
2015-02-11
SRM 645
Div1 Easy (250) JanuszTheBusinessman
問題
- ホテルを経営している
- 宿泊客の到着日と出発日の配列が与えられる
- 宿泊客に特別なサービスをすると、良いレビューを残してくれる
- 特別なサービスを受けた宿泊客に居合わせた宿泊客も良いレビューを残してくれる
- 全員が良いレビューを残すために必要な特別サービスの最小値を求める
方針
- 蟻本の区間スケジューリング問題のようなやつ
- 出発日が一番早い人から貪欲に処理していけばよさそう
- 良いレビュアーではない人のうちの一番早い出発日に宿泊していて、出発日が一番遅い人に特別サービスを与える
- その範囲内の人を良いレビュアーにする
- Failed System Test
- すでに良いレビュアーだが、それ以降の区間で特別サービスを与えたほうがよいケースを見落としていた
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_645/JanuszTheBusinessman.cpp
結果
x-- +1 50pts 162nd/471 rating 1426 -> 1492 (+66)
easyはDPできるかと思ったが無理だった。
貪欲のコーナーケース難しい。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150211
2015-01-28
SRM 644
Div1 Easy (250) OkonomiyakiParty
問題
- M人でお好み焼きパーティーをする
- T種類のお好み焼きがあり、それぞれの大きさが与えられる
- M種類購入したとき、大きさの差がK以下になる組み合わせの総数を求める
方針
- ソートしておく
- 下限の値を固定し、+Kの位置を求めて、その範囲の組み合わせの数をnCkで求める
- https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_644/OkonomiyakiParty.cpp
結果
unrated
サンプル4が114514になっているの全く気がつかなかった。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20150128