結果

問題 No.5017 Tool-assisted Shooting
ユーザー PechiPechi
提出日時 2023-07-16 21:58:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,703 ms / 2,000 ms
コード長 14,201 bytes
コンパイル時間 6,465 ms
コンパイル使用メモリ 283,440 KB
実行使用メモリ 24,420 KB
スコア 4,262,907
平均クエリ数 980.00
最終ジャッジ日時 2023-07-16 22:01:32
合計ジャッジ時間 170,769 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,560 ms
24,000 KB
testcase_01 AC 1,660 ms
24,072 KB
testcase_02 AC 1,445 ms
23,700 KB
testcase_03 AC 1,548 ms
23,652 KB
testcase_04 AC 1,486 ms
23,448 KB
testcase_05 AC 1,503 ms
24,024 KB
testcase_06 AC 1,547 ms
23,580 KB
testcase_07 AC 1,582 ms
24,012 KB
testcase_08 AC 1,514 ms
23,652 KB
testcase_09 AC 1,533 ms
23,436 KB
testcase_10 AC 1,581 ms
24,036 KB
testcase_11 AC 1,503 ms
23,652 KB
testcase_12 AC 1,554 ms
23,412 KB
testcase_13 AC 1,592 ms
23,568 KB
testcase_14 AC 1,605 ms
23,700 KB
testcase_15 AC 1,592 ms
23,400 KB
testcase_16 AC 1,560 ms
23,568 KB
testcase_17 AC 1,616 ms
23,424 KB
testcase_18 AC 1,572 ms
23,388 KB
testcase_19 AC 1,609 ms
23,424 KB
testcase_20 AC 1,607 ms
23,652 KB
testcase_21 AC 1,624 ms
24,372 KB
testcase_22 AC 1,479 ms
23,832 KB
testcase_23 AC 1,553 ms
23,436 KB
testcase_24 AC 1,653 ms
23,676 KB
testcase_25 AC 1,615 ms
24,000 KB
testcase_26 AC 1,622 ms
24,024 KB
testcase_27 AC 1,532 ms
23,832 KB
testcase_28 AC 1,679 ms
23,400 KB
testcase_29 AC 1,457 ms
23,664 KB
testcase_30 AC 1,470 ms
23,820 KB
testcase_31 AC 1,525 ms
24,024 KB
testcase_32 AC 1,604 ms
24,396 KB
testcase_33 AC 1,666 ms
23,652 KB
testcase_34 AC 1,608 ms
24,360 KB
testcase_35 AC 1,578 ms
23,832 KB
testcase_36 AC 1,520 ms
23,376 KB
testcase_37 AC 1,629 ms
24,216 KB
testcase_38 AC 1,568 ms
23,688 KB
testcase_39 AC 1,578 ms
23,412 KB
testcase_40 AC 1,630 ms
23,436 KB
testcase_41 AC 1,542 ms
23,580 KB
testcase_42 AC 1,639 ms
24,000 KB
testcase_43 AC 1,588 ms
23,556 KB
testcase_44 AC 1,596 ms
24,000 KB
testcase_45 AC 1,583 ms
23,412 KB
testcase_46 AC 1,650 ms
23,556 KB
testcase_47 AC 1,472 ms
23,664 KB
testcase_48 AC 1,613 ms
24,228 KB
testcase_49 AC 1,534 ms
24,024 KB
testcase_50 AC 1,613 ms
24,216 KB
testcase_51 AC 1,618 ms
23,568 KB
testcase_52 AC 1,611 ms
23,400 KB
testcase_53 AC 1,572 ms
23,832 KB
testcase_54 AC 1,627 ms
23,400 KB
testcase_55 AC 1,552 ms
24,396 KB
testcase_56 AC 1,582 ms
24,228 KB
testcase_57 AC 1,497 ms
23,556 KB
testcase_58 AC 1,558 ms
24,012 KB
testcase_59 AC 1,609 ms
23,556 KB
testcase_60 AC 1,534 ms
23,412 KB
testcase_61 AC 1,544 ms
23,664 KB
testcase_62 AC 1,521 ms
23,400 KB
testcase_63 AC 1,591 ms
24,324 KB
testcase_64 AC 1,563 ms
23,556 KB
testcase_65 AC 1,703 ms
23,832 KB
testcase_66 AC 1,645 ms
23,544 KB
testcase_67 AC 1,574 ms
23,640 KB
testcase_68 AC 1,587 ms
23,664 KB
testcase_69 AC 1,550 ms
24,420 KB
testcase_70 AC 1,561 ms
23,412 KB
testcase_71 AC 1,610 ms
23,676 KB
testcase_72 AC 1,466 ms
23,424 KB
testcase_73 AC 1,636 ms
23,820 KB
testcase_74 AC 1,486 ms
23,556 KB
testcase_75 AC 1,565 ms
24,048 KB
testcase_76 AC 1,618 ms
23,400 KB
testcase_77 AC 1,629 ms
24,384 KB
testcase_78 AC 1,628 ms
24,000 KB
testcase_79 AC 1,584 ms
23,592 KB
testcase_80 AC 1,614 ms
24,372 KB
testcase_81 AC 1,549 ms
23,628 KB
testcase_82 AC 1,558 ms
23,676 KB
testcase_83 AC 1,514 ms
23,640 KB
testcase_84 AC 1,595 ms
23,640 KB
testcase_85 AC 1,627 ms
24,024 KB
testcase_86 AC 1,596 ms
23,424 KB
testcase_87 AC 1,604 ms
24,216 KB
testcase_88 AC 1,589 ms
23,652 KB
testcase_89 AC 1,609 ms
23,640 KB
testcase_90 AC 1,587 ms
23,808 KB
testcase_91 AC 1,641 ms
23,388 KB
testcase_92 AC 1,497 ms
23,820 KB
testcase_93 AC 1,557 ms
23,424 KB
testcase_94 AC 1,512 ms
23,628 KB
testcase_95 AC 1,606 ms
23,412 KB
testcase_96 AC 1,557 ms
23,988 KB
testcase_97 AC 1,588 ms
23,424 KB
testcase_98 AC 1,532 ms
23,580 KB
testcase_99 AC 1,657 ms
23,424 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<optional>
#include<random>
#include <array>
#include <complex>
#include<chrono>

using namespace std;
#define LP(I,S,G) for (long long int I = (S); I < (G); ++I)
#define IN(X) 	for (int in = 0; in < X.size(); in++)cin >> X[in]
#define OUT(X) 	for (int in = 0; in < X.size(); in++)cout << X[in]<<" "
#define SORT(X) sort((X).begin(), (X).end())
#define CSORT(X,Y) sort(X.begin(), X.end(),Y)
#define COPY(X,Y) copy(X.begin(), X.end(), Y.begin())
#define ALL(X,Y) for (auto X = (Y).begin(); X != (Y).end(); X++)
#define FULL(a)  (a).begin(),(a).end()
#define BFS(Q,S) for(Q.push(S);Q.size()!=0;Q.pop())
typedef long long int ll;
typedef unsigned long long int ull;

chrono::system_clock::time_point starttime;
using namespace std::chrono;

inline float getTime() {
	return duration_cast<milliseconds>(system_clock::now() - starttime).count();
}

bool phase = 0;
int dx[] = { -1,0,1 };

ll MAX(ll A, ll B) { return ((A) > (B) ? (A) : (B)); }
ll MIN(ll A, ll B) { return ((A) < (B) ? (A) : (B)); }
inline long long int xor128() {
	static long long int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	long long int t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

#define X_SIZE 25
#define MAX_TURN 1000

vector<ll> enemy_count(X_SIZE, 0);
mt19937_64 rnd;

using namespace std;

using ull = unsigned long long;

//https://nyaannyaan.github.io/library/inner/inner-hash.hpp
struct Hash {
	ull val;
	static constexpr ull M = (1ull << 61) - 1;

	Hash() {}
	static Hash set(const ll& a) {
		Hash res;
		res.val = cast(a);
		return res;
	}
	Hash& operator+=(const Hash& r) {
		if (((*this).val += r.val) >= M) (*this).val -= M;
		return *this;
	}
	Hash& operator+=(const ll& r) {
		ull s = cast(r);
		if (((*this).val += s) >= M) (*this).val -= M;
		return *this;
	}
	Hash& operator-=(const Hash& r) {
		if (((*this).val += M - r.val) >= M) (*this).val -= M;
		return *this;
	}
	Hash& operator-=(const ll& r) {
		ull s = cast(r);
		if (((*this).val += M - s) >= M) (*this).val -= M;
		return *this;
	}
	Hash& operator*=(const Hash& r) {
		(*this).val = modmul((*this).val, r.val);
		return *this;
	}
	Hash& operator*=(const ll& r) {
		ull s = cast(r);
		(*this).val = modmul((*this).val, s);
		return *this;
	}
	bool operator==(const Hash& r) const { return (*this).val == r.val; }
	Hash operator+(const Hash& r) { return Hash(*this) += r; }
	Hash operator+(const ll& r) { return Hash(*this) += r; }
	Hash operator-(const Hash& r) { return Hash(*this) -= r; }
	Hash operator-(const ll& r) { return Hash(*this) -= r; }
	Hash operator*(const Hash& r) { return Hash(*this) *= r; }
	Hash operator*(const ll& r) { return Hash(*this) *= r; }
	Hash operator-() const {
		Hash res;
		res.val = (*this).val == 0 ? 0 : M - (*this).val;
		return res;
	}

	Hash pow(long long e) {
		Hash a{ *this }, res{ Hash::set(1) };
		for (; e; a *= a, e >>= 1) {
			if (e & 1) res *= a;
		}
		return res;
	}

	static Hash get_basis() {
		static auto rand_time =
			chrono::duration_cast<chrono::nanoseconds>(
				chrono::high_resolution_clock::now().time_since_epoch())
			.count();
		static mt19937_64 rng(rand_time);
		Hash h;
		while (isPrimitive(h.val = rng() % (M - 1) + 1) == false)
			;
		return h;
	}

private:
	static constexpr ull MASK30 = (1ull << 30) - 1;
	static constexpr ull MASK31 = (1ull << 31) - 1;
	static constexpr ull MASK61 = M;
	static inline ull CalcMod(ull x) {
		ull xu = x >> 61;
		ull xd = x & MASK61;
		ull res = xu + xd;
		if (res >= M) res -= M;
		return res;
	}
	static ull modpow(ull a, ull b) {
		ull r = 1;
		for (a = CalcMod(a); b; a = modmul(a, a), b >>= 1) r = modmul(r, a);
		return r;
	}
	static bool isPrimitive(ull x) {
		for (auto& d : vector<ull>{ 2, 3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321 })
			if (modpow(x, (M - 1) / d) <= 1) return false;
		return true;
	}
	static inline constexpr ull cast(const long long& a) {
		return a < 0 ? a + M : a;
	}

	static inline ull modmul(const ull& a, const ull& b) {
		ull au = a >> 31;
		ull ad = a & MASK31;
		ull bu = b >> 31;
		ull bd = b & MASK31;
		ull mid = ad * bu + au * bd;
		ull midu = mid >> 30;
		ull midd = mid & MASK30;
		return CalcMod(au * bu * 2 + midu + (midd << 31) + ad * bd);
	}
};

namespace std {
	template<>
	struct hash<Hash> {
	public:
		size_t operator()(const Hash& data)const {
			return hash<ull>()(data.val);
		}
	};
}

struct HashSpace {
	static vector <Hash> hashVal;
	static bool isFirstInit;
	int Sx = X_SIZE * 3;
	HashSpace() {
		if (isFirstInit) {
			vector<Hash> pw[1];
			Hash basis[1];
			pw[0] = { vector<Hash>(Sx + 1) };
			basis[0] = Hash::get_basis();
			isFirstInit = 0;
			pw[0][0] = Hash::set(1);
			for (int i = 1; i <= Sx; i++) pw[0][i] = pw[0][i - 1] * basis[0];
			hashVal = pw[0];
		}
	}

};

vector<Hash> HashSpace::hashVal;
bool HashSpace::isFirstInit = 1;


struct State {
	vector<deque<array<int, 4>>> enemy_table;
	int power;
	static HashSpace t;
	Hash myHash;
	int myScore;
	int x;
	int turn;
	// 初期状態の生成
	State(vector<deque<array<int, 4>>>& in_e, int in_p, int in_x, int in_t) :enemy_table(in_e) {
		power = in_p;
		myScore = 0;
		if (!phase)myScore = power;
		x = in_x;
		turn = in_t;
		for (int i = 0; i < X_SIZE; ++i) {
			if (enemy_table[i].size() != 0)myHash += t.hashVal[i * 3] * enemy_table[i].front()[0] + t.hashVal[i * 3 + 1] * enemy_table[i].front()[1] + t.hashVal[i * 3 + 2] * enemy_table[i].front()[3];
		}
		myHash += x;
	}

	int score() {
		return myScore;
	}

	Hash hash() {
		return myHash;
	}

	Hash update_hash(int x) {
		Hash ret = Hash::set(0);
		ret -= t.hashVal[x * 3] * enemy_table[x].front()[0] + t.hashVal[x * 3 + 1] * enemy_table[x].front()[1] + t.hashVal[x * 3 + 2] * enemy_table[x].front()[3];
		array<int, 4> note = enemy_table[x].front();
		enemy_table[x].pop_front();
		if (enemy_table[x].size() != 0)ret += t.hashVal[x * 3] * enemy_table[x].front()[0] + t.hashVal[x * 3 + 1] * enemy_table[x].front()[1] + t.hashVal[x * 3 + 2] * enemy_table[x].front()[3];
		enemy_table[x].push_front(note);
		return ret;
	}

	// スコアとハッシュの差分計算
	// 状態は更新しない
	pair<int, Hash> try_apply(ull op, ull score, Hash hash) {
		x=(x+X_SIZE+dx[op])%X_SIZE;
		hash += dx[op];
		if (enemy_table[x].size() != 0) {
			if (enemy_table[x].front()[0] <= turn + 2) {
				x=(x+X_SIZE-dx[op])%X_SIZE;
				return { -10000,Hash::set(0) };
			}
			if (enemy_table[x].front()[1] - (1 + power / 100) <= 0) {
				if (phase)score += enemy_table[x].front()[3] * 10000;
				else score += enemy_table[x].front()[2] * 10000;
				hash += update_hash(x);
			}
			else {
				hash -= t.hashVal[x * 3 + 1] * (1 + power / 100);
				score += enemy_table[x].front()[2] - (enemy_table[x].front()[1] - (1 + power / 100));
			}
		}
		for (int i = 0; i < 25; ++i) {
			if (enemy_table[i].size() == 0)continue;
			if (enemy_table[i].front()[0] == turn) {
				hash += update_hash(i);
			}
		}
		x=(x+X_SIZE-dx[op])%X_SIZE;
		return { score,hash };
	}

	// 状態を更新する
	// 元の状態に戻すための情報を返す
	pair<pair<int, int>, queue<pair<int, array<int, 4>>>> apply(ull op) {
		x=(x+X_SIZE+dx[op])%X_SIZE;
		int bp = power;
		queue < pair<int, array<int, 4>>> backup;
		if (enemy_table[x].size() != 0) {
			if (enemy_table[x].front()[0] <= turn + 2) {
				++turn;
				return { {op,0},{} };
			}
			enemy_table[x].front()[1] -= (1 + power / 100);
			if (enemy_table[x].front()[1] <= 0) {
				power += enemy_table[x].front()[3];
				backup.push({ x,enemy_table[x].front() });
				enemy_table[x].pop_front();
			}
		}
		for (int i = 0; i < X_SIZE; ++i) {
			if (enemy_table[i].size() == 0)continue;
			if (enemy_table[i].front()[0] == turn) {
				backup.push({ i,enemy_table[i].front() });
				enemy_table[i].pop_front();
			}
		}
		++turn;
		return { {op,bp},backup };
	}

	// applyから返された情報をもとに状態を元に戻す
	ull back(pair<pair<int, int>, queue<pair<int, array<int, 4>>>> backup) {
		power = backup.first.second;
		--turn;
		while (backup.second.size() != 0) {
			int i = backup.second.front().first;
			enemy_table[i].push_front(backup.second.front().second);
			backup.second.pop();
		}
		if (enemy_table[x].size() != 0) enemy_table[x].front()[1] += (1 + power / 100);
		x = (x+X_SIZE-dx[backup.first.first])%X_SIZE;
		return backup.first.first;
	}
};

HashSpace State::t;

struct Node;

struct Kouho {
	ull op;
	shared_ptr<Node> parent;
	int score;
	Hash hash;
	ull p; // 優先度(複数もたせたほうがいい場合があるかもしれない。)
};

using Parent = optional<pair<ull, shared_ptr<Node>>>;
using Children = vector<pair<ull, weak_ptr<Node>>>;

struct Node {
	Parent parent; // 操作、親への参照
	Children child; // 操作、子への参照
	int score;
	Hash hash;

	Node(Parent parent, Children child, ull score, Hash hash) :
		parent(parent), child(child), score(score), hash(hash) {}
};


// 多スタート用に構造体にまとめておくと楽
struct Tree {
	State state;
	shared_ptr<Node> node;
	ull rank;

	// 注意: depthは深くなっていくごとに-1されていく
	void dfs(vector<Kouho>& next_states, bool one, ull& p, ull depth) {
		if (depth == 0) {
			ull score = node->score;
			Hash hash = node->hash;

			// 検算
			// assert(score==state.score());
			// assert(hash==state.hash());

			// 次の操作を列挙
			for (ull op = 0; op < 3; ++op) {
				int nx = state.x + dx[op];
				auto[next_score, next_hash] = state.try_apply(op, score, hash);
				if (next_score >= 0) {
					next_states.emplace_back(Kouho{ op,node,next_score,next_hash,p });

					p += 1;
				}
			}
		}
		else {
			auto node_backup = node;
			auto child = &node_backup->child;
			// 有効な子だけにする
			child->erase(remove_if(child->begin(), child->end(), [](pair<ull, weak_ptr<Node>>& x) {return x.second.expired(); }), child->end());

			bool next_one = one & child->size() == 1;

			// 定数調整の必要あり
			if (depth == 5) {
				p = 0;
			}
			++rank;

			for (const auto&[op, ptr] : *child) {
				node = ptr.lock();
				pair<pair<int, int>, queue<pair<int, array<int, 4>>>> backup = state.apply(op);
				dfs(next_states, next_one, p, depth - 1);

				if (!next_one) {
					state.back(backup);
				}
			}

			if (!next_one) {
				node = node_backup;
				--rank;
			}
		}
	}
};

int beam(vector<deque<array<int, 4>>>& enemy_table, int x, int turn, int power) {
	constexpr ull TURN = 30;
	constexpr ull M = 40; // ビーム幅

	State state(enemy_table, power, x, turn);
	ull score = state.score();
	Hash hash = state.hash();

	Tree tree{ move(state),shared_ptr<Node>(new Node(Parent(),Children(),score,hash)),0 };

	vector<shared_ptr<Node>> cur{ tree.node };
	vector<Kouho> next_states;
	//	cerr << state.x << "\n";
	unordered_set<Hash> set;
	for (ull i = 0; i < TURN; ++i) {
		next_states.clear();
		ull tmp = 0;
		tree.dfs(next_states, true, tmp, i - tree.rank);
		if (i + 1 != TURN) {
			// 上位M個を残す
			if (next_states.size() > M) {
				nth_element(next_states.begin(), next_states.begin() + M, next_states.end(), [](Kouho& a, Kouho& b) {
					if (a.score == b.score) {
						return a.p > b.p;
					}
					else {
						return a.score > b.score;
					}
					});
				next_states.erase(next_states.begin() + M, next_states.end());
			}

			cur.clear();
			set.clear();
			for (const auto&[op, parent, next_score, next_hash, p] : next_states) {
				// 重複除去
				if (set.count(next_hash) == 0) {
					set.insert(next_hash);
					auto child_ptr = shared_ptr<Node>(new Node(Parent({ op,parent }), Children(), next_score, next_hash));
					parent->child.emplace_back(op, weak_ptr<Node>(child_ptr));
					cur.emplace_back(child_ptr);
				}
			}
		}
	}

	// 最良の状態を選択
	ull arg_max = -1;
	ull max = 0;
	if (next_states.size() == 0)return 1;
	for (ull i = 0; i < next_states.size(); ++i) {
		if (next_states[i].score >= max) {
			max = next_states[i].score;
			arg_max = i;
		}
	}
	auto[op, ptr, best_score, _, __] = next_states[arg_max];

	vector<ull> ret{ op };
	//	cerr << "score: " << best_score<<" ";
	//	cerr << "rank: " << TURN - tree.rank << endl;

		// 操作の復元
	while (ptr->parent.has_value()) {
		auto[op, parent] = ptr->parent.value();
		ret.emplace_back(op);
		ptr = parent;
	}

	reverse(ret.begin(), ret.end());
	return ret[0];
}

int simulate(int x, int power, int turn, vector<deque<array<int, 4>>> enemy_table) {
	/*	for (int i = turn + 1; i < MIN(turn + TURN, 1060); ++i) {
			normal_distribution<> dist_h(7.7 + 0.15*i, 1.5 + 0.03*i);
			for (int k = 0; k < 25; ++k) {
				if (xor128() % 10000 < MAX(100, MIN(800, enemy_count[k] * 10000 / (turn+1)))) {
					int h = MAX(1, (int)dist_h(rnd));
					normal_distribution<> dist_p(0.8*h, 0.1*h);
					int p= MAX(0, (int)dist_p(rnd));
					enemy_table[k].push_back({ i,h,p });
				}
			}
		}
	*/
	return beam(enemy_table, x, turn, power);
}


int main() {
	int n, turn = 0, x = 12, power = 0;
	cin >> n;
	vector<deque<array<int, 4>>> enemy_table(25);
	string move = "LSR";
	while (n != -1) {
//		cerr << n << endl;
		if (power >= 99900)phase = 1;
		for (int i = 0; i < n; ++i) {
			int h, p, ix;
			cin >> h >> p >> ix;
			enemy_table[ix].push_back({ turn + 60,h,h, p });
		}
		vector<int> cnt(3, 0);
		for (int i = 0; i < 1; ++i)++cnt[simulate(x, power, turn, enemy_table)];
		int max_id = 0;
		for (int i = 0; i < 3; ++i)if (cnt[i] > cnt[max_id])max_id = i;
		x = (x + X_SIZE + dx[max_id]) % X_SIZE;
		if (enemy_table[x].size() != 0) {
			enemy_table[x].front()[1] -= (1 + power / 100);
			if (enemy_table[x].front()[1] <= 0) {
				power += enemy_table[x].front()[3];
				enemy_table[x].pop_front();
			}
		}
		//		cerr << turn << "\t:";
		for (int i = 0; i < X_SIZE; ++i) {
			if (enemy_table[i].size() == 0) {
				//				cerr << "- ";
				continue;
			}
			//			cerr << enemy_table[i].front()[0] - turn << " ";
			if (enemy_table[i].front()[0] == turn) {
				enemy_table[i].pop_front();
			}
		}
		//		cerr <<power<< "\n";
		cout << move[max_id] << endl;
		++turn;
		if (turn == 1000)break;
		cin >> n;
	}
	return 0;
}
0