結果

問題 No.5017 Tool-assisted Shooting
ユーザー niuezniuez
提出日時 2023-07-16 16:02:13
言語 C++17
(gcc 12.3.0 + boost 1.83.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,930 ms
24,336 KB
testcase_01 AC 278 ms
24,264 KB
testcase_02 AC 1,899 ms
24,252 KB
testcase_03 AC 1,894 ms
24,288 KB
testcase_04 AC 1,783 ms
24,396 KB
testcase_05 AC 1,432 ms
23,640 KB
testcase_06 AC 1,595 ms
24,276 KB
testcase_07 AC 709 ms
23,388 KB
testcase_08 AC 729 ms
24,276 KB
testcase_09 AC 1,886 ms
23,724 KB
testcase_10 AC 191 ms
23,844 KB
testcase_11 AC 1,920 ms
24,024 KB
testcase_12 AC 1,906 ms
24,036 KB
testcase_13 AC 992 ms
23,388 KB
testcase_14 AC 1,651 ms
24,408 KB
testcase_15 AC 345 ms
23,664 KB
testcase_16 AC 1,892 ms
23,424 KB
testcase_17 AC 647 ms
23,676 KB
testcase_18 AC 1,885 ms
23,376 KB
testcase_19 AC 738 ms
23,832 KB
testcase_20 AC 1,927 ms
24,060 KB
testcase_21 AC 1,897 ms
24,048 KB
testcase_22 AC 1,896 ms
24,048 KB
testcase_23 AC 1,894 ms
23,664 KB
testcase_24 AC 1,906 ms
24,024 KB
testcase_25 AC 1,566 ms
24,048 KB
testcase_26 AC 1,336 ms
24,060 KB
testcase_27 AC 1,911 ms
24,348 KB
testcase_28 AC 1,015 ms
23,652 KB
testcase_29 AC 1,730 ms
24,408 KB
testcase_30 AC 1,880 ms
23,832 KB
testcase_31 AC 1,923 ms
23,400 KB
testcase_32 AC 1,891 ms
24,348 KB
testcase_33 AC 434 ms
24,012 KB
testcase_34 AC 1,897 ms
24,372 KB
testcase_35 AC 1,877 ms
24,336 KB
testcase_36 AC 1,924 ms
23,652 KB
testcase_37 AC 501 ms
23,412 KB
testcase_38 AC 1,897 ms
23,544 KB
testcase_39 AC 1,863 ms
24,060 KB
testcase_40 AC 1,903 ms
23,424 KB
testcase_41 AC 1,919 ms
24,036 KB
testcase_42 AC 1,811 ms
23,544 KB
testcase_43 AC 1,916 ms
23,664 KB
testcase_44 AC 526 ms
23,424 KB
testcase_45 AC 1,894 ms
24,336 KB
testcase_46 AC 1,901 ms
23,652 KB
testcase_47 AC 1,927 ms
23,388 KB
testcase_48 AC 1,909 ms
23,424 KB
testcase_49 AC 654 ms
23,544 KB
testcase_50 AC 1,910 ms
23,664 KB
testcase_51 AC 1,898 ms
23,832 KB
testcase_52 AC 1,905 ms
24,288 KB
testcase_53 AC 1,879 ms
24,408 KB
testcase_54 AC 1,879 ms
24,060 KB
testcase_55 AC 1,219 ms
24,048 KB
testcase_56 AC 1,900 ms
23,544 KB
testcase_57 AC 1,891 ms
23,412 KB
testcase_58 AC 1,925 ms
23,376 KB
testcase_59 AC 1,912 ms
23,628 KB
testcase_60 AC 1,958 ms
23,424 KB
testcase_61 AC 1,888 ms
24,396 KB
testcase_62 AC 1,907 ms
23,640 KB
testcase_63 AC 1,914 ms
23,436 KB
testcase_64 AC 1,883 ms
24,408 KB
testcase_65 AC 483 ms
23,388 KB
testcase_66 AC 1,389 ms
23,844 KB
testcase_67 AC 1,882 ms
24,348 KB
testcase_68 AC 1,896 ms
23,652 KB
testcase_69 AC 1,913 ms
23,892 KB
testcase_70 AC 1,089 ms
24,048 KB
testcase_71 AC 505 ms
24,360 KB
testcase_72 AC 1,917 ms
24,024 KB
testcase_73 AC 1,902 ms
23,844 KB
testcase_74 AC 1,882 ms
23,544 KB
testcase_75 AC 1,901 ms
23,844 KB
testcase_76 AC 1,867 ms
23,544 KB
testcase_77 AC 1,901 ms
23,604 KB
testcase_78 AC 1,502 ms
24,360 KB
testcase_79 AC 1,873 ms
24,276 KB
testcase_80 AC 1,877 ms
23,856 KB
testcase_81 AC 1,886 ms
23,556 KB
testcase_82 AC 597 ms
24,024 KB
testcase_83 AC 1,925 ms
24,516 KB
testcase_84 AC 1,893 ms
23,532 KB
testcase_85 AC 1,891 ms
23,244 KB
testcase_86 AC 1,870 ms
24,024 KB
testcase_87 AC 691 ms
24,024 KB
testcase_88 AC 322 ms
23,844 KB
testcase_89 AC 1,920 ms
24,060 KB
testcase_90 AC 1,887 ms
23,424 KB
testcase_91 AC 1,900 ms
24,408 KB
testcase_92 AC 1,917 ms
23,424 KB
testcase_93 AC 1,876 ms
23,388 KB
testcase_94 AC 1,911 ms
23,388 KB
testcase_95 AC 1,886 ms
24,036 KB
testcase_96 AC 905 ms
24,012 KB
testcase_97 AC 1,902 ms
24,276 KB
testcase_98 AC 1,901 ms
23,436 KB
testcase_99 AC 1,927 ms
24,036 KB
権限があれば一括ダウンロードができます

ソースコード

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