#include const int LOCAL = 0; // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair; const ll INF=4e18; #define debug1(a) { cerr<<#a<<":"<> n; for (int it = 0; it < n; it++) { int h, p, x; cin >> h >> p >> x; enemy_t e; e.hp = h; e.init_hp = h; e.power = p; state.board[H - 1][x] = e; } } void generate_enemies(state_t &state) { return; double mean = 7.5 + 0.15 * state.turn; double sd = 1.5 + 0.03 * state.turn; normal_distribution<> dist(mean, sd); for (int c = 0; c < W; c++) { double prob = 0.05; // TODO 履歴から確率を推定する if (marathon::uniform(0.0, 1.0) < prob) { // double h_ = dist(marathon::engine); // int h = max(1, int(h_)); // normal_distribution<> distp(0.8 * h_, 0.1 * h_); // double p_ = distp(marathon::engine); // int p = max(0, int(p_)); int h = mean; int p = 0.8 * h; enemy_t e; e.hp = h; e.init_hp = h; e.power = p; state.board[H - 1][c] = e; } } } bool move_enemies(state_t &state) { for (int r = 0; r < H - 1; r++) { for (int c = 0; c < W; c++) { state.board[r][c] = state.board[r + 1][c]; } } for (int c = 0; c < W; c++) { state.board[H - 1][c] = {-1, -1, -1}; } return state.board[0][state.my_c].hp <= 0; } char greedy_op(state_t &state) { vector scores(3, 0.0); for (int pi = 0; pi <= 2; pi++) { scores[pi] = marathon::uniform(0.01, 0.02); int c = state.my_c; if (pi == 0) { c--; } else if (pi == 2) { c++; } // 盤面の外 if (c < 0 || c >= W) { scores[pi] += -1e18; continue; } // ゲームオーバー if (state.board[0][c].hp > 0) { scores[pi] += -1e16; } // 敵への攻撃 for (int r = 1; r < H; r++) { int level = state.level(); enemy_t e = state.board[r][c]; if (e.hp <= 0) continue; int turns = (e.hp + level - 1) / level; if (turns > r) { scores[pi] += -1e10 * (H - r); // 倒せるかどうか } else { double ratio = 1.0 * e.power / turns; scores[pi] += ratio * 1e5; } break; } // 敵との近さ for (int d = 0; d < W; d++) { for (int r = 1; r < H; r++) { int distance = abs(c - d); enemy_t e = state.board[r][d]; if (e.hp <= 0) continue; int level = state.level(); // 本当は途中でレベルが上がるが... int turns = (e.hp + level - 1) / level; if (turns + abs(c - d) > r) continue; // 倒せるかどうか double ratio = 1.0 * e.power / turns; scores[pi] += ratio / (distance + 1.0); // TODO 適当 } } } pair max_score = {-1e50, -1}; for (int i = 0; i <= 2; i++) { max_score = max({scores[i], i}, max_score); } if (max_score.second == 0) { return 'L'; } else if (max_score.second == 2) { return 'R'; } else { return 'S'; } } bool move_attack(state_t &state, char op) { if (op == 'L') { state.my_c--; } else if (op == 'R') { state.my_c++; } if (state.my_c < 0 || state.my_c >= W) return false; if (state.board[0][state.my_c].hp > 0) return false; for (int i = 1; i < H; i++) { if (state.board[i][state.my_c].hp > 0) { state.board[i][state.my_c].hp -= state.level(); // debug4(state.turn, i, state.my_c, state.level()); if (state.board[i][state.my_c].hp <= 0) { state.total_power += state.board[i][state.my_c].power; state.total_hp += state.board[i][state.my_c].init_hp; state.board[i][state.my_c] = {-1, -1, -1}; } break; } } return true; } double montecarlo_score(int pi, state_t &org_state) { const int MONTECARLO_ITER = 1; double total_score = 0; for (int mit = 0; mit < MONTECARLO_ITER; mit++) { auto state = org_state; { // 初回移動 char op = 'S'; if (pi == 0) op = 'L'; if (pi == 2) op = 'R'; bool alive2 = move_attack(state, op); if (!alive2) return -1e8; } int init_turn = org_state.turn; // int end_turn = 1000; // TODO init_turn+100くらいで十分な気がする。その場合、 前半はパワーの稼ぎ重視? int end_turn = init_turn + H; for (int turn = init_turn + 1; turn <= end_turn; turn++) { state.turn = turn; bool alive1 = move_enemies(state); if (!alive1) { total_score -= 1e6; break; } generate_enemies(state); char op = greedy_op(state); bool alive2 = move_attack(state, op); total_score += state.total_power; if (!alive2) { total_score -= 1e6; break; } } // if (init_turn > 600) { // total_score += state.total_hp; // } else { // total_score += state.total_power; // } } return total_score; } char select_op(state_t &state) { int turn = state.turn; vector scores(3, 0.0); for (int pi = 0; pi <= 2; pi++) { scores[pi] = montecarlo_score(pi, state); } pair max_score = {-1e50, -1}; for (int i = 0; i <= 2; i++) { max_score = max({scores[i], i}, max_score); } if (max_score.second == 0) { return 'L'; } else if (max_score.second == 2) { return 'R'; } else { return 'S'; } } int main() { marathon::marathon_init(); if (LOCAL) { for (int c = 0; c < W; c++) { int p; cin >> p; } } state_t state; { state.total_power = 0; state.total_hp = 0; state.my_c = INIT_MY_C; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { state.board[r][c] = {-1, -1, -1}; } } } for (int turn = 1; turn <= 1000; turn++) { state.turn = turn; bool alive1 = move_enemies(state); if (!alive1) break; read_enemies(state); char op = select_op(state); cout << op << endl; bool alive2 = move_attack(state, op); if (!alive2) break; } cerr << "score==" << state.total_hp << " turn==" << state.turn << " power==" << state.total_power << " time==" << marathon::now() << endl; return 0; }