結果

問題 No.5017 Tool-assisted Shooting
ユーザー niuezniuez
提出日時 2023-07-16 16:24:22
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,934 ms / 2,000 ms
コード長 7,928 bytes
コンパイル時間 1,687 ms
コンパイル使用メモリ 115,504 KB
実行使用メモリ 24,408 KB
スコア 19,900
平均クエリ数 940.00
最終ジャッジ日時 2023-07-16 16:27:47
合計ジャッジ時間 193,437 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,917 ms
23,652 KB
testcase_01 AC 1,837 ms
23,664 KB
testcase_02 AC 1,892 ms
23,424 KB
testcase_03 AC 1,841 ms
23,664 KB
testcase_04 AC 1,870 ms
23,544 KB
testcase_05 AC 1,867 ms
23,388 KB
testcase_06 AC 1,862 ms
24,060 KB
testcase_07 AC 1,870 ms
23,964 KB
testcase_08 AC 1,854 ms
23,544 KB
testcase_09 AC 1,865 ms
23,544 KB
testcase_10 AC 1,849 ms
23,676 KB
testcase_11 AC 1,856 ms
24,024 KB
testcase_12 AC 1,889 ms
24,012 KB
testcase_13 AC 1,855 ms
24,024 KB
testcase_14 AC 1,874 ms
24,396 KB
testcase_15 AC 1,836 ms
23,640 KB
testcase_16 AC 1,838 ms
24,396 KB
testcase_17 AC 1,862 ms
24,396 KB
testcase_18 AC 1,834 ms
23,424 KB
testcase_19 AC 1,853 ms
24,396 KB
testcase_20 AC 1,844 ms
23,832 KB
testcase_21 AC 1,844 ms
23,664 KB
testcase_22 AC 1,886 ms
24,072 KB
testcase_23 AC 1,855 ms
24,048 KB
testcase_24 AC 1,834 ms
24,036 KB
testcase_25 AC 1,863 ms
23,664 KB
testcase_26 AC 1,932 ms
24,036 KB
testcase_27 AC 1,871 ms
23,412 KB
testcase_28 AC 1,823 ms
23,676 KB
testcase_29 AC 1,884 ms
23,544 KB
testcase_30 AC 1,865 ms
24,396 KB
testcase_31 AC 1,831 ms
24,048 KB
testcase_32 AC 1,897 ms
24,036 KB
testcase_33 AC 1,833 ms
23,436 KB
testcase_34 AC 1,862 ms
23,532 KB
testcase_35 AC 1,839 ms
24,216 KB
testcase_36 AC 1,851 ms
23,400 KB
testcase_37 AC 1,867 ms
24,036 KB
testcase_38 AC 1,853 ms
24,384 KB
testcase_39 AC 1,873 ms
23,640 KB
testcase_40 AC 1,841 ms
24,060 KB
testcase_41 AC 1,846 ms
24,372 KB
testcase_42 AC 1,872 ms
24,384 KB
testcase_43 AC 1,842 ms
23,856 KB
testcase_44 AC 1,854 ms
24,324 KB
testcase_45 AC 1,835 ms
24,024 KB
testcase_46 AC 1,838 ms
24,348 KB
testcase_47 AC 1,873 ms
23,388 KB
testcase_48 AC 1,828 ms
24,024 KB
testcase_49 AC 1,853 ms
24,396 KB
testcase_50 AC 1,876 ms
24,024 KB
testcase_51 AC 1,832 ms
23,424 KB
testcase_52 AC 1,829 ms
23,640 KB
testcase_53 AC 1,826 ms
24,024 KB
testcase_54 AC 1,858 ms
24,024 KB
testcase_55 AC 1,832 ms
23,832 KB
testcase_56 AC 1,845 ms
23,544 KB
testcase_57 AC 1,880 ms
23,832 KB
testcase_58 AC 1,839 ms
24,060 KB
testcase_59 AC 1,857 ms
24,384 KB
testcase_60 AC 1,845 ms
24,264 KB
testcase_61 AC 1,838 ms
24,360 KB
testcase_62 AC 1,806 ms
24,036 KB
testcase_63 AC 1,858 ms
23,628 KB
testcase_64 AC 1,816 ms
24,276 KB
testcase_65 AC 1,845 ms
24,048 KB
testcase_66 AC 1,832 ms
23,424 KB
testcase_67 AC 1,831 ms
24,048 KB
testcase_68 AC 1,831 ms
24,072 KB
testcase_69 AC 1,831 ms
23,412 KB
testcase_70 AC 1,858 ms
23,424 KB
testcase_71 AC 1,842 ms
23,544 KB
testcase_72 AC 1,854 ms
23,532 KB
testcase_73 AC 1,860 ms
23,388 KB
testcase_74 AC 1,853 ms
23,544 KB
testcase_75 AC 1,863 ms
23,640 KB
testcase_76 AC 1,845 ms
23,424 KB
testcase_77 AC 1,852 ms
23,424 KB
testcase_78 AC 1,851 ms
24,360 KB
testcase_79 AC 1,835 ms
23,544 KB
testcase_80 AC 1,857 ms
23,544 KB
testcase_81 AC 1,821 ms
23,676 KB
testcase_82 AC 1,850 ms
23,640 KB
testcase_83 AC 1,859 ms
23,640 KB
testcase_84 AC 1,838 ms
23,556 KB
testcase_85 AC 1,853 ms
23,544 KB
testcase_86 AC 1,841 ms
24,036 KB
testcase_87 AC 1,849 ms
24,408 KB
testcase_88 AC 1,861 ms
24,048 KB
testcase_89 AC 1,850 ms
23,388 KB
testcase_90 AC 1,865 ms
23,904 KB
testcase_91 AC 1,934 ms
24,012 KB
testcase_92 AC 1,870 ms
23,676 KB
testcase_93 AC 1,836 ms
23,652 KB
testcase_94 AC 1,862 ms
23,400 KB
testcase_95 AC 1,862 ms
23,556 KB
testcase_96 AC 1,844 ms
23,652 KB
testcase_97 AC 1,877 ms
24,384 KB
testcase_98 AC 1,824 ms
24,384 KB
testcase_99 AC 1,867 ms
24,396 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 = 30;
  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);
    int st = 0;
    for(int i = 0; st < beam_width && i < score.size(); i++) {
      auto& [s, id, x] = score[i];
      if(cnt[x]++ < 2) {
        st++;
        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);
}
0