hotpepsiの練習帳

Facebook Hacker Cup 2015 Round 1

00:59

A. Homework

問題

• 数AからBまでの間で、素因数の個数の最大値を求める

方針

• 素因数の個数を配列に持つ
• 全探索
• 配列p[n]の値が0だったら素数なので、p[n*2],p[n*3]...の素因数を+1
• https://github.com/firewood/topcoder/blob/master/fhc_2015/R1_A.cpp

B. Autocomplete

問題

• 残りの文字列が一意なら文字を補完してくれるシステムがある
• 全ての単語を入力するのに必要な入力文字数を求める

方針

• 1文字ずつノードにする
• https://github.com/firewood/topcoder/blob/master/fhc_2015/R1_B.cpp
• Trie木でやればよかったらしい

C. Winning at Sports

問題

• 1点ずつ取っていくスポーツがある
• 先に1点取り、常に相手より得点して勝つ(stress-free)
• 相手が最終得点になるまで相手の得点を上回らないで勝つ(stressful)
• のそれぞれの勝ち方の総数を求める

方針

• DPがんばる
• スコア20までを全探索して検算した
• https://github.com/firewood/topcoder/blob/master/fhc_2015/R1_C.cpp

D. Corporate Gifting

問題

• 会社にN人の従業員がいる
• それぞれの直属の上司の番号が与えられる
• 直属の上司にある金額の贈り物をする
• 部下を持つ従業員は、部下からもらったのと同じ額の贈り物はできない
• CEOも贈り物をする
• 贈り物に使う全社の合計金額の最小値を求める

方針

• 彩色問題みたいなやつ?
• あるノードが色Cで塗られていたときのコストの合計をDFSで求める
• https://github.com/firewood/topcoder/blob/master/fhc_2015/R1_D.cpp

結果

ooox 60pts

変な持ち方をしてしまいDを落とした。解きなおしたが、intオーバーフローしたりして、時間内には無理かもだった。

去年は1問だけ正解なのでだいぶ解けるようになった感はある。