結果
| 問題 | No.5017 Tool-assisted Shooting |
| ユーザー |
 niuez
|
| 提出日時 | 2023-07-16 16:19:20 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,879 bytes |
| コンパイル時間 | 1,634 ms |
| コンパイル使用メモリ | 115,388 KB |
| 実行使用メモリ | 24,516 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2023-07-16 16:23:10 |
| 合計ジャッジ時間 | 222,142 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | TLE | - |
| testcase_02 | TLE | - |
| testcase_03 | TLE | - |
| testcase_04 | TLE | - |
| testcase_05 | TLE | - |
| testcase_06 | TLE | - |
| testcase_07 | TLE | - |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| testcase_10 | TLE | - |
| testcase_11 | TLE | - |
| testcase_12 | TLE | - |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
| testcase_17 | TLE | - |
| testcase_18 | TLE | - |
| testcase_19 | TLE | - |
| testcase_20 | TLE | - |
| testcase_21 | TLE | - |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | TLE | - |
| testcase_25 | TLE | - |
| testcase_26 | TLE | - |
| testcase_27 | TLE | - |
| testcase_28 | TLE | - |
| testcase_29 | TLE | - |
| testcase_30 | TLE | - |
| testcase_31 | TLE | - |
| testcase_32 | TLE | - |
| testcase_33 | TLE | - |
| testcase_34 | TLE | - |
| testcase_35 | TLE | - |
| testcase_36 | TLE | - |
| testcase_37 | TLE | - |
| testcase_38 | TLE | - |
| testcase_39 | TLE | - |
| testcase_40 | TLE | - |
| testcase_41 | TLE | - |
| testcase_42 | TLE | - |
| testcase_43 | TLE | - |
| testcase_44 | TLE | - |
| testcase_45 | TLE | - |
| testcase_46 | TLE | - |
| testcase_47 | TLE | - |
| testcase_48 | TLE | - |
| testcase_49 | TLE | - |
| testcase_50 | TLE | - |
| testcase_51 | TLE | - |
| testcase_52 | TLE | - |
| testcase_53 | TLE | - |
| testcase_54 | TLE | - |
| testcase_55 | TLE | - |
| testcase_56 | TLE | - |
| testcase_57 | TLE | - |
| testcase_58 | TLE | - |
| testcase_59 | TLE | - |
| testcase_60 | TLE | - |
| testcase_61 | TLE | - |
| testcase_62 | TLE | - |
| testcase_63 | TLE | - |
| testcase_64 | TLE | - |
| testcase_65 | TLE | - |
| testcase_66 | TLE | - |
| testcase_67 | TLE | - |
| testcase_68 | TLE | - |
| testcase_69 | TLE | - |
| testcase_70 | TLE | - |
| testcase_71 | TLE | - |
| testcase_72 | TLE | - |
| testcase_73 | TLE | - |
| testcase_74 | TLE | - |
| testcase_75 | TLE | - |
| testcase_76 | TLE | - |
| testcase_77 | TLE | - |
| testcase_78 | TLE | - |
| testcase_79 | TLE | - |
| testcase_80 | TLE | - |
| testcase_81 | TLE | - |
| testcase_82 | TLE | - |
| testcase_83 | TLE | - |
| testcase_84 | TLE | - |
| testcase_85 | TLE | - |
| testcase_86 | TLE | - |
| testcase_87 | TLE | - |
| testcase_88 | TLE | - |
| testcase_89 | TLE | - |
| testcase_90 | TLE | - |
| testcase_91 | TLE | - |
| testcase_92 | TLE | - |
| testcase_93 | TLE | - |
| testcase_94 | TLE | - |
| testcase_95 | TLE | - |
| testcase_96 | TLE | - |
| testcase_97 | TLE | - |
| testcase_98 | TLE | - |
| testcase_99 | TLE | - |
ソースコード
#include <iostream>
#include <cassert>
#include <vector>
#include <cstdint>
#include <numeric>
#include <chrono>
#include <bitset>
#include <tuple>
#include <algorithm>
using i64 = long long;
struct Timer {
std::chrono::high_resolution_clock::time_point st;
Timer() { st = now(); }
std::chrono::high_resolution_clock::time_point now() { return std::chrono::high_resolution_clock::now(); }
std::chrono::milliseconds::rep span() {
auto ed = now();
return std::chrono::duration_cast<std::chrono::milliseconds>(ed - st).count();
}
};
struct Xor64 {
using state_type = std::uint64_t;
using result_type = std::uint64_t;
state_type a;
static constexpr result_type min() {
return std::numeric_limits<result_type>::min();
}
static constexpr result_type max() {
return std::numeric_limits<result_type>::max();
}
constexpr Xor64(state_type seed = 88675123): a(seed) {}
constexpr void seed(state_type seed = 88675123) {
a = seed;
}
constexpr result_type operator()() {
a ^= a << 7;
a ^= a >> 9;
return a;
}
void discard(unsigned long long z) {
while(z --> 0) {
(*this)();
}
}
};
struct Enemy {
int x = -1;
int power = -1;
int score = -1;
int hp = -1;
inline bool exist() { return hp >= 1; }
};
struct Action {
int act;
int attack_y = -1;
};
struct State {
const int X = 25;
const int Y = 60;
const int H = 1000;
int turn = 0;
int x = 12;
int power_sum = 0;
i64 score = 0;
std::vector<std::vector<Enemy>> field;
State() {
field.resize(X, std::vector<Enemy>(H + Y + 100));
}
int level() const {
return 1 + power_sum / 100;
}
Action forward(int act, const std::vector<Enemy>& new_enemies) {
x = (x + act + X) % X;
if(field[x][turn].exist()) {
score -= 1e8;
}
Action action = Action { .act = act };
for(int y = turn; y < turn + Y; y++) {
if(field[x][y].exist()) {
int dmg = level();
score += std::min(field[x][y].hp, dmg);
field[x][y].hp -= dmg;
if(!field[x][y].exist()) {
//score += field[x][y].score;
power_sum += field[x][y].power;
}
action = Action { .act = act, .attack_y = y };
break;
}
}
turn++;
if(field[x][turn].exist()) {
score -= 1e8;
}
for(auto e: new_enemies) {
field[e.x][turn + Y - 1] = e;
}
return action;
}
void backward(const Action& act) {
if(field[x][turn].exist()) {
score += 1e8;
}
turn--;
if(act.attack_y != -1) {
if(!field[x][act.attack_y].exist()) {
//score -= field[x][act.attack_y].score;
power_sum -= field[x][act.attack_y].power;
}
int dmg = level();
field[x][act.attack_y].hp += dmg;
score -= std::min(field[x][act.attack_y].hp, dmg);
}
if(field[x][turn].exist()) {
score += 1e8;
}
x = (x - act.act + X) % X;
}
};
struct EulerTourEdge {
bool is_down;
bool is_leaf;
Action act;
i64 score;
int id;
};
struct EulerTourTree {
std::vector<EulerTourEdge> edges;
std::vector<std::tuple<i64, int, int>> leaf_scores;
};
i64 sol_score = 0;
i64 sol_act = 0;
std::vector<Enemy> empty_enemies;
const int FLAG_LENGTH = 3 * 25 * 25;
using flagset = std::bitset<FLAG_LENGTH>;
void extend_euler_tree(const State& init_state, const EulerTourTree& cur_tree, EulerTourTree& next_tree, const flagset& flag) {
//std::cerr << "---" << std::endl;
State state = init_state;
int ids = 0;
std::vector<Action> down_actions;
int downed = 0;
for(int ei = 0; ei < cur_tree.edges.size(); ei++) {
auto& e = cur_tree.edges[ei];
//std::cerr << e.is_down << " " << e.is_leaf << " " << " " << e.action << " " << e.score << std::endl;
if(e.is_down) {
down_actions.push_back(e.act);
state.forward(e.act.act, empty_enemies);
{
int score = state.score;
if(sol_score < score) {
sol_score = score;
sol_act = down_actions.front().act;
}
}
}
else { // up
if(e.is_leaf /* && !state.is_done() */ && flag.test(e.id)) {
for(int dir = -1; dir <= 1; dir++) {
{
// completion edge for new leaf
for(; downed < down_actions.size(); downed++) {
next_tree.edges.push_back( EulerTourEdge {
.is_down = true,
.is_leaf = false,
.act = down_actions[downed],
.score = 0,
});
}
auto act = state.forward(dir, empty_enemies);
i64 score = state.score;
next_tree.edges.push_back( EulerTourEdge {
.is_down = true,
.is_leaf = false,
.act = act,
.score = 0,
});
next_tree.edges.push_back( EulerTourEdge {
.is_down = false,
.is_leaf = true,
.act = {},
.score = score,
.id = ids++,
});
next_tree.leaf_scores.push_back({ score, ids - 1, state.x});
state.backward(act);
}
}
}
if(down_actions.empty()) {
next_tree.edges.push_back( EulerTourEdge {
.is_down = false,
.is_leaf = false,
.act = {},
.score = 0,
});
return;
}
state.backward(down_actions.back());
if(downed == down_actions.size()) {
next_tree.edges.push_back( EulerTourEdge {
.is_down = false,
.is_leaf = false,
.act = {},
.score = 0,
});
downed--;
}
down_actions.pop_back();
}
}
}
int beam_search(const State& init_state) {
const int beam_width = 50;
EulerTourTree cur_tree;
EulerTourTree next_tree;
sol_score = -1e9;
sol_act = -2;
cur_tree.edges.push_back( EulerTourEdge {
.is_down = 0,
.is_leaf = 1,
.act = {},
.score = init_state.score,
.id = 0,
});
cur_tree.leaf_scores.push_back({ init_state.score, 0, init_state.x});
std::vector<int> cnt(25);
for(int depth = 0; depth < 25; depth++) {
auto& score = cur_tree.leaf_scores;
int w = std::min(beam_width, (int)score.size());
std::sort(score.begin(), score.end(), std::greater<std::tuple<int, int, int>>());
//std::cerr << depth << " " << std::get<0>(score[0]) << " " << std::get<0>(score.back()) << std::endl;
next_tree.edges.clear();
next_tree.leaf_scores.clear();
flagset flag;
std::fill(cnt.begin(), cnt.end(), 0);
for(int i = 0; i < score.size(); i++) {
auto& [s, id, x] = score[i];
if(cnt[x]++ < 2) {
flag.set(id);
}
}
extend_euler_tree(init_state, cur_tree, next_tree, flag);
std::swap(cur_tree, next_tree);
}
return sol_act;
}
char act_to_char(int act) {
static char ac[] = "LSR";
return ac[act + 1];
}
void solve() {
const int T = 1000;
State init_state;
int before_act = 0;
for(int t = 0; t < T; t++) {
int N;
std::cin >> N;
if(N == -1) {
return;
}
std::vector<Enemy> es(N);
for(int i = 0; i < N; i++) {
std::cin >> es[i].hp >> es[i].power >> es[i].x;
es[i].score = es[i].hp;
}
init_state.forward(before_act, es);
int act = beam_search(init_state);
//std::cerr << act << " " << init_state.score << " " << init_state.x << std::endl;
before_act = act;
/*
for(int x = 0; x < 25; x++) {
std::cerr << x << ":\t";
for(int y = init_state.turn; y < init_state.turn + 60; y++) {
std::cerr << init_state.field[x][y].exist();
}
std::cerr << std::endl;
}
if(init_state.score < 0) {
return;
}
*/
std::cerr << init_state.score << std::endl;
std::cout << act_to_char(act) << std::endl;
}
}
int main() {
solve();
Xor64 mt(786);
}