Div1 Hardを大幅に簡単にした問題だが、こちらを解いておくとDiv1 Hardの考え方がすっきりする。
http://community.topcoder.com/stat?c=problem_statement&pm=13659
問題
初期状態でN個のカートからなる列が1つだけある。
1ターン毎に、カート列群に対しそれぞれ以下の何れかの行動をどちらか1つ行える。
- 列のカートを1つ減らす
- 列を2つに分割する(分割後の2列のカート数配分は任意)
ただし、列の分割は最大K回までしか行えない。
全てのカートを取り除くのにかかる最小ターン数を答えよ。
解法
列を1回分割すると、以後列のカートを減らすペースを1増加できる。
よって、どうせ分割するなら早めに行った方がよい。
そのため最大X列まで分割するケースを考える。
とする。たとえばX=6ならY=3。
この場合、最初の(Y-1)ターンはひたすら列の分割を行う。
Yターン目は(X-2^(Y-1))列は分割し、残り(2^Y-X)列は1個減らすと、X列になる。
あとはYターン目に残った(N - (2^Y-X))個のカートを1ターンX個減らすので、最初のYターンと合わせて必要ターン数はとなる。
列の分割が最大K回なので、X=1~(K+1)に対し上記値の最小値を求めればよい。
class CartInSupermarketEasy { public: int calc(int N, int K) { int mi=N; for(int X=1;X<=K+1;X++) { int y=0; while(1<<y<=X) y++; if(X>N) continue; mi=min(mi,(N-(1<<y)+X-1)/X+(y+1)); } return mi; } }
まとめ
ここまで考察するとDiv1 Hardが楽。