yukicoder : No.9 モンスターのレベル上げ

うーん、タグで解法バレバレだな…。
http://yukicoder.me/problems/28

問題

自分と相手はN匹のモンスターを持っており、それぞれのレベルA[i]、B[i]が与えられる。
敵のモンスターは円状に並んでおり、最初の１匹B[i]を任意に選択すると、以後B[i+1]、B[i+2]…と順に戦っていく。

自分がモンスターを出す順番は決まっており、

• 手持ちで一番レベルが低いモンスター
• 最低レベルのモンスターが複数いるなら、戦闘回数が最小のものを選択

両者のモンスターのレベルにかかわらず自分のモンスターは必ず勝利し、その際敵モンスターのレベルの半分の自分のレベルに加算する。

N匹の戦闘を終えた後、自分の最多戦闘回数のモンスターの戦闘回数が最小となるよう、最初の１匹を選択し、最多戦闘回数を答えよ。

解法

愚直にB[0]～B[N-1]それぞれを先頭とするパターンを総当たりすればよい。

自分のモンスターは(レベル*100000+戦闘回数)でpriority_queueでソートすれば、常に次に戦うモンスターをpopできる。
よって全体で計算量はO(N^2*logN)かな。

int N;
int A[2000],B[2000],L[2000];
int num[2000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	int mi=10000;
	FOR(i,N) {
		ZERO(num);
		priority_queue<pair<int,int> > P;
		FOR(x,N) L[x]=A[x];
		FOR(x,N) P.push(make_pair(-L[x]*100000,x));
		
		FOR(x,N) {
			pair<int,int> p=P.top();
			P.pop();
			num[p.second]++;
			L[p.second] += B[(i+x)%N]/2;
			P.push(make_pair(-L[p.second]*100000-num[p.second],p.second));
		}
		mi=min(mi,*max_element(num,num+N));
		
	}
	cout<<mi<<endl;
}

まとめ

☆３つはDiv2 Medium位かな？Div1 Easyより少し簡単な気がする。