2017-01-18
Facebook Hacker Cup 2017 Round 1
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://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20170118
2017-01-14
SRM 705
https://competitiveprogramming.info/topcoder/srm/round/16856/div/1
Div1 Easy (225) AlphabetOrderDiv1
問題
- aからzまで26種類の文字を使う言語がある
- 便宜的にaからzで表すが、各文字の序列は不明である
- ある単語の文字が、文字の序列順になっているものを、良い単語とする
- N個の単語が与えられる
- 全ての単語が良い単語になるような文字セットが存在するかどうかを求める
方針
- 各文字の大小関係を記録していき、矛盾が生じたらImpossibleとする
- 文字pが文字qより前にあり、文字qが文字rより前にあるとき、文字pは文字rより前になければならない、という判定をがんばる
- Challenge Succeeded
- 同じ文字が連続するときの判定が抜けていた
- (解き直し)
- 考察
- hama_duさんに聞く
- グラフで
- 文字p、文字qの順に出現したとき、文字pからqへ辺を張る
- ただし同じ文字が連続するときは無視する
- あとで全部たどるので、辺を張るのは前後の文字だけでよい
- 辺をたどって、ループしているときはImpossible
- ループするときには同じ文字に到達する
- 解法
- 一つ前の文字に(片方向の)辺を張る
- Warshall-Floydをかけて、自分自身に戻ってくる文字があるかどうかを判定
- https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_705/AlphabetOrderDiv1.cpp
- 別解として、トポロジカルソートして、ループが残るかどうかで判定してもよい
Div1 Medium (450) MovingTokens
問題
- N個の容器があり、それぞれに駒が入っている
- 駒の行先を示す表M[i][j]がある
- 各ターンにiをひとつ選ぶ
- 容器jに駒が入っていれば、それをM[i][j]に移動する
- 移動は同時に行う
- 駒が入っている容器の数を最小化するとき、10^100ターン後の容器の数を求める
方針
- 合流と移動がある
- 合流はunion findで同じと見なす
- 合流しているもののどちらかに移動するものがあれば、それも合流と見なす
- サンプル通ったので提出
- Challenge Succeeded
- (解き直し)
- Codeforcesのフォーラムを読む
- 2つの容器が合流するかどうかをDFSで見つけて、合流するときは、その手順を覚えておく
- 容器の初期状態を1として、任意の2つの容器のうち、合流するものがなくなるまでループする
- https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_705/MovingTokens.cpp
結果
xx- +1 50pt 141st/262 rating 1414 -> 1434 (+20)
clock()で1.7秒までがんばるコードが落とされていた。アリーナではclock()やtimes()は常に0を返すようだ。sleepもsleepせずにすぐに戻ってくる。
gettimeofday()またはRDTSC(インラインアセンブラ)は使えた。
mediumは、交換か減るかしかないので、貪欲的にやってよい模様。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20170114
2017-01-12
Facebook Hacker Cup 2017 Qualification Round
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://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20170112
2017-01-09
Codeforces 390
http://codeforces.com/contest/754
C. Vladik and chat
問題
- チャットのログがある
- 同一人物の連続する発言は1行にまとめられる (＝連続する行は発言者が異なる)
- 自分のIDは発言しない (＝発言中にハンドルネームがある場合、発言者はそれ以外である)
- 発言者が不明な場合がある
- 発言者を補え
方針
- 不定の行について考える
- strtokでトークンに分割して、ハンドルネームの場合、候補から外す (setで全IDを持っておいて、ハンドルネームがあったらeraseしていく)
- 残った候補をランダムで選んで、前後と違うハンドルネームならOK
- 10万回くらいやってみて、だめならImpossible
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/codeforces_3xx/cf_390/c.cpp
結果
ooo-- 1687 -> 1785
面倒でみんな諦めるだろうからと思ってやってみた。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20170109
2017-01-06
SRM 704
https://competitiveprogramming.info/topcoder/srm/round/16849/div/1
Div1 Easy (300) TreeDistanceConstruction
問題
- 木において、距離d(u,v)は、uからvへ到達するために経由する辺の数の最小値である
- 頂点uのd(u,v)の最大値を、頂点uの偏心とする
- 各頂点iについて、偏心がd[i]となる木を構築せよ
方針
- 考察
- 最長のものを考えると、A->B->C->D->Eのように一直線に連鎖しているものになる
- 一番長いものを構築済であること仮定する
- 中間地点にあるものが最短になる
- 最短のものは、最長の辺の長さが偶数であれば1、奇数なら2つだけ存在できる
- 最短以外の頂点は2つ以上存在する必要がある
- 最短の頂点に葉を増やすと、距離がひとつ増えるので、最短の数を増やすことはできない
- 最長の頂点に葉を増やすと、最長がのびることになるので、制約を満たさなくなる
- つまり、最短と最長以外の頂点は増やすことができる
- 構築手順
- 頂点を距離毎に分類する
- 左右方向に構築することを考える
- 左右それぞれの端(dが一番大きい)から、中心に向かってひとつずつのばしていき、3つ以上の頂点は葉として追加していく
- 左の頂点はひとつ右(dが1小さい)に、右の頂点はひとつ左(dが1小さい)につなぐ。つなぐものがなければ失敗
- 奇数の場合は最後の2つの頂点同士をつなぐ
- Passed System Test
- https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_704/TreeDistanceConstruction.cpp
結果
o-- 117.61pt 184th/373 rating 1370 -> 1414 (+44)
紙に書いてそのまま実装したら通ってよかった。
AGCで既出だったらしい。
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20170106