結果

問題 No.5017 Tool-assisted Shooting
ユーザー platinumplatinum
提出日時 2023-07-13 12:32:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,861 ms / 2,000 ms
コード長 12,638 bytes
コンパイル時間 1,923 ms
コンパイル使用メモリ 129,116 KB
実行使用メモリ 24,480 KB
スコア 4,034,879
平均クエリ数 1000.00
最終ジャッジ日時 2023-07-16 13:49:16
合計ジャッジ時間 170,696 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,618 ms
23,628 KB
testcase_01 AC 1,687 ms
23,820 KB
testcase_02 AC 1,485 ms
24,300 KB
testcase_03 AC 1,632 ms
24,012 KB
testcase_04 AC 1,557 ms
23,640 KB
testcase_05 AC 1,596 ms
24,012 KB
testcase_06 AC 1,616 ms
23,520 KB
testcase_07 AC 1,615 ms
23,652 KB
testcase_08 AC 1,537 ms
23,508 KB
testcase_09 AC 1,567 ms
24,348 KB
testcase_10 AC 1,663 ms
24,024 KB
testcase_11 AC 1,503 ms
24,012 KB
testcase_12 AC 1,626 ms
23,832 KB
testcase_13 AC 1,634 ms
23,628 KB
testcase_14 AC 1,671 ms
24,312 KB
testcase_15 AC 1,605 ms
23,376 KB
testcase_16 AC 1,531 ms
23,640 KB
testcase_17 AC 1,658 ms
23,640 KB
testcase_18 AC 1,634 ms
23,508 KB
testcase_19 AC 1,652 ms
24,240 KB
testcase_20 AC 1,597 ms
23,844 KB
testcase_21 AC 1,685 ms
23,604 KB
testcase_22 AC 1,513 ms
23,352 KB
testcase_23 AC 1,547 ms
23,520 KB
testcase_24 AC 1,639 ms
23,364 KB
testcase_25 AC 1,695 ms
23,616 KB
testcase_26 AC 1,592 ms
24,024 KB
testcase_27 AC 1,611 ms
24,012 KB
testcase_28 AC 1,685 ms
23,652 KB
testcase_29 AC 1,497 ms
23,652 KB
testcase_30 AC 1,468 ms
23,508 KB
testcase_31 AC 1,543 ms
24,012 KB
testcase_32 AC 1,668 ms
24,252 KB
testcase_33 AC 1,759 ms
24,012 KB
testcase_34 AC 1,612 ms
23,400 KB
testcase_35 AC 1,653 ms
23,400 KB
testcase_36 AC 1,567 ms
23,400 KB
testcase_37 AC 1,650 ms
23,400 KB
testcase_38 AC 1,632 ms
23,832 KB
testcase_39 AC 1,611 ms
24,300 KB
testcase_40 AC 1,630 ms
24,036 KB
testcase_41 AC 1,615 ms
24,024 KB
testcase_42 AC 1,726 ms
23,376 KB
testcase_43 AC 1,564 ms
24,300 KB
testcase_44 AC 1,660 ms
23,400 KB
testcase_45 AC 1,648 ms
24,036 KB
testcase_46 AC 1,648 ms
24,012 KB
testcase_47 AC 1,543 ms
23,652 KB
testcase_48 AC 1,677 ms
24,312 KB
testcase_49 AC 1,578 ms
23,832 KB
testcase_50 AC 1,612 ms
23,820 KB
testcase_51 AC 1,621 ms
23,520 KB
testcase_52 AC 1,673 ms
24,348 KB
testcase_53 AC 1,633 ms
23,412 KB
testcase_54 AC 1,720 ms
24,240 KB
testcase_55 AC 1,622 ms
24,012 KB
testcase_56 AC 1,577 ms
24,240 KB
testcase_57 AC 1,558 ms
23,388 KB
testcase_58 AC 1,618 ms
24,012 KB
testcase_59 AC 1,693 ms
23,844 KB
testcase_60 AC 1,646 ms
24,036 KB
testcase_61 AC 1,588 ms
23,652 KB
testcase_62 AC 1,559 ms
23,412 KB
testcase_63 AC 1,655 ms
23,508 KB
testcase_64 AC 1,670 ms
24,240 KB
testcase_65 AC 1,861 ms
23,412 KB
testcase_66 AC 1,666 ms
24,012 KB
testcase_67 AC 1,627 ms
23,820 KB
testcase_68 AC 1,627 ms
23,532 KB
testcase_69 AC 1,621 ms
23,364 KB
testcase_70 AC 1,640 ms
24,024 KB
testcase_71 AC 1,659 ms
23,628 KB
testcase_72 AC 1,506 ms
23,628 KB
testcase_73 AC 1,655 ms
24,036 KB
testcase_74 AC 1,475 ms
24,312 KB
testcase_75 AC 1,634 ms
23,616 KB
testcase_76 AC 1,638 ms
23,352 KB
testcase_77 AC 1,693 ms
24,240 KB
testcase_78 AC 1,572 ms
23,364 KB
testcase_79 AC 1,629 ms
24,324 KB
testcase_80 AC 1,642 ms
24,000 KB
testcase_81 AC 1,578 ms
24,000 KB
testcase_82 AC 1,596 ms
23,844 KB
testcase_83 AC 1,619 ms
23,664 KB
testcase_84 AC 1,632 ms
24,360 KB
testcase_85 AC 1,695 ms
23,520 KB
testcase_86 AC 1,638 ms
24,264 KB
testcase_87 AC 1,596 ms
24,372 KB
testcase_88 AC 1,694 ms
23,532 KB
testcase_89 AC 1,611 ms
23,364 KB
testcase_90 AC 1,656 ms
23,652 KB
testcase_91 AC 1,726 ms
23,820 KB
testcase_92 AC 1,488 ms
23,508 KB
testcase_93 AC 1,637 ms
24,480 KB
testcase_94 AC 1,554 ms
24,000 KB
testcase_95 AC 1,644 ms
23,832 KB
testcase_96 AC 1,667 ms
23,592 KB
testcase_97 AC 1,602 ms
23,400 KB
testcase_98 AC 1,614 ms
24,240 KB
testcase_99 AC 1,606 ms
23,808 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
#include <random>
#include <cassert>

using namespace std;
using pii = pair<int,int>;

constexpr int width = 25;  // フィールドの幅
constexpr int height = 60; // フィールドの高さ
constexpr int max_turn = 1000; // ゲームの最大ターン数
constexpr int level_up = 100; // レベルアップに必要なパワー値
constexpr int min_P = 1;
constexpr int max_P = 8;

constexpr int INF = (int)1e9;

constexpr int testcase = 1;
bool submit = true;

void read_input(){
    std::stringstream ss;
    std::string num = std::to_string(testcase);
    int siz = num.size();
    for(int i = 0; i < 4 - siz; i++) num = '0' + num;
    ss << "in/" << num << ".txt";
    FILE *in = freopen(ss.str().c_str(), "r", stdin);
}
void file_output(){
    std::stringstream ss;
    std::string num = std::to_string(testcase);
    int siz = num.size();
    for(int i = 0; i < 4 - siz; i++) num = '0' + num;
    ss << "out_mcts/" << num << ".txt";
    FILE *out = freopen(ss.str().c_str(), "w", stdout);
}

// 敵機の情報
struct Enemy {
	int init_hp;
	int h, p;
	int x, y;
	Enemy(int h, int p, int x) : h(h), p(p), x(x) {
		init_hp = h;
		y = height - 1;
	}
};
void MoveEnemy(vector<queue<Enemy>>& enemies) {
	for(int x = 0; x < width; x++) {
		int siz = enemies[x].size();
		for(int i = 0; i < siz; i++) {
			Enemy enemy = enemies[x].front(); enemies[x].pop();
			enemy.y--;
			if(enemy.y < 0) continue;
			enemies[x].push(enemy);
		}
	}
}

// 自機の情報
struct Player {
	int x, y;
	int score;
	int power, level;
	Player(int x, int y) : x(x), y(y) {
		score = 0;
		power = 0;
		level = 1;
	}
	void destroy_enemy(const Enemy& e) {
		score += e.init_hp;
		power += e.p;
		level = 1 + power / level_up;
	}
	bool try_move(const vector<queue<Enemy>>& enemies, int move) const {
		// 目の前に倒せる敵がいるなら動かない
		if(!enemies[x].empty()) {
			const Enemy& enemy = enemies[x].front();
			int des = (enemy.h + level - 1) / level;
			if(enemy.y >= des) {
				if(move == 0) return true;
				else return false;
			}
		}

		int nx = (x + move + width) % width;
		if(enemies[nx].empty()) return true;
		const Enemy& enemy = enemies[nx].front();
		int lx = (nx - 1 + width) % width, rx = (nx + 1) % width;

		int des = (enemy.h + level - 1) / level;
		if(enemy.y >= des) return true;
		// 目の前の敵を倒せない場合は左右に動けるなら動く
		else if(move == 0) {
			if(enemies[lx].empty() || enemies[rx].empty()) return false;
			if(enemies[lx].front().y > 1 || enemies[rx].front().y > 1) return false;
		}

		// 次のターン確実に当たるならfalse
		if(enemy.y <= 1) return false;
		// 次のターン包囲されるならfalse
		else if(enemy.y <= 3) {
			if(enemies[lx].empty() || enemies[rx].empty()) {
				return true;
			}
			const Enemy& left_enemy = enemies[lx].front();
			const Enemy& right_enemy = enemies[rx].front();
			if(left_enemy.y <= 2 && right_enemy.y <= 2) {
				return false;
			}
			else return true;
		}
		else return true;
	}
	void apply_move(int move, bool output = false) {
		if(output) {
			const string actions = "LSR";
			std::cout << actions[move+1] << std::endl;
			//std::cout << "# " << c << std::endl;
		}
		x = (x + move + width) % width;
	}
};
// 敵機の攻撃処理、与えたダメージが返る
int AttackEnemy(Player& player, vector<queue<Enemy>>& enemies) {
	if(enemies[player.x].empty()) return 0;
	Enemy& target_enemy = enemies[player.x].front();
	int damage = min(target_enemy.h, player.level);
	target_enemy.h -= player.level;
	if(target_enemy.h <= 0) {
		player.destroy_enemy(target_enemy);
		enemies[player.x].pop();
	}
	return damage;
}

struct beta_distribution {
	double alpha, beta;
	beta_distribution(double a, double b) : alpha (a), beta(b) {}
	void update(bool appeared) {
		if(appeared) alpha += 1.0;
		else beta += 1.0;
	}
	double mu() {
		return alpha / (alpha + beta);
	}
	double var() {
		bool tot = alpha + beta;
		return alpha * beta / tot / tot / (tot + 1.0);
	}
};
vector<beta_distribution> Beta(width, {1.0, 24.0}); 

random_device rnd;
mt19937 engine(rnd());
uniform_int_distribution<> cent(1, 100);

struct State {
	int now_turn, depth;
	//double score;
	Player player;
	vector<queue<Enemy>> enemies;
	vector<int> legal_actions; // L : -1, S : 0, R : 1

	void check_actions() {
		legal_actions.clear();
		for(int move = -1; move <= 1; move++) {
			if(player.try_move(enemies, move)) {
				legal_actions.emplace_back(move);
			}
		}
	}
	State(int now_turn, int depth, const Player& player, const vector<queue<Enemy>>& enemies) :
	now_turn(now_turn), depth(depth), player(player), enemies(enemies) {
		check_actions();
	}

	void advance(int move) {
		this->now_turn++;
		this->depth--;
		this->player.apply_move(move);
		AttackEnemy(this->player, this->enemies);
		MoveEnemy(this->enemies);
		// ベイズ推定した確率に基づいてランダムに敵機を生成する
		int T = now_turn;
		for(int x = 0; x < width; x++) {
			int poss = Beta[x].mu() * 100;
			poss = max(poss, min_P);
			poss = min(poss, max_P);
			if(cent(engine) <= poss) {
				double d_hp = 7.5 + 0.15 * T;
				double d_power = d_hp * 0.8;
				int hp = max(1, (int)d_hp);
				int power = max(0, (int)d_power);
				this->enemies[x].emplace(hp, power, x);
			}
		}
		check_actions();
	}
	bool is_end() {
		if(now_turn >= max_turn) return true;
		if(depth <= 0) return true;
		return false;
	}
	bool random_action() {
		if(legal_actions.empty()) return false;
		if(is_end()) return false;
		int choice = legal_actions.size();
		uniform_int_distribution<> choose_action(0, choice - 1);
		int move = choose_action(engine);
		advance(legal_actions[move]);
		return true;
	}
};

double RandomPlayout(State& state, bool endgame) {
	while(state.random_action());
	if(endgame) return state.player.score;
	else return state.player.power;
}

constexpr int EXPAND_THRESHOLD = 20;
constexpr int GET_SCORE = 800;
constexpr int GET_POWER = 500;
class Node {
private:
	State state;
	double value;
	double C;
public:
	vector<Node> child_nodes;
	int trial;
	Node(const State& state) : state(state) {
		value = 0.0;
		trial = 0;
		if(state.now_turn >= GET_SCORE) C = state.player.score * 2;
		else if (state.now_turn >= GET_POWER) C = state.player.power * 1.5;
	}

	double evaluate() {
		if(this->state.is_end()) {
			double res = 0.0;
			if (this->state.now_turn >= GET_SCORE) {
				res = this->state.player.score;
			}
			else if(this->state.now_turn >= GET_POWER) {
				res = this->state.player.power;
			}
			this->value += res;
			this->trial++;
			return res;
		}
		if(this->child_nodes.empty()) {
			State copy_state = this->state;
			bool endgame = (state.now_turn >= GET_SCORE);
			double res = RandomPlayout(copy_state, endgame);
			this->value += res;
			this->trial++;

			if(this->trial == EXPAND_THRESHOLD) {
				this->expand();
			}
			return res;
		}
		else {
			double res = this->NextChildNode().evaluate();
			this->value += res;
			this->trial++;
			return res;
		}
	}
	bool expand() {
		auto legal_actions = this->state.legal_actions;
		if(legal_actions.empty()) return false;;
		this->child_nodes.clear();
		for(const auto move : legal_actions) {
			this->child_nodes.emplace_back(this->state);
			this->child_nodes.back().state.advance(move);
		}
		return true;
	}
	Node& NextChildNode() {
		// 試行回数が0なら優先的に選択
		for(auto& child_node : this->child_nodes) {
			if(child_node.trial == 0) {
				return child_node;
			}
		}
		// UCB1に基づいてノードを選択
		double total_trial = 0.0;
		for(auto& child_node : this->child_nodes) {
			total_trial += child_node.trial;
		}
		double best_value = -INF;
		int arg_best = -1;
		for(int i = 0; i < (int)this->child_nodes.size(); i++) {
			const auto& child_node = this->child_nodes[i];
			double ucb1 = child_node.value / (double)child_node.trial
			+ C * sqrt(2.0 * log(total_trial) / (double)child_node.trial);
			if(ucb1 > best_value) {
				best_value = ucb1;
				arg_best = i;
			}
		}
		return this->child_nodes[arg_best];
	}
};

int MCTS(const State& state, const int playout) {
	Node root_node = Node(state);
	// 合法手がない場合は諦める
	if(!root_node.expand()) {
		return 0;
	}
	for(int i = 0; i < playout; i++) {
		root_node.evaluate();
	}
	auto legal_actions = state.legal_actions;
	int max_trial = -1;
	int arg_best = -1;
	for(int i = 0; i < (int)legal_actions.size(); i++) {
		int trial = root_node.child_nodes[i].trial;
		if(trial > max_trial) {
			max_trial = trial;
			arg_best = i;
		}
	}
	return legal_actions[arg_best];
}

int main(){
	if(!submit) {
		read_input();
		file_output();
	}

	Player player(12, 0);
	vector<queue<Enemy>> enemies(width);

	vector<int> P(width);
	if(!submit) {
		for(int i = 0; i < width; i++) cin >> P[i];
	}

	for(int T = 1; T <= max_turn; T++) {
		// 敵機の移動
		MoveEnemy(enemies);
		// 入力の受け取り
		int n;
		cin >> n;
		if(n == -1) {
			std::cerr << "turn = " << T << std::endl;
			std::cerr << "score = " << player.score << std::endl;
			return 0;
		}
		vector<int> appeared(width);
		for(int i = 0; i < n; i++) {
			int h, p, x;
			cin >> h >> p >> x;
			enemies[x].emplace(h, p, x);
			appeared[x] = 1;
		}
		for(int x = 0; x < width; x++) {
			Beta[x].update(appeared[x]);
		}
		// 自機の移動
		// 中盤はパワー優先、終盤はスコア優先のMCTS
		if(T >= GET_POWER) {
			int depth = 20; // MCTSの深さを設定
			State state(T, depth, player, enemies);
			int playout = 150; // MCTSのプレイアウト数を設定
			int next_move = MCTS(state, playout);
			player.apply_move(next_move, true);
		}
		else {
		// 敵機を倒せない列には移動しない
		vector<pii> front_enemy(width, {-1, -1});
		for(int x = 0; x < width; x++) {
			if(enemies[x].empty()) continue;
			int dx1 = abs(x - player.x);
			int dx2 = abs(x - (player.x - width));
			int dx = max(1, min(dx1, dx2));
			
			const Enemy& enemy = enemies[x].front();
			int des = dx - 1 + (enemy.h + player.level - 1) / player.level;
			if(enemy.y >= des) {
				front_enemy[x] = {enemy.y, des};
			}
		}
		// 前半は一番パワーが稼げる敵、後半は一番スコアが稼げる敵を探す
		const Enemy* near_enemy = nullptr;
		double max_value = -1.0;
		for(int x = 0; x < width; x++) {
			int y = front_enemy[x].first;
			if(y == -1) continue;
			int des = front_enemy[x].second;
			double value = 0.0;
			if(player.level < 70) {
				value = (double)enemies[x].front().p / des;
			}
			else {
				value = (double)enemies[x].front().init_hp / des;
			}
			if(value > max_value) {
				max_value = value;
				near_enemy = &enemies[x].front();
			}
		}
		// 倒せる敵がいない場合
		if(!near_enemy) {
			if(player.try_move(enemies, 0)) {
				player.apply_move(0, true);
			}
			else if(player.try_move(enemies, -1)) {
				player.apply_move(-1, true);
			}
			else if(player.try_move(enemies, 1)) {
				player.apply_move(1, true);
			}
			else player.apply_move(0, true);
		}
		// 同列に倒せる敵がいるならとどまる
		else if(near_enemy->x == player.x) {
			player.apply_move(0, true);
		}
		// 敵が左にいる場合
		else if(near_enemy->x < player.x) {
			int ex = near_enemy->x, px = player.x;
			int left = px - ex, right = ex - (px - width);
			if(left < right) {
				if(player.try_move(enemies, -1)) {
					player.apply_move(-1, true);
				}
				else if(player.try_move(enemies, 0)) {
					player.apply_move(0, true);
				}
				else player.apply_move(1, true);
			}
			else {
				if(player.try_move(enemies, 1)) {
					player.apply_move(1, true);
				}
				else if(player.try_move(enemies, 0)) {
					player.apply_move(0, true);
				}
				else player.apply_move(-1, true);
			}
		}
		// 敵が右にいる場合
		else {
			int ex = near_enemy->x, px = player.x;
			int left = px + width - ex, right = ex - px;
			if(left < right) {
				if(player.try_move(enemies, -1)) {
					player.apply_move(-1, true);
				}
				else if(player.try_move(enemies, 0)) {
					player.apply_move(0, true);
				}
				else player.apply_move(1, true);
			}
			else {
				if(player.try_move(enemies, 1)) {
					player.apply_move(1, true);
				}
				else if(player.try_move(enemies, 0)) {
					player.apply_move(0, true);
				}
				else player.apply_move(-1, true);
			}			
		}
		/*
		if(near_enemy) {
			cout << "# " << near_enemy->x << " " << near_enemy->y << endl;
			cout << "# hp = " << near_enemy->h << endl;
		}
		*/
		}
		// 自機の攻撃
		AttackEnemy(player, enemies);
	}
	std::cerr << "turn = " << max_turn + 1 << endl;
	std::cerr << "score = " << player.score << endl;

	return 0;
}
0