SRM 669 Div1 Easy - SubdividedSlimes
問題
TopCoder Statistics - Problem Statement
問題概要
スライムを分割するゲームをする。最初は大きさがのスライムが1体いる。ゲームはターン制で、1ターンの内に次のことを行う:
今いるスライムの中から1体を選んで、2体に分裂させる。選んだ1体のスライムの大きさがなら、2体の大きさは2つの自然数とを選ぶことに酔ってに分裂させることが出来る。その時に、プレイヤーは得点としてを得る。
とが与えられる時、の大きさのスライムを分裂させて合計の得点が以上になるのに必要なターン数の最小値を求めよ。
アイデア
分裂の方法によらず最終的には1のスライムが個生まれるのは想像に難くない。また、その分裂の方法によらずに最終的に得られる得点も決まっているので、それ以上の得点を取ることは不可能であることから、それを基に不可能判定をまず行っておく。以下、ターン数があるものとして考える。
最終的に得られる得点は同じなのだから、できるだけ最初の方に得られる点数が大きい方がいいだろう、と思って最終的な状態(1が個)から優先度付きキューを使って最小の2つをマージしていってそれを逆からみるのが最良なのではないか、と思って試してみたけどそれだとうまくいかない。
見る方向をちょっと変えて、ターン数を決め打ちにする。ターン与えられるので、その時に得られる最大スコアを考えてみると、スライムは体いる状態で終わっていることになる。さっきと同じように、これをマージしていく方向で考えると、この体のスライムはできるだけ均等な大きさのほうがよい。よって、小さいターン数からこの方法で得られる最大スコアを試していき、これがを初めて超えた位置が解となる。
Editorialみると、もっと数学的にわかりやすい説明書いてあった。Lagrangeの未定乗数法とかそういえば習ったなぐらいの感覚だった...
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(i=0;i<n;++i) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define mp make_pair #define pb push_back #define fi first #define sc second class SubdividedSlimes { public: int needCut(int S, int M){ int i,j; int lim=0; rep(i,S) lim+=i; //このサイズで得られる点数上限を超えている if(lim<M) return -1; int ans=0; for(i=1;i<=S;++i){//i回の分割に対してベストな方法 vector<long> ends(i); rep(j,i) ends[j]=S/i; rep(j,S%i) ++ends[j]; //printf("start %d\n",i); priority_queue<long,vector<long>,greater<long>> minpq; rep(j,i) minpq.push(ends[j]); long sc=0; while(minpq.size()>1){ long x=minpq.top(); minpq.pop(); long y=minpq.top(); minpq.pop(); //printf("merge %ld %ld makes %ld\n",x,y,x*y); sc+=x*y; minpq.push(x+y); } if(sc>=M){ ans=i-1; break; } } return ans; } };