Submission #67897859

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#if 0
#if 0
#define KI_MAX 4096
void ki_set(int* ki, int pos, int value) {
  pos += KI_MAX - 1;
  ki[pos] = value;
  do {
    int a, b;
    pos = (pos - 1) / 2;
    a = ki[pos * 2 + 1];
    b = ki[pos * 2 + 2];
    ki[pos] = a >= b ? a : b;
  } while (pos > 0);
}
int ki_get_i(const int* ki, int idx, int ss, int se, int qs, int qe) {
  if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

#if 0

#if 0
#define KI_MAX 4096

void ki_set(int* ki, int pos, int value) {
	pos += KI_MAX - 1;
	ki[pos] = value;
	do {
		int a, b;
		pos = (pos - 1) / 2;
		a = ki[pos * 2 + 1];
		b = ki[pos * 2 + 2];
		ki[pos] = a >= b ? a : b;
	} while (pos > 0);
}

int ki_get_i(const int* ki, int idx, int ss, int se, int qs, int qe) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return ki[idx];
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		return 0;
	} else {
		int sm = ss + (se - ss) / 2;
		int l = ki_get_i(ki, idx * 2 + 1, ss, sm, qs, qe);
		int r = ki_get_i(ki, idx * 2 + 2, sm, se, qs, qe);
		return l >=r ? l : r;
	}
}

int ki_get(const int* ki, int qs, int qe) {
	return ki_get_i(ki, 0, 0, KI_MAX, qs, qe);
}

int kis[3123][KI_MAX * 2 - 1];
#else
int maryoku_tairyoku[3123][3123];
#endif

int N, H, M;
int A[3123], B[3123];

int memo[3123][3123];
int memo_maryoku[3123][3123];

int calc(int pos, int tairyoku, int maryoku) {
	int ans = 0;
	if (pos >= N) return 0;
	if (memo[pos][tairyoku]) {
		if (maryoku == memo_maryoku[pos][tairyoku]) return ~memo[pos][tairyoku];
		if (maryoku < memo_maryoku[pos][tairyoku]) return 0;
	}
	/* 上位互換性判定 */
#if 0
	if (ki_get(kis[pos], tairyoku, H + 1) > maryoku) return 0;
#else
	if (maryoku_tairyoku[pos][maryoku] > tairyoku) return 0;
#endif
	if (A[pos] <= tairyoku) {
		int candidate = calc(pos + 1, tairyoku - A[pos], maryoku) + 1;
		if (candidate > ans) ans = candidate;
	}
	if (B[pos] <= maryoku) {
		int candidate = calc(pos + 1, tairyoku, maryoku - B[pos]) + 1;
		if (candidate > ans) ans = candidate;
	}
#if 0
	ki_set(kis[pos], tairyoku, maryoku);
#else
	maryoku_tairyoku[pos][maryoku] = tairyoku;
#endif
	memo_maryoku[pos][tairyoku] = maryoku;
	return ~(memo[pos][tairyoku] = ~ans);
}

int main(void) {
	int i;
	if (scanf("%d%d%d", &N, &H, &M) != 3) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d%d", &A[i], &B[i]) != 2) return 1;
	}
	printf("%d\n", calc(0, H, M));
	return 0;
}

#else

#include <string.h>

void chmax(int* target, int candidate) {
	if (*target < candidate) *target = candidate;
}

int N, H, M;
int A[3123], B[3123];

int max_maryoku[3123][3123];

int main(void) {
	int i;
	int ans = 0;
	if (scanf("%d%d%d", &N, &H, &M) != 3) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d%d", &A[i], &B[i]) != 2) return 1;
	}
	memset(max_maryoku, -1, sizeof(max_maryoku));
	max_maryoku[0][H] = M;
	for (i = 0; i < N; i++) {
		int j;
		for (j = 0; j <= H; j++){
			if (max_maryoku[i][j] >= 0) {
				ans = i; /* 最終到達点を求める */
				/* 魔法を使わずに戦う */
				if (j >= A[i]) {
					chmax(&max_maryoku[i + 1][j - A[i]], max_maryoku[i][j]);
				}
				/* 魔法を使って戦う */
				if (max_maryoku[i][j] >= B[i]) {
					chmax(&max_maryoku[i + 1][j], max_maryoku[i][j] - B[i]);
				}
			}
		}
	}
	for (i = 0; i <= H; i++) {
		if (max_maryoku[N][i] >= 0) ans = N;
	}
	printf("%d\n", ans);
	return 0;
}

#endif

/*

[位置][体力][魔力]でメモ化探索をしたい → そのままやると死にそう
各位置で必ず体力か魔力を削るので、魔力は位置と体力から一意に決まる → 省略可
↑嘘 Aが同じでBが異なる敵が居た場合、どっちを魔力でやったかわからない

メモと一緒にそのときの魔力も書いておく
新しい探索の際の魔力が
多い → 探索をしなおす
同じ → メモの値を返す
少ない → 上位互換の状態で来れるはず、無駄なので0を返す
これでWAは回避できるかもだけど、計算量どやろ……？
↓
以下のコードで作ったランダムケースで2.8sだった 厳しそう

#include <stdio.h>

static unsigned int x=123456789;
static unsigned int y=362436069;
static unsigned int z=521288629;
static unsigned int w=88675123;

unsigned int randint(void) {
	unsigned int t;
	t = (x ^ (x << 11));
	x = y; y = z; z = w;
	w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
	return w;
}

int main(void) {
	int i;
	puts("3000 3000 3000");
	for (i = 0; i < 3000; i++) {
		unsigned int a = randint() % 50 + 1;
		unsigned int b = randint() % 50 + 1;
		printf("%u %u\n", a, b);
	}
	return 0;
}

魔力ごとにその魔力での最大体力も書いておく → 上位互換性判定
体力・魔力ともに上回るケースがあるかも知りたい → セグ木

→ セグ木使ったらむしろクソ時間かかった
その魔力だけの判定に → 2.6s あまり効かない

-----------

「上位互換性」をより活用するため、深さ優先探索から幅優先探索に切り替える
各階層の各体力ごとに、魔力が最大の条件だけ次に進む
→ 各階層で高々H+1パターンになり、いけそう

各階層に来たときの各体力について、実現できる最大の魔力を求める

*/

Submission Info

Judge Result