[未]AOJ 0553: Dungeon

JOIボリューム, この問題が終わればチェックメイトなのですが, 中々オーダーが改善できません...

30点解法です. 満点解法ではないので詳しい解法は述べませんが, 泉の最小使用回数をminAとすると, O(N + minA* (NlogN))くらいです.
minAが10^4くらいになると死にます. (最大ケースでは, minA >= 10^9なのでこの解法自体ダメなのかもしれない.)

もう少し頑張ると O(N + minA * (log^2N))にできる可能性が存在しますが, 現時点では厳しそうです (そもそも満点は得れ無さそうなオーダーでかなしい).

想定解はO(NlogN)くらいなのでしょうか...

#include <stdio.h>
#include <string.h>

#define min(a, b) ((a) > (b) ? (b) : (a))
#define MAX_N (100000)

typedef struct {
    int val;
    int pos;
} SEG;
typedef long long ll;


SEG seg[1 << 18];
SEG dummy;
int seg_size;

void init(int N)
{
    seg_size = 1;
    while (seg_size < N){
        seg_size *= 2;
    }
    
    memset(seg, -1, sizeof(seg));
}

void update(int k, int x)
{
    k += seg_size - 1;
    seg[k].val = x;
    seg[k].pos = k - (seg_size - 1);
    
    while (k != 0){
        k = (k - 1) / 2;
        if (seg[k * 2 + 2].val > seg[k * 2 + 1].val){
            seg[k] = seg[k * 2 + 2];
        }
        else if (seg[k * 2 + 1].val > seg[k * 2 + 2].val){
            seg[k] = seg[k * 2 + 1];
        }
        else {
            seg[k] = (seg[k * 2 + 1].pos < seg[k * 2 + 2].pos) ? seg[k * 2 + 2] : seg[k * 2 + 1];
        }
    }
}

SEG query(int a, int b, int k, int l, int r)
{
    SEG vl, vr;
    
    if (r <= a || b <= l){
        return (dummy);
    }
    
    if (a <= l && r <= b){
        return (seg[k]);
    }
    else {
        vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    }
    if (vl.val > vr.val || (vl.val == vr.val && vl.pos > vr.pos)){
        return (vl);
    }
    else {
        return (vr);
    }
}

int main(void)
{
    int i, j;
    int N, H;
    int damage[MAX_N];
    static ll curLife[MAX_N], sum;
    int life;
    int tail;
    int ans;
    SEG temp;
    
    scanf("%d%d", &N, &H);
    
    init(N);
    
    sum = H;
    for (i = 0; i < N - 1; i++){
        scanf("%d%d", &damage[i], &life);
        update(i, (int)min((ll)life, ((ll)H - sum)));
        
        curLife[i] = sum;
        sum -= damage[i];
    }
    curLife[i] = sum;
    update(i, 0);
    
    dummy.val = -100000, dummy.pos = -1;
    
    life = H;
    ans = 0;
    tail = 0;
    
    for (i = 0; i < N; i++){
        while (curLife[i] <= 0){
            temp = query(tail, i, 0, 0, seg_size);
            ans++;
            tail = temp.pos;
            for (j = temp.pos; j < N; j++){
                curLife[j] += temp.val;
                update(j, min(seg[seg_size + j - 1].val, H - curLife[j]));
            }
        }
    }
    
    printf("%d\n", ans);
    
    return (0);
}

コメント 1

sinapusu2002こと堀江伸一です。
ダンジョンの問題。
大昔解いて最初の階で大きな値が来てその後の階で小さい値が連続すると絶対計算量が間に合わないコードを書いたら実行速度一位で通りました。

この問題採点データかなり甘いようです。
一位を取れたことから見て多分極端で恣意的なデータは少なくランダム性の高い数字が並んでると見ています。
その辺見越して楽観的なコードで挑戦してみるとよいかと。

もう一度挑戦してみようかなこの問題。
厳しいデータが来ても高速に動く処理を考えるのも楽しそうです。
今この問題で俺は何位まで落ちてるのかな楽しみ。
by 堀江伸一 (2013-09-18 17:05)