結果

問題 No.5017 Tool-assisted Shooting
ユーザー niuezniuez
提出日時 2023-07-16 15:51:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 7,547 bytes
コンパイル時間 1,427 ms
コンパイル使用メモリ 105,868 KB
実行使用メモリ 24,504 KB
スコア 1,446
平均クエリ数 136.17
最終ジャッジ日時 2023-07-16 15:55:02
合計ジャッジ時間 204,735 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 AC 353 ms
23,844 KB
testcase_02 TLE -
testcase_03 TLE -
testcase_04 TLE -
testcase_05 AC 1,816 ms
24,396 KB
testcase_06 TLE -
testcase_07 AC 904 ms
23,436 KB
testcase_08 AC 878 ms
23,400 KB
testcase_09 AC 368 ms
24,348 KB
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 AC 1,240 ms
23,424 KB
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 AC 821 ms
23,388 KB
testcase_18 TLE -
testcase_19 AC 891 ms
24,408 KB
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 AC 1,944 ms
24,048 KB
testcase_26 AC 1,702 ms
23,424 KB
testcase_27 TLE -
testcase_28 AC 1,276 ms
24,324 KB
testcase_29 AC 511 ms
24,024 KB
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 AC 541 ms
24,084 KB
testcase_34 AC 913 ms
23,688 KB
testcase_35 TLE -
testcase_36 TLE -
testcase_37 AC 657 ms
23,832 KB
testcase_38 TLE -
testcase_39 TLE -
testcase_40 TLE -
testcase_41 TLE -
testcase_42 TLE -
testcase_43 TLE -
testcase_44 AC 625 ms
24,012 KB
testcase_45 AC 1,462 ms
23,400 KB
testcase_46 TLE -
testcase_47 TLE -
testcase_48 TLE -
testcase_49 TLE -
testcase_50 TLE -
testcase_51 AC 1,307 ms
23,424 KB
testcase_52 AC 1,335 ms
23,832 KB
testcase_53 TLE -
testcase_54 TLE -
testcase_55 AC 1,511 ms
23,640 KB
testcase_56 TLE -
testcase_57 AC 1,137 ms
23,388 KB
testcase_58 TLE -
testcase_59 TLE -
testcase_60 TLE -
testcase_61 TLE -
testcase_62 TLE -
testcase_63 TLE -
testcase_64 TLE -
testcase_65 AC 569 ms
23,544 KB
testcase_66 AC 1,758 ms
24,360 KB
testcase_67 TLE -
testcase_68 TLE -
testcase_69 TLE -
testcase_70 AC 1,399 ms
23,436 KB
testcase_71 AC 630 ms
23,424 KB
testcase_72 TLE -
testcase_73 TLE -
testcase_74 TLE -
testcase_75 TLE -
testcase_76 AC 315 ms
23,544 KB
testcase_77 TLE -
testcase_78 AC 1,847 ms
24,384 KB
testcase_79 TLE -
testcase_80 TLE -
testcase_81 TLE -
testcase_82 AC 753 ms
23,544 KB
testcase_83 TLE -
testcase_84 TLE -
testcase_85 AC 1,267 ms
24,384 KB
testcase_86 TLE -
testcase_87 AC 833 ms
24,348 KB
testcase_88 AC 399 ms
23,424 KB
testcase_89 TLE -
testcase_90 TLE -
testcase_91 TLE -
testcase_92 TLE -
testcase_93 TLE -
testcase_94 TLE -
testcase_95 TLE -
testcase_96 AC 1,133 ms
24,324 KB
testcase_97 TLE -
testcase_98 TLE -
testcase_99 TLE -
権限があれば一括ダウンロードができます

ソースコード

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