結果

問題 No.5017 Tool-assisted Shooting
コンテスト
ユーザー 👑 wanui
提出日時 2023-07-18 12:42:51
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
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;
}
0