結果
| 問題 | No.5017 Tool-assisted Shooting |
| ユーザー |
 Pechi
|
| 提出日時 | 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 | -- | - |
ソースコード
#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;
}