#892837 (C++17) No.5017 Tool-assisted Shooting

提出ソース

結果

問題	No.5017 Tool-assisted Shooting
ユーザー	wanui
提出日時	2023-07-18 12:42:51
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	725 ms / 2,000 ms
コード長	3,966 bytes
コンパイル時間	2,140 ms
コンパイル使用メモリ	204,048 KB
実行使用メモリ	24,420 KB
スコア	4,630,712
平均クエリ数	1000.00
最終ジャッジ日時	2023-07-18 12:44:05
合計ジャッジ時間	73,629 ms
ジャッジサーバーID （参考情報）	judge15 / judge12
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	633 ms 23,832 KB
testcase_01	AC	677 ms 24,408 KB
testcase_02	AC	584 ms 24,036 KB
testcase_03	AC	654 ms 24,012 KB
testcase_04	AC	605 ms 23,628 KB
testcase_05	AC	625 ms 23,412 KB
testcase_06	AC	631 ms 24,348 KB
testcase_07	AC	637 ms 23,640 KB
testcase_08	AC	606 ms 23,712 KB
testcase_09	AC	612 ms 24,300 KB
testcase_10	AC	654 ms 23,640 KB
testcase_11	AC	604 ms 23,808 KB
testcase_12	AC	663 ms 24,180 KB
testcase_13	AC	626 ms 24,048 KB
testcase_14	AC	683 ms 24,048 KB
testcase_15	AC	616 ms 24,036 KB
testcase_16	AC	626 ms 23,544 KB
testcase_17	AC	636 ms 23,412 KB
testcase_18	AC	659 ms 23,412 KB
testcase_19	AC	635 ms 23,424 KB
testcase_20	AC	635 ms 23,712 KB
testcase_21	AC	646 ms 23,628 KB
testcase_22	AC	588 ms 23,856 KB
testcase_23	AC	624 ms 24,024 KB
testcase_24	AC	638 ms 24,012 KB
testcase_25	AC	689 ms 24,180 KB
testcase_26	AC	629 ms 23,400 KB
testcase_27	AC	637 ms 24,024 KB
testcase_28	AC	646 ms 23,808 KB
testcase_29	AC	597 ms 24,012 KB
testcase_30	AC	596 ms 23,664 KB
testcase_31	AC	609 ms 24,384 KB
testcase_32	AC	653 ms 23,712 KB
testcase_33	AC	663 ms 24,036 KB
testcase_34	AC	650 ms 24,336 KB
testcase_35	AC	635 ms 23,676 KB
testcase_36	AC	629 ms 24,348 KB
testcase_37	AC	643 ms 24,048 KB
testcase_38	AC	658 ms 24,024 KB
testcase_39	AC	633 ms 24,264 KB
testcase_40	AC	635 ms 24,408 KB
testcase_41	AC	625 ms 23,388 KB
testcase_42	AC	651 ms 23,388 KB
testcase_43	AC	637 ms 23,616 KB
testcase_44	AC	643 ms 23,820 KB
testcase_45	AC	697 ms 23,400 KB
testcase_46	AC	647 ms 23,544 KB
testcase_47	AC	630 ms 24,024 KB
testcase_48	AC	646 ms 23,424 KB
testcase_49	AC	622 ms 23,532 KB
testcase_50	AC	652 ms 23,448 KB
testcase_51	AC	633 ms 23,364 KB
testcase_52	AC	677 ms 24,300 KB
testcase_53	AC	634 ms 23,652 KB
testcase_54	AC	683 ms 23,820 KB
testcase_55	AC	622 ms 24,420 KB
testcase_56	AC	648 ms 24,192 KB
testcase_57	AC	611 ms 23,652 KB
testcase_58	AC	630 ms 24,012 KB
testcase_59	AC	678 ms 23,640 KB
testcase_60	AC	632 ms 23,544 KB
testcase_61	AC	642 ms 24,360 KB
testcase_62	AC	611 ms 23,424 KB
testcase_63	AC	658 ms 23,664 KB
testcase_64	AC	640 ms 23,820 KB
testcase_65	AC	725 ms 23,424 KB
testcase_66	AC	639 ms 23,952 KB
testcase_67	AC	633 ms 23,376 KB
testcase_68	AC	667 ms 23,532 KB
testcase_69	AC	634 ms 24,372 KB
testcase_70	AC	658 ms 23,952 KB
testcase_71	AC	642 ms 23,628 KB
testcase_72	AC	621 ms 23,376 KB
testcase_73	AC	634 ms 24,336 KB
testcase_74	AC	615 ms 24,012 KB
testcase_75	AC	638 ms 23,964 KB
testcase_76	AC	666 ms 23,820 KB
testcase_77	AC	649 ms 24,420 KB
testcase_78	AC	621 ms 24,036 KB
testcase_79	AC	657 ms 23,664 KB
testcase_80	AC	642 ms 24,324 KB
testcase_81	AC	644 ms 23,544 KB
testcase_82	AC	633 ms 24,024 KB
testcase_83	AC	644 ms 24,300 KB
testcase_84	AC	636 ms 23,424 KB
testcase_85	AC	683 ms 23,952 KB
testcase_86	AC	639 ms 23,820 KB
testcase_87	AC	625 ms 23,664 KB
testcase_88	AC	672 ms 23,388 KB
testcase_89	AC	634 ms 24,276 KB
testcase_90	AC	660 ms 24,252 KB
testcase_91	AC	672 ms 23,400 KB
testcase_92	AC	624 ms 23,628 KB
testcase_93	AC	648 ms 24,396 KB
testcase_94	AC	630 ms 23,436 KB
testcase_95	AC	635 ms 23,400 KB
testcase_96	AC	671 ms 24,012 KB
testcase_97	AC	634 ms 23,628 KB
testcase_98	AC	627 ms 23,808 KB
testcase_99	AC	652 ms 23,808 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 = 0.01 * ((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;
		total_score += (init_turn > 950) ? state.total_hp : state.total_power;
	}
	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;
}

yukicoder

結果

テストケース

ソースコード