// Copyright [2022] // 本書のサンプルゲーム以外でも時間制限付きビームサーチをするためにコピー&ペーストで使えるサンプルコード #include #include #include #include #include #include #include #include using namespace std; int N; long long A[59]; long long B[59]; const long long avg = 500000000000000000; const long long INFL = 6e18; // 時間を管理するクラス class TimeKeeper { private: std::chrono::high_resolution_clock::time_point start_time_; int64_t time_threshold_; public: // 時間制限をミリ秒単位で指定してインスタンスをつくる。 TimeKeeper(const int64_t &time_threshold) : start_time_(std::chrono::high_resolution_clock::now()), time_threshold_(time_threshold) { } // インスタンス生成した時から指定した時間制限を超過したか判定する。 bool isTimeOver() const { auto diff = std::chrono::high_resolution_clock::now() - this->start_time_; return std::chrono::duration_cast(diff).count() >= time_threshold_; } }; std::mt19937 mt_for_action(0); // 行動選択用の乱数生成器を初期化 using ScoreType = int64_t; // ゲームの評価スコアの型を決めておく。 constexpr const ScoreType INF = 1000000000LL; // あり得ないぐらい大きなスコアの例を用意しておく class State { private: public: ScoreType evaluated_score_ = 0; // 探索上で評価したスコア vector> actions_{}; vector> cards_; int turn_ = 0; State() {} // ゲームの終了判定 bool isDone() const { return this->turn_ == 50; } // 探索用の盤面評価をする void evaluateScore() { long long max_diff = 0; max_diff = max( abs(avg-cards_[0].first),abs(avg-cards_[0].second) ); this->evaluated_score_ = -max_diff; } // 指定したactionでゲームを1ターン進める void advance(const pair action) { int i = action.first; int j = action.second; long long avg_card_A = (cards_[i].first+cards_[j].first)/2; long long avg_card_B = (cards_[i].second+cards_[j].second)/2; cards_[i].first = avg_card_A; cards_[j].first = avg_card_A; cards_[i].second = avg_card_B; cards_[j].second = avg_card_B; ++this->turn_; } // 現在の状況でプレイヤーが可能な行動を全て取得する std::vector> legalActions() const { std::vector> actions; for (int i = 1; i < N; i++) { actions.push_back({0,i}); } return actions; } // // 必要に応じてアンコメント // // 現在のゲーム状況を文字列にする // std::string toString() const // { // return /*(std::string)文字列化されたゲーム状況*/; // } }; // 探索時のソート用に評価を比較する bool operator<(const State &state_1, const State &state_2) { return state_1.evaluated_score_ < state_2.evaluated_score_; } // ビーム幅と制限時間(ms)を指定してビームサーチで行動を決定する vector> beamSearchActionWithTimeThreshold( const State &state, const int beam_width, const int64_t time_threshold) { auto time_keeper = TimeKeeper(time_threshold); auto legal_actions = state.legalActions(); std::priority_queue now_beam; State best_state; now_beam.push(state); for (int t = 0;; t++) { std::priority_queue next_beam; for (int i = 0; i < beam_width; i++) { if (time_keeper.isTimeOver()) { return best_state.actions_; } 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(); 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_; } // 入力を読み取る void read() { // Step 1. 入力 cin >> N; for (int i = 0; i < N; i++) cin >> A[i] >> B[i]; } int main() { /********************************************************************/ // 1. 入力を読み取る read(); /********************************************************************/ State state{}; state.cards_.resize(N); for (int i = 0; i < N; i++) { state.cards_[i].first = A[i]; state.cards_[i].second = B[i]; } auto actions = beamSearchActionWithTimeThreshold(state, 16, 975); cout << actions.size() << endl; for (auto &action : actions) { cout << action.first+1 << " " << action.second+1 << endl; } return 0; }