hotpepsiの練習帳

Facebook Hacker Cup 2016 Round 2

14:33

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

A. Boomerang Decoration (15pt)

問題

• 左右対称のブーメランがある
• 左半分と右半分はそれぞれN個の区間に区切られて塗られており、各区間の色が与えられる
• 右半分と対称になるように、左半分を塗り替える。右半分は塗り替えない
• 左半分について、毎秒、Jackが左端からx、Jillが右端からyだけ塗る。x+yはN以下
• 塗った部分はすべて上書きされる
• 右半分と同じにするための最小の秒数を求める

方針

• 右半分の色が異なる部分の個数の半分が最大値
• 色が異なる最も内側から塗ることになるが、最も外側から等しくなるまで塗っても手数は同じ
• 両端から貪欲に、右半分の色cが変化するまで塗る、というステップを進めていく
• ステップ数が答え
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2016/R2_A.cpp

C. Snakes and Ladders (25pt)

問題

• N本のはしごを持っていて、位置Xiと高さHiが与えられる
• 任意のはしごa,bについて、aとbが同じ高さで、その間にaとbより高いはしごがないとき、そこには蛇が住み着く
• 蛇にはエサをやる必要があり、そのコストは|Xa-Xb|^2である
• コストの合計値を求める

方針

• Xでソートしておく
• 高さごとにはしごを覚えておき、先頭からひとつずつ処理する
• 今処理しているよりも低いはしごのことは忘れる
• 今処理しているよりも前にある同じ高さのはしごのコストを加算
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2016/R2_C.cpp

結果

o-o- 40pt

Tシャツgetならず...

http://togetter.com/li/929428

SRM 679

02:12

https://competitiveprogramming.info/topcoder/srm/round/16649/div/1

Div1 Easy (250) FiringEmployees

問題

• 社長とN人の社員がいる
• それぞれのボス、給与、生産力が与えられる
• 生産力から給与をひいたものが利益となる
• 任意の社員を解雇できる
• ただし部下がいる社員を解雇すると部下も解雇する必要がある
• 利益の最大値を求める

方針

• 部下を含めたコストを計算しておく
• 先頭から足すかどうか貪欲に決める
• Passed System Test
• (解き直し)
• 後方には部下しかいない(上司がいない)ので、末尾から貪欲に足すことができる
• 自分iのコストをa[i]とする
• 自分の利益をdとして、a[i]に足す
• a[i]がプラスであれば、a[boss]にa[i]を足すことで、a[i]が再帰的に計算できる
• a[0]が答え
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_679/FiringEmployees.cpp

結果

o-- 151.54pt 345th/454 rating 1407 -> 1365 (-42)

珍しくeasyが簡単な回。

http://togetter.com/li/928104

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

SRM 678

12:45

https://competitiveprogramming.info/topcoder/srm/round/16648/div/1

Div1 Easy (250) ANewHope

問題

• はるかな銀河の彼方で...一週間はN日からなる
• ルークはN種類のシャツを1枚ずつ持っている
• 各週において、毎日違うシャツを着る
• シャツは洗濯する必要があり、同じシャツはD日後以降にしか着られない
• 最初の週のシャツを着る順番と、最後の週のシャツを着る順番が与えられる
• 条件を満たすための週の総数の最小値を求める

方針

• 最初と最後が同じなら答えは1
• 各シャツの最初の週の位置a[i]、最終週の位置b[i]を求める
• 各シャツの位置の差d[i]=b[i] + N - a[i]で、最短でd[i]日後に着ることになる
• d[i]の最小値mがD未満のときは、毎日r=N-Dずつ差を広げていく必要がある
• D以上にするのに必要な日数はx=ceil(D - m) / r日
• 最初と最終週が必要なのでx+2が答え
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_678/ANewHope.cpp

結果

o-- 168th/296 125.86pt rating 1380 -> 1407 (+27)

スターウオーズ回。

単純に差を縮めていけばいいようだが、合っているかあまり自信なし。

http://togetter.com/li/925031

Facebook Hacker Cup 2016 Qualification Round

22:53

A. Boomerang Constellations

問題

• 同じ点から延びる同じ長さの二つの線分が何ペアあるかを数える

方針

• 全ての点のペア(i,j)を列挙して、i,jそれぞれ、長さ別に保持しておく
• ある点aについて、長さbのものがc個あるとき、対象の線分は(c×(c-1))÷2ペアある
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2016/QR_A.cpp

B. High Security

問題

• 2行N列のマス目状の施設がある
• それぞれの場所は何もないか障害物である
• 何人かの守衛を配置する
• 守衛は障害物にさえぎられない見通しの上下左右を監視できる
• 施設内で守衛が監視できていない場所をなくすために必要な守衛の人数の最小値を求める

方針

• 左から右に1列ずつ見ていき、上下2マスが空いている場所があったら、そこは必ず埋める必要があるので、左下が空いていれば下に、そうでなければ上に配置する
• 右端まで見たら、もう一度左から右に1列ずつ見ていき、空いているマスを埋める
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2016/QR_B.cpp

C. The Price is Correct

問題

• N個の数がある
• 連続するK個の数を取り出し、P以下になる場合の数を求める

方針

• 典型的なしゃくとり法
• N個の数を一つずつ読み込んでいく
• K個の合計がPを越えたら、左端の数を合計から引いて、位置leftを進める
• 今の位置rightまでを取り出す個数は(right-left+1)通り
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2016/QR_C.cpp

D. Text Editor

問題

• 末尾に1文字追加、末尾の1文字を削除、現在の単語を印刷、の3つの操作が可能な装置がある
• 与えられたN個のうち、K個の単語を印刷し、最後に現在の単語を空にするとき、総操作回数の最小値を求める

方針

• ソートしておく
• DP[どの単語で終わったか][印刷した個数]=コスト
• 単語aで終わっていて単語bを入力するときは、aとbの共通部分の長さを求めて、その位置まで削除してからbの残りを入力する、というのが追加コストになる。
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2016/QR_D.cpp

結果

全問正解

Bの解き方は確証がない。Dが比較的シンプルに書けたのが良かった。

http://togetter.com/li/923210