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

問題

問題概要

手持ちのモンスターから、レベルの一番低くくて、その中でも、一番先頭回数が少ないモンスターから使う。モンスターは戦わせるとレベルが上がる。敵は円に並んでいる。どこから始めてもよいが、1回ずつ順番に戦う。このときに、最も先頭回数が多くなるモンスターの先頭回数の最小値を求める問題。

解法

レベルが低くて、その中でも一番先頭回数が少ないモンスターがどれかを高速に求めるには、priority_queue使えばよい。新しい要素の追加が０(logN)ででき、topを取り出せば辞書順最小のものが取り出せる。また、どこから始めるかは全探索ですべて調べて、最小のものを求めればよい。

ミス

priority_queueでpairを使うと、first、secondとともに、辞書順になるから便利だね

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;    
typedef pair<int, int> P;

int main(void){
    //priority_queue + pair sample
    priority_queue<P, vector<P>, greater<P> > pq;
    pq.push(make_pair(1, 1));
    pq.push(make_pair(1, 2));
    pq.push(make_pair(1, 3));
    pq.push(make_pair(2, 3));
    pq.push(make_pair(2, 2));
    pq.push(make_pair(2, 1));
    pq.push(make_pair(3, 2));
    pq.push(make_pair(3, 3));
    pq.push(make_pair(3, 1));

    while(!pq.empty()){
        auto t = pq.top();
        pq.pop();
        printf("%d %d\n", t.first, t.second);
    }
    return 0;
}

上のようなプログラムを実行すると下のような結果になる。

1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

コード

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;    
typedef long long ll;
typedef pair<int, int> P;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;
int n;
int a[3010], b[3010];

int main(void){
    cin >> n;
    rep(i, n){
        cin >> a[i];
        a[i + n] = a[i];
    }
    rep(i, n){
        cin >> b[i];
        b[i + n] = b[i];
    }

    int ans = INF;
    rep(i, n){
        priority_queue<P, vector<P>, greater<P> > pq;
        for (int j = 0; j < n; ++j){
            pq.push(make_pair(a[j], 0));
        }


        for (int j = i; j < i + n; ++j){
            int nlv = pq.top().first;
            int t = pq.top().second;
            pq.pop();
            int lvup = b[j] / 2;
            pq.push(make_pair(nlv + lvup, t + 1));
        }
        int tmp = 0;
        while(!pq.empty()){
            int t = pq.top().second; pq.pop();
            tmp = max(tmp, t);
        }
        ans = min(ans, tmp);
    }
    printf("%d\n", ans);
    return 0;
}