結果

問題 No.5017 Tool-assisted Shooting
ユーザー PechiPechi
提出日時 2023-07-16 18:47:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 14,056 bytes
コンパイル時間 5,494 ms
コンパイル使用メモリ 284,016 KB
実行使用メモリ 35,304 KB
スコア 0
最終ジャッジ日時 2023-07-16 18:48:01
合計ジャッジ時間 12,000 ms
ジャッジサーバーID
(参考情報)
judge11 / judge13
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
testcase_55 -- -
testcase_56 -- -
testcase_57 -- -
testcase_58 -- -
testcase_59 -- -
testcase_60 -- -
testcase_61 -- -
testcase_62 -- -
testcase_63 -- -
testcase_64 -- -
testcase_65 -- -
testcase_66 -- -
testcase_67 -- -
testcase_68 -- -
testcase_69 -- -
testcase_70 -- -
testcase_71 -- -
testcase_72 -- -
testcase_73 -- -
testcase_74 -- -
testcase_75 -- -
testcase_76 -- -
testcase_77 -- -
testcase_78 -- -
testcase_79 -- -
testcase_80 -- -
testcase_81 -- -
testcase_82 -- -
testcase_83 -- -
testcase_84 -- -
testcase_85 -- -
testcase_86 -- -
testcase_87 -- -
testcase_88 -- -
testcase_89 -- -
testcase_90 -- -
testcase_91 -- -
testcase_92 -- -
testcase_93 -- -
testcase_94 -- -
testcase_95 -- -
testcase_96 -- -
testcase_97 -- -
testcase_98 -- -
testcase_99 -- -
権限があれば一括ダウンロードができます

ソースコード

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;
long long int M = 998244353;

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 += dx[op];
		hash += dx[op];
		if (enemy_table[x].size() != 0) {
			if (enemy_table[x].front()[0] <= turn+2) {
				x -= dx[op];
				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 -= dx[op];
		return { score,hash };
	}

	// 状態を更新する
	// 元の状態に戻すための情報を返す
	pair<pair<int,int>,queue<pair<int,array<int,4>>>> apply(ull op) {
		x += dx[op];
		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 -= dx[backup.first.first];
		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];
				if (nx < 0 || nx >= X_SIZE)continue;
				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 = 60;
	constexpr ull M = 50; // ビーム幅

	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;
	assert(next_states.size() != 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) {
		if (turn >= 500)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 += dx[max_id];
		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;
		cin >> n;
	}
	return 0;
}
0