結果

問題 No.5017 Tool-assisted Shooting
ユーザー wanuiwanui
提出日時 2023-07-17 08:58:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 693 ms / 2,000 ms
コード長 3,884 bytes
コンパイル時間 2,239 ms
コンパイル使用メモリ 204,088 KB
実行使用メモリ 24,396 KB
スコア 4,552,779
平均クエリ数 1000.00
最終ジャッジ日時 2023-07-17 08:59:41
合計ジャッジ時間 72,418 ms
ジャッジサーバーID
(参考情報)
judge13 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 674 ms
23,628 KB
testcase_01 AC 656 ms
24,348 KB
testcase_02 AC 619 ms
23,424 KB
testcase_03 AC 631 ms
23,664 KB
testcase_04 AC 637 ms
24,312 KB
testcase_05 AC 619 ms
23,580 KB
testcase_06 AC 632 ms
23,988 KB
testcase_07 AC 630 ms
23,388 KB
testcase_08 AC 612 ms
24,336 KB
testcase_09 AC 629 ms
23,484 KB
testcase_10 AC 642 ms
24,036 KB
testcase_11 AC 628 ms
24,060 KB
testcase_12 AC 631 ms
24,360 KB
testcase_13 AC 650 ms
23,388 KB
testcase_14 AC 652 ms
24,348 KB
testcase_15 AC 652 ms
23,340 KB
testcase_16 AC 606 ms
23,556 KB
testcase_17 AC 645 ms
23,976 KB
testcase_18 AC 632 ms
23,388 KB
testcase_19 AC 632 ms
24,036 KB
testcase_20 AC 642 ms
24,012 KB
testcase_21 AC 651 ms
23,340 KB
testcase_22 AC 620 ms
24,000 KB
testcase_23 AC 608 ms
23,652 KB
testcase_24 AC 660 ms
23,652 KB
testcase_25 AC 654 ms
23,376 KB
testcase_26 AC 628 ms
24,300 KB
testcase_27 AC 620 ms
23,340 KB
testcase_28 AC 649 ms
23,388 KB
testcase_29 AC 602 ms
24,060 KB
testcase_30 AC 595 ms
24,288 KB
testcase_31 AC 639 ms
23,616 KB
testcase_32 AC 636 ms
23,424 KB
testcase_33 AC 691 ms
23,628 KB
testcase_34 AC 615 ms
23,628 KB
testcase_35 AC 640 ms
23,988 KB
testcase_36 AC 605 ms
23,544 KB
testcase_37 AC 638 ms
23,616 KB
testcase_38 AC 635 ms
24,060 KB
testcase_39 AC 636 ms
23,664 KB
testcase_40 AC 657 ms
23,580 KB
testcase_41 AC 624 ms
23,676 KB
testcase_42 AC 670 ms
23,376 KB
testcase_43 AC 619 ms
23,808 KB
testcase_44 AC 670 ms
23,340 KB
testcase_45 AC 644 ms
23,496 KB
testcase_46 AC 651 ms
23,376 KB
testcase_47 AC 609 ms
24,312 KB
testcase_48 AC 647 ms
24,324 KB
testcase_49 AC 619 ms
24,396 KB
testcase_50 AC 634 ms
23,532 KB
testcase_51 AC 639 ms
23,508 KB
testcase_52 AC 650 ms
23,640 KB
testcase_53 AC 637 ms
24,048 KB
testcase_54 AC 648 ms
23,544 KB
testcase_55 AC 649 ms
23,388 KB
testcase_56 AC 626 ms
23,340 KB
testcase_57 AC 622 ms
24,324 KB
testcase_58 AC 626 ms
23,616 KB
testcase_59 AC 663 ms
24,336 KB
testcase_60 AC 633 ms
24,012 KB
testcase_61 AC 630 ms
23,988 KB
testcase_62 AC 625 ms
23,976 KB
testcase_63 AC 666 ms
24,240 KB
testcase_64 AC 642 ms
24,036 KB
testcase_65 AC 693 ms
24,384 KB
testcase_66 AC 653 ms
24,276 KB
testcase_67 AC 630 ms
23,328 KB
testcase_68 AC 638 ms
23,640 KB
testcase_69 AC 629 ms
23,448 KB
testcase_70 AC 655 ms
23,844 KB
testcase_71 AC 632 ms
24,060 KB
testcase_72 AC 591 ms
23,376 KB
testcase_73 AC 628 ms
23,808 KB
testcase_74 AC 598 ms
23,976 KB
testcase_75 AC 639 ms
23,508 KB
testcase_76 AC 635 ms
23,424 KB
testcase_77 AC 653 ms
23,376 KB
testcase_78 AC 623 ms
23,352 KB
testcase_79 AC 650 ms
24,012 KB
testcase_80 AC 641 ms
24,312 KB
testcase_81 AC 658 ms
23,976 KB
testcase_82 AC 638 ms
23,856 KB
testcase_83 AC 627 ms
24,024 KB
testcase_84 AC 651 ms
23,640 KB
testcase_85 AC 638 ms
24,360 KB
testcase_86 AC 643 ms
23,676 KB
testcase_87 AC 624 ms
23,364 KB
testcase_88 AC 684 ms
23,604 KB
testcase_89 AC 634 ms
23,532 KB
testcase_90 AC 668 ms
23,604 KB
testcase_91 AC 668 ms
24,348 KB
testcase_92 AC 594 ms
23,976 KB
testcase_93 AC 641 ms
24,348 KB
testcase_94 AC 604 ms
24,012 KB
testcase_95 AC 669 ms
23,340 KB
testcase_96 AC 647 ms
23,364 KB
testcase_97 AC 670 ms
23,328 KB
testcase_98 AC 629 ms
23,796 KB
testcase_99 AC 656 ms
23,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;
const int H = 60;
const int W = 25;
vector<char> OPTBL = {'L', 'S', 'R'};
struct enemy_t {
	int init_hp;
	int hp;
	int power;
};
struct state_t {
	enemy_t board[H][W];
	int total_power;
	int total_hp;
	int my_c;
	int turn;
	int level() {
		return 1 + total_power / 100;
	}
};
void read_enemies(state_t &state) {
	int n;
	cin >> n;
	while (n--) {
		int h, p, x;
		cin >> h >> p >> x;
		state.board[H - 1][x] = enemy_t{h, h, p};
	}
}
bool move_enemies(state_t &state) {
	for (int r = 0; r < H - 1; r++) {
		for (int c = 0; c < W; c++) {
			state.board[r][c] = state.board[r + 1][c];
		}
	}
	for (int c = 0; c < W; c++) {
		state.board[H - 1][c] = {-1, -1, -1};
	}
	return state.board[0][state.my_c].hp <= 0;
}
bool move_attack(state_t &state, char op) {
	if (op == 'L') {
		state.my_c--;
	} else if (op == 'R') {
		state.my_c++;
	}
	state.my_c = (state.my_c + W) % W;
	if (state.board[0][state.my_c].hp > 0) return false;
	for (int i = 1; i < H; i++) {
		if (state.board[i][state.my_c].hp > 0) {
			state.board[i][state.my_c].hp -= state.level();
			if (state.board[i][state.my_c].hp <= 0) {
				state.total_power += state.board[i][state.my_c].power;
				state.total_hp += state.board[i][state.my_c].init_hp;
				state.board[i][state.my_c] = {-1, -1, -1};
			}
			break;
		}
	}
	return true;
}
char greedy_op(state_t &state) {
	pair<double, int> max_score = {-1e50, -1};
	for (int o = 0; o <= 2; o++) {
		double score = (state.turn + o) % 3;
		int c = state.my_c;
		if (o == 0) c--;
		if (o == 2) c++;
		c = (c + W) % W;

		if (state.board[0][c].hp > 0) {
			score += -1e16;
		}
		for (int r = 1; r < H; r++) {
			int level = state.level();
			enemy_t e = state.board[r][c];
			if (e.hp <= 0) continue;
			int turns = (e.hp + level - 1) / level;
			if (turns > r) {
				score += -1e10 * (H - r);
			} else {
				score += (state.turn > 950) ? (1e5 * e.init_hp / turns) : (1e5 * e.power / turns);
			}
			break;
		}
		for (int d = 0; d < W; d++) {
			for (int r = 1; r < H; r++) {
				int distance = min(min(abs(c - W - d), abs(c + W - d)), abs(c - d));
				enemy_t e = state.board[r][d];
				if (e.hp <= 0) continue;
				int level = state.level();
				int turns = (e.hp + level - 1) / level;
				if (turns + distance > r) continue;
				score += (state.turn > 950) ? (1.0 * e.init_hp / turns / (distance + 1.0)) : (1.0 * e.power / turns / (distance + 1.0));
			}
		}
		max_score = max({score, o}, max_score);
	}
	return OPTBL[max_score.second];
}
double simulation_score(int ini_op, state_t state) {
	double total_score = 0;
	int init_turn = state.turn;
	int end_turn = (init_turn > 200) ? min(init_turn + 30, 1000) : min(init_turn + 40, 1000);

	{
		char op = OPTBL[ini_op];
		bool alive2 = move_attack(state, op);
		if (!alive2) return -1e8;
	}
	for (int turn = init_turn + 1; turn <= end_turn; turn++) {
		state.turn = turn;
		bool alive1 = move_enemies(state);
		if (!alive1) {
			total_score -= 1e6;
			break;
		}
		char op = greedy_op(state);
		bool alive2 = move_attack(state, op);
		if (!alive2) {
			total_score -= 1e6;
			break;
		}
		total_score += (init_turn > 950) ? state.total_hp : state.total_power;
	}
	return total_score;
}
char select_op(state_t &state) {
	pair<double, int> max_score = {-1e50, -1};
	for (int o = 0; o <= 2; o++) {
		max_score = max({simulation_score(o, state), o}, max_score);
	}
	return OPTBL[max_score.second];
}
int main() {
	state_t state;
	{
		state.total_power = 0;
		state.total_hp = 0;
		state.my_c = 12;
		for (int r = 0; r < H; r++) {
			for (int c = 0; c < W; c++) {
				state.board[r][c] = {-1, -1, -1};
			}
		}
	}
	for (int turn = 1; turn <= 1000; turn++) {
		state.turn = turn;
		bool alive1 = move_enemies(state);
		if (!alive1) break;
		read_enemies(state);
		char op = select_op(state);
		cout << op << endl;
		bool alive2 = move_attack(state, op);
		if (!alive2) break;
	}
	return 0;
}
0