結果
| 問題 | No.5017 Tool-assisted Shooting |
| ユーザー |
 niuez
|
| 提出日時 | 2023-07-16 15:41:51 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,122 bytes |
| コンパイル時間 | 1,294 ms |
| コンパイル使用メモリ | 106,168 KB |
| 実行使用メモリ | 24,504 KB |
| スコア | 72 |
| 平均クエリ数 | 72.33 |
| 最終ジャッジ日時 | 2023-07-16 15:42:35 |
| 合計ジャッジ時間 | 38,027 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
| testcase_27 | RE | - |
| testcase_28 | RE | - |
| testcase_29 | RE | - |
| testcase_30 | RE | - |
| testcase_31 | RE | - |
| testcase_32 | RE | - |
| testcase_33 | RE | - |
| testcase_34 | RE | - |
| testcase_35 | RE | - |
| testcase_36 | RE | - |
| testcase_37 | RE | - |
| testcase_38 | RE | - |
| testcase_39 | RE | - |
| testcase_40 | RE | - |
| testcase_41 | RE | - |
| testcase_42 | RE | - |
| testcase_43 | RE | - |
| testcase_44 | RE | - |
| testcase_45 | RE | - |
| testcase_46 | RE | - |
| testcase_47 | RE | - |
| testcase_48 | RE | - |
| testcase_49 | RE | - |
| testcase_50 | RE | - |
| testcase_51 | RE | - |
| testcase_52 | RE | - |
| testcase_53 | RE | - |
| testcase_54 | RE | - |
| testcase_55 | RE | - |
| testcase_56 | RE | - |
| testcase_57 | RE | - |
| testcase_58 | RE | - |
| testcase_59 | RE | - |
| testcase_60 | RE | - |
| testcase_61 | RE | - |
| testcase_62 | RE | - |
| testcase_63 | RE | - |
| testcase_64 | RE | - |
| testcase_65 | RE | - |
| testcase_66 | RE | - |
| testcase_67 | RE | - |
| testcase_68 | RE | - |
| testcase_69 | RE | - |
| testcase_70 | RE | - |
| testcase_71 | RE | - |
| testcase_72 | RE | - |
| testcase_73 | RE | - |
| testcase_74 | RE | - |
| testcase_75 | RE | - |
| testcase_76 | RE | - |
| testcase_77 | RE | - |
| testcase_78 | RE | - |
| testcase_79 | RE | - |
| testcase_80 | RE | - |
| testcase_81 | RE | - |
| testcase_82 | RE | - |
| testcase_83 | RE | - |
| testcase_84 | RE | - |
| testcase_85 | RE | - |
| testcase_86 | RE | - |
| testcase_87 | RE | - |
| testcase_88 | RE | - |
| testcase_89 | RE | - |
| testcase_90 | RE | - |
| testcase_91 | RE | - |
| testcase_92 | RE | - |
| testcase_93 | RE | - |
| testcase_94 | RE | - |
| testcase_95 | RE | - |
| testcase_96 | RE | - |
| testcase_97 | RE | - |
| testcase_98 | RE | - |
| testcase_99 | RE | - |
ソースコード
#include <iostream>
#include <cassert>
#include <vector>
#include <cstdint>
#include <numeric>
#include <chrono>
#include <bitset>
#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 + 10));
}
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();
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;
}
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::pair<i64, 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.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 = 5;
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 });
for(int depth = 0; depth < 25; depth++) {
auto& score = cur_tree.leaf_scores;
int w = std::min(beam_width, (int)score.size());
std::partial_sort(score.begin(), score.begin() + w, score.end(), std::greater<std::pair<int, int>>());
next_tree.edges.clear();
next_tree.leaf_scores.clear();
flagset flag;
for(int i = 0; i < w; i++) {
flag.set(score[i].second);
}
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;
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 << std::endl;
if(init_state.score < 0) {
exit(0);
}
std::cout << act_to_char(act) << std::endl;
}
}
int main() {
solve();
Xor64 mt(786);
}