// Copyright [2022] // どこが間違っているのかわからず。いったん中止 #include #include #include #include #include #include using namespace std; #define ll long long #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) // 時間を管理するクラス class TimeKeeper { private: chrono::high_resolution_clock::time_point start_time_; int64_t time_threshold_; public: // 時間制限をミリ秒単位で指定してインスタンスをつくる。 TimeKeeper(const int64_t &time_threshold) : start_time_(chrono::high_resolution_clock::now()), time_threshold_(time_threshold) { } // インスタンス生成した時から指定した時間制限を超過したか判定する。 bool isTimeOver() const { auto diff = chrono::high_resolution_clock::now() - this->start_time_; return chrono::duration_cast(diff).count() >= time_threshold_; } }; mt19937 mt_for_action(0); // 行動選択用の乱数生成器を初期化 using ScoreType = int64_t; // ゲームの評価スコアの型を決めておく。 constexpr const ScoreType INF = 1000000000LL; // あり得ないぐらい大きなスコアの例を用意しておく constexpr const int T = 1000; constexpr const int DY[4] = {0, 0, 1, -1}; // 右、左、下、上への移動方向のy成分 constexpr const int DX[4] = {1, -1, 0, 0}; // 右、左、下、上への移動方向のx成分 constexpr const char DC[4] = {'R', 'L', 'D', 'U'}; constexpr int width = 25; // フィールドの幅 constexpr int height = 60; // フィールドの高さ constexpr int max_turn = 1000; // ゲームの最大ターン数 const char choice[3] = {'L', 'R', 'S'}; //敵機情報 struct Data { int h; int p; int x; int y; Data(int h, int p, int x, int y) : h(h), p(p), x(x), y(y) {} }; vector data_moto[25]; class State { private: public: ScoreType evaluated_score_ = 0; // 探索上で評価したスコア int score_=0; int first_action_ = -1; // 探索木のルートノードで最初に選択した行動 int sx=12; int turn_ = 0; // 現在のターン int power=0; int kogeki=1; vector data[25]; int lane[25]; State() {} // ゲームの終了判定 bool isDone() const { /*処理*/ return this->turn_ == T; //return /*(bool)終了判定*/; } // 探索用の盤面評価をする void evaluateScore() { int res=0; int min_i=-1; int sho=1000; //kogeki=1; rep(i,25){ if (lane[i]==-1)continue; if(lane[i]+1>data[i].size())continue; Data z=data[i][lane[i]]; if(z.h==0)continue; kogeki=1+(power/100); if(kogeki<=0)kogeki=1; //cerr<<__LINE__<<"---"<1&&sho>abs(sx-z.x)+evaluated_score&&z.y!=-1&&z.x!=-1&&z.h>0){ min_i=z.x; sho=abs(sx-z.x)+evaluated_score; res=tmp; } } this->evaluated_score_ = res+score_; cout<<"#res"<evaluated_score_ = /*(ScoreType)評価結果*/; } // 指定したactionでゲームを1ターン進める void advance(const int action) { if(action==0){//L sx++; if(sx==25)sx=0; }else if (action==1){//R sx--; if(sx==-1)sx=24; }else{//S stay } rep(i,25){ if (lane[i]==-1)continue; int size=data[i].size(); rep(j,size){ Data& z=data[i][j];// if(z.y!=-1)z.y=z.y-1; if(lane[i]==j&&z.y<0)lane[i]==j+1; } } if(turn_==1)cerr<<__LINE__<<"---turn_"<turn_; } // 現在の状況でプレイヤーが可能な行動を全て取得する vector legalActions() const { vector actions; /*処理*/ for (int action = 0; action < 3; action++) { int nx=sx; if(action==0)nx++; else if(action==1)nx--; bool can_action = true; rep(i,25){ int z=data[i].size(); if(z!=0){ rep(j,z){ auto q=data[i][j]; if(q.x!=nx)continue; if(q.y==1)can_action=false; if(q.y==0)can_action=false; } } } if (can_action) { actions.emplace_back(action); } } cout<<"#legal action size:"< beamSearchActionWithTimeThreshold( const State &state, const int beam_width, const int64_t time_threshold) { auto time_keeper = TimeKeeper(time_threshold); auto legal_actions = state.legalActions(); priority_queue now_beam; State best_state; now_beam.push(state); for (int t = 0;; t++) { priority_queue next_beam; for (int i = 0; i < beam_width; i++) { if (time_keeper.isTimeOver()) { //return best_state.actions_; return best_state.first_action_; } if (now_beam.empty()) break; State now_state = now_beam.top(); now_beam.pop(); auto legal_actions = now_state.legalActions(); for (const auto &action : legal_actions) { State next_state = now_state; next_state.advance(action); next_state.evaluateScore(); if (t == 0) next_state.first_action_ = action; //next_state.actions_.emplace_back(action);// next_beam.push(next_state); } } now_beam = next_beam; best_state = now_beam.top(); if (best_state.isDone()) { break; } } //return best_state.actions_; return best_state.first_action_; } int main() { #ifdef ONLINE_JUDGE #else //読み飛ばし //rep(i,25){ // int nx; // cin>>nx; //} #endif State state; for (int turn = 1; turn <= max_turn; turn++) { /********************************************************************/ // 1. 入力を読み取る int n; cin >> n; if (n == -1)return 0; for (int i = 0; i < n; i++) { int h1, p1, x1; cin >> h1 >> p1 >> x1; state.data[x1].emplace_back(h1, p1, x1, 59); data_moto[x1].emplace_back(h1, p1, x1, 59); if(state.lane[x1]==-1)state.lane[x1]=0; } /********************************************************************/ // 2.ビームサーチで探索する //int action=beamSearchActionWithTimeThreshold(state, 64, 3);//幅64、3msec int action=beamSearchActionWithTimeThreshold(state, 1, 3);//幅64、3msec if(action==0){//L state.sx++; if(state.sx==25)state.sx=0; }else if (action==1){//R state.sx--; if(state.sx==-1)state.sx=24; }else{//S stay } /********************************************************************/ // 3.探索結果の行動を出力する cout<