結果

問題 No.5017 Tool-assisted Shooting
ユーザー niuezniuez
提出日時 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 -
権限があれば一括ダウンロードができます

ソースコード

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 + 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);
}
0