結果

問題 No.5017 Tool-assisted Shooting
ユーザー platinumplatinum
提出日時 2023-06-28 23:55:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 102 ms / 2,000 ms
コード長 5,433 bytes
コンパイル時間 2,485 ms
コンパイル使用メモリ 210,164 KB
実行使用メモリ 24,384 KB
スコア 2,760,634
平均クエリ数 3968.04
最終ジャッジ日時 2023-07-16 13:30:34
合計ジャッジ時間 15,932 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 102 ms
24,024 KB
testcase_01 AC 100 ms
24,012 KB
testcase_02 AC 87 ms
23,400 KB
testcase_03 AC 91 ms
23,364 KB
testcase_04 AC 89 ms
23,616 KB
testcase_05 AC 93 ms
23,352 KB
testcase_06 AC 93 ms
24,036 KB
testcase_07 AC 92 ms
23,616 KB
testcase_08 AC 90 ms
23,616 KB
testcase_09 AC 89 ms
23,352 KB
testcase_10 AC 94 ms
23,652 KB
testcase_11 AC 88 ms
24,000 KB
testcase_12 AC 92 ms
24,300 KB
testcase_13 AC 91 ms
24,000 KB
testcase_14 AC 94 ms
24,372 KB
testcase_15 AC 94 ms
23,364 KB
testcase_16 AC 91 ms
23,520 KB
testcase_17 AC 100 ms
24,336 KB
testcase_18 AC 92 ms
24,240 KB
testcase_19 AC 92 ms
23,616 KB
testcase_20 AC 93 ms
24,024 KB
testcase_21 AC 92 ms
24,336 KB
testcase_22 AC 89 ms
23,652 KB
testcase_23 AC 90 ms
23,388 KB
testcase_24 AC 92 ms
23,376 KB
testcase_25 AC 96 ms
24,288 KB
testcase_26 AC 91 ms
23,412 KB
testcase_27 AC 40 ms
24,240 KB
testcase_28 AC 96 ms
24,252 KB
testcase_29 AC 87 ms
24,000 KB
testcase_30 AC 86 ms
23,652 KB
testcase_31 AC 89 ms
23,652 KB
testcase_32 AC 92 ms
23,652 KB
testcase_33 AC 100 ms
24,012 KB
testcase_34 AC 99 ms
23,616 KB
testcase_35 AC 92 ms
23,400 KB
testcase_36 AC 88 ms
23,628 KB
testcase_37 AC 95 ms
23,400 KB
testcase_38 AC 93 ms
24,012 KB
testcase_39 AC 94 ms
24,000 KB
testcase_40 AC 96 ms
23,604 KB
testcase_41 AC 93 ms
23,412 KB
testcase_42 AC 94 ms
23,400 KB
testcase_43 AC 92 ms
23,400 KB
testcase_44 AC 91 ms
23,376 KB
testcase_45 AC 92 ms
23,496 KB
testcase_46 AC 91 ms
23,400 KB
testcase_47 AC 88 ms
23,364 KB
testcase_48 AC 93 ms
24,012 KB
testcase_49 AC 91 ms
24,348 KB
testcase_50 AC 92 ms
23,820 KB
testcase_51 AC 89 ms
23,628 KB
testcase_52 AC 91 ms
24,000 KB
testcase_53 AC 93 ms
24,348 KB
testcase_54 AC 93 ms
23,640 KB
testcase_55 AC 94 ms
23,616 KB
testcase_56 AC 93 ms
24,312 KB
testcase_57 AC 91 ms
23,376 KB
testcase_58 AC 92 ms
23,616 KB
testcase_59 AC 94 ms
24,360 KB
testcase_60 AC 92 ms
23,640 KB
testcase_61 AC 92 ms
23,820 KB
testcase_62 AC 91 ms
23,412 KB
testcase_63 AC 97 ms
23,376 KB
testcase_64 AC 91 ms
24,024 KB
testcase_65 AC 100 ms
23,616 KB
testcase_66 AC 94 ms
23,508 KB
testcase_67 AC 93 ms
23,808 KB
testcase_68 AC 93 ms
23,628 KB
testcase_69 AC 94 ms
24,360 KB
testcase_70 AC 94 ms
24,348 KB
testcase_71 AC 98 ms
23,364 KB
testcase_72 AC 91 ms
23,640 KB
testcase_73 AC 93 ms
23,508 KB
testcase_74 AC 89 ms
24,348 KB
testcase_75 AC 94 ms
23,376 KB
testcase_76 AC 93 ms
24,024 KB
testcase_77 AC 93 ms
24,024 KB
testcase_78 AC 91 ms
23,508 KB
testcase_79 AC 93 ms
23,832 KB
testcase_80 AC 90 ms
23,508 KB
testcase_81 AC 87 ms
23,628 KB
testcase_82 AC 95 ms
23,376 KB
testcase_83 AC 91 ms
24,312 KB
testcase_84 AC 92 ms
23,364 KB
testcase_85 AC 96 ms
24,240 KB
testcase_86 AC 96 ms
23,820 KB
testcase_87 AC 91 ms
24,012 KB
testcase_88 AC 96 ms
23,400 KB
testcase_89 AC 92 ms
23,400 KB
testcase_90 AC 90 ms
23,640 KB
testcase_91 AC 97 ms
23,508 KB
testcase_92 AC 88 ms
23,808 KB
testcase_93 AC 95 ms
23,616 KB
testcase_94 AC 89 ms
24,024 KB
testcase_95 AC 91 ms
23,496 KB
testcase_96 AC 93 ms
23,664 KB
testcase_97 AC 94 ms
24,024 KB
testcase_98 AC 88 ms
24,384 KB
testcase_99 AC 91 ms
23,616 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

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

constexpr int INF = (int)1e9;

// 敵機の情報
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;
	}
};

// 自機の情報
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(Enemy* e) {
		score += e->init_hp;
		power += e->p;
		level = 1 + power / level_up;
	}
	bool try_move(vector<vector<Enemy*>>& field ,char c) {
		if(c == 'L') {
			int nx = (x - 1 + width) % width;
			if(field[y][nx]) return false;
			else if(field[y+1][nx]) return false;
			else return true;
		}
		else if(c == 'R') {
			int nx = (x + 1) % width;
			if(field[y][nx]) return false;
			else if(field[y+1][nx]) return false;
			else return true;
		}
		else if(c == 'S') {
			if(field[y+1][x]) return false;
			return true;
		}
		else return false;
	}
	void apply_move(char c) {
		std::cout << c << std::endl;
		std::cout << "# " << c << std::endl;
		if(c == 'L') {
			x = (x - 1 + width) % width;
		}
		else if(c == 'R') {
			x = (x + 1) % width;
		}
	}
};

int main(){
	Player player(12, 0);
	vector<vector<Enemy>> enemies(max_turn + 1);
	vector field = vector(height, vector<Enemy*>(width, nullptr));

	for(int T = 1; T <= max_turn; T++) {
		// 敵機の移動
		for(int y = 0; y < height; y++) {
			for(int x = 0; x < width; x++) {
				if(!field[y][x]) continue;
				field[y][x]->y -= 1;
				if(y == 0) {
					field[y][x] = nullptr;
				}
				else {
					field[y-1][x] = field[y][x];
					field[y][x] = nullptr;
					if(y - 1 == player.y && x == player.x) {
						std::cerr << "turn = " << T << endl;
						std::cerr << "score = " << player.score << endl;
						return 0;						
					}
				}
			}
		}
		// 入力の受け取り
		int n;
		cin >> n;
		if(n == -1) return 0;
		for(int i = 0; i < n; i++) {
			int h, p, x;
			cin >> h >> p >> x;
			enemies[T].emplace_back(h, p, x);
		}
		for(auto& enemy : enemies[T]) {
			field[height-1][enemy.x] = &enemy;
		}
		// 自機の移動
		// 敵機を倒せない列には移動しない
		vector<int> invalid_line(width);
		for(int t = 1; t <= T; t++) {
			for(auto& enemy : enemies[t]) {
				if(enemy.y < 0 || enemy.h <= 0) continue;
				int dx1 = abs(enemy.x - player.x);
				int dx2 = abs(enemy.x - (player.x - width));
				int dx = max(1, min(dx1, dx2));
				int dy = enemy.y;
				int des = dx - 1 + (enemy.h + player.level - 1) / player.level;
				if(dy < des) {
					invalid_line[enemy.x] = 1;
				}
			}
		}
		// 一番早く倒せる敵を探す
		Enemy* near_enemy = nullptr;
		int min_dist = INF;
		for(int t = 1; t <= T; t++) {
			for(auto& enemy : enemies[t]) {
				if(enemy.y < 0 || enemy.h <= 0) continue;
				if(invalid_line[enemy.x]) continue;
				int dx1 = abs(enemy.x - player.x);
				int dx2 = abs(enemy.x - (player.x - width));
				int dx = min(dx1, dx2);
				int dy = enemy.y;
				int des = dx - 1 + enemy.h / player.level;

				if(des < min_dist) {
					min_dist = des;
					near_enemy = &enemy;
				}
			}
		}
		// 倒せる敵がいない場合
		if(!near_enemy) {
			if(player.try_move(field, 'S')) {
				player.apply_move('S');
			}
			else if(player.try_move(field, 'L')) {
				player.apply_move('S');
			}
			else if(player.try_move(field, 'R')) {
				player.apply_move('R');
			}
			else player.apply_move('S');
		}
		// 同列に倒せる敵がいるならとどまる
		else if(near_enemy->x == player.x) {
			player.apply_move('S');
		}
		// 敵が左にいる場合
		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(field, 'L')) {
					player.apply_move('L');
				}
				else if(player.try_move(field, 'S')) {
					player.apply_move('S');
				}
				else player.apply_move('R');
			}
			else {
				if(player.try_move(field, 'R')) {
					player.apply_move('R');
				}
				else if(player.try_move(field, 'S')) {
					player.apply_move('S');
				}
				else player.apply_move('L');
			}
		}
		// 敵が右にいる場合
		else {
			int ex = near_enemy->x, px = player.x;
			int left = px + width - ex, right = ex - px;
			if(left < right) {
				if(player.try_move(field, 'L')) {
					player.apply_move('L');
				}
				else if(player.try_move(field, 'S')) {
					player.apply_move('S');
				}
				else player.apply_move('R');
			}
			else {
				if(player.try_move(field, 'R')) {
					player.apply_move('R');
				}
				else if(player.try_move(field, 'S')) {
					player.apply_move('S');
				}
				else player.apply_move('L');
			}			
		}
		if(near_enemy) {
			cout << "# " << near_enemy->x << " " << near_enemy->y << endl;
			cout << "# hp = " << near_enemy->h << endl;
		}
		// 自機の攻撃
		int px = player.x, py = player.y + 1;
		while(py < height) {
			if(field[py][px]) {
				field[py][px]->h -= player.level;
				if(field[py][px]->h <= 0) {
					player.destroy_enemy(field[py][px]);
					field[py][px] = nullptr;
				}
				break;
			}
			py++;
		}
	}
	std::cerr << "turn = " << max_turn + 1 << endl;
	std::cerr << "score = " << player.score << endl;

	return 0;
}
0