結果

問題 No.5017 Tool-assisted Shooting
ユーザー niuez
提出日時 2023-07-16 16:02:13
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,958 ms / 2,000 ms
コード長 7,547 bytes
コンパイル時間 1,397 ms
コンパイル使用メモリ 106,024 KB
実行使用メモリ 24,516 KB
スコア 4,115
平均クエリ数 823.61
最終ジャッジ日時 2023-07-16 16:05:04
合計ジャッジ時間 170,520 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 + 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();
        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 = 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 });
  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>>());
    //std::cerr << depth << " " << score[0].first << " " << score[w - 1].first << std::endl;
    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;
    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::cout << act_to_char(act) << std::endl;
  }
}
int main() {
  solve();
  Xor64 mt(786);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0