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