#define _USE_MATH_DEFINES #pragma GCC target("avx2") #pragma GCC optimize("O3") #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include 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(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 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::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{ 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 { public: size_t operator()(const Hash& data)const { return hash()(data.val); } }; } struct HashSpace { static vector hashVal; static bool isFirstInit; int Sx = X_SIZE*3; HashSpace() { if (isFirstInit) { vector pw[1]; Hash basis[1]; pw[0] = { vector(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 HashSpace::hashVal; bool HashSpace::isFirstInit = 1; struct State { vector>> enemy_table; int power; static HashSpace t; Hash myHash; int myScore; int x; int turn; // 初期状態の生成 State(vector>>& 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 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 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,queue>>> apply(ull op) { x += dx[op]; int bp = power; queue < pair>> 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, queue>>> 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 parent; int score; Hash hash; ull p; // 優先度(複数もたせたほうがいい場合があるかもしれない。) }; using Parent = optional>>; using Children = vector>>; 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; ull rank; // 注意: depthは深くなっていくごとに-1されていく void dfs(vector& 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>& 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, queue>>> 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>>& enemy_table,int x,int turn,int power) { constexpr ull TURN = 30; constexpr ull M = 25; // ビーム幅 State state(enemy_table, power, x,turn); ull score = state.score(); Hash hash = state.hash(); Tree tree{ move(state),shared_ptr(new Node(Parent(),Children(),score,hash)),0 }; vector> cur{ tree.node }; vector next_states; // cerr << state.x << "\n"; unordered_set 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(new Node(Parent({ op,parent }), Children(), next_score, next_hash)); parent->child.emplace_back(op, weak_ptr(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 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>> 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>> 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 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 <> n; } return 0; }