hotpepsiの練習帳

SRM 669

00:57

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

Div1 Easy (250) SubdividedSlimes

問題

• 大きさSのスライムがある
• 1ターンで任意のスライムを選び、大きさxとyの二つに分割する
• その際スコアx×yが得られる
• 合計スコアがKとなる最小のターン数を求める

方針

• 死
• (終了後)
• ターン数Tとするとき、T等分するのが最適らしい
• Tを小さい方から全部試して、条件を満たしたものが答え
• 分割後は、どの順番に合体させてもスコアは同じらしい(Div2 Medium)
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_669/SubdividedSlimes.cpp

結果

x-- 0pt 199th/463 rating 1330 -> 1322 (-8)

スコアは異なるのペアの積の和になり、積は差が小さい方が大きくなるので等分するのがベストということみたい。

http://togetter.com/li/879808