結果

問題 No.5020 Averaging
ユーザー komasandesukomasandesu
提出日時 2024-02-25 16:14:20
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 292 ms / 1,000 ms
コード長 5,464 bytes
コンパイル時間 2,113 ms
コンパイル使用メモリ 150,984 KB
実行使用メモリ 26,644 KB
スコア 26,951,471
最終ジャッジ日時 2024-02-25 16:14:39
合計ジャッジ時間 17,556 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 277 ms
26,132 KB
testcase_01 AC 258 ms
26,260 KB
testcase_02 AC 252 ms
26,132 KB
testcase_03 AC 256 ms
26,132 KB
testcase_04 AC 257 ms
26,132 KB
testcase_05 AC 284 ms
26,260 KB
testcase_06 AC 255 ms
26,136 KB
testcase_07 AC 260 ms
26,260 KB
testcase_08 AC 265 ms
26,260 KB
testcase_09 AC 292 ms
26,260 KB
testcase_10 AC 262 ms
26,132 KB
testcase_11 AC 265 ms
26,132 KB
testcase_12 AC 263 ms
26,132 KB
testcase_13 AC 264 ms
26,132 KB
testcase_14 AC 285 ms
26,132 KB
testcase_15 AC 271 ms
26,132 KB
testcase_16 AC 263 ms
26,132 KB
testcase_17 AC 264 ms
26,132 KB
testcase_18 AC 291 ms
26,132 KB
testcase_19 AC 263 ms
26,260 KB
testcase_20 AC 262 ms
26,260 KB
testcase_21 AC 260 ms
26,132 KB
testcase_22 AC 287 ms
26,260 KB
testcase_23 AC 263 ms
26,260 KB
testcase_24 AC 266 ms
26,132 KB
testcase_25 AC 262 ms
26,132 KB
testcase_26 AC 257 ms
26,132 KB
testcase_27 AC 267 ms
26,004 KB
testcase_28 AC 259 ms
26,132 KB
testcase_29 AC 263 ms
26,132 KB
testcase_30 AC 264 ms
26,132 KB
testcase_31 AC 281 ms
26,132 KB
testcase_32 AC 269 ms
26,132 KB
testcase_33 AC 266 ms
26,132 KB
testcase_34 AC 268 ms
26,260 KB
testcase_35 AC 276 ms
26,132 KB
testcase_36 AC 265 ms
26,132 KB
testcase_37 AC 268 ms
26,132 KB
testcase_38 AC 262 ms
26,136 KB
testcase_39 AC 266 ms
26,132 KB
testcase_40 AC 284 ms
26,132 KB
testcase_41 AC 262 ms
26,132 KB
testcase_42 AC 261 ms
26,644 KB
testcase_43 AC 259 ms
26,132 KB
testcase_44 AC 285 ms
26,260 KB
testcase_45 AC 257 ms
26,132 KB
testcase_46 AC 261 ms
26,132 KB
testcase_47 AC 258 ms
26,132 KB
testcase_48 AC 262 ms
26,132 KB
testcase_49 AC 274 ms
26,132 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Copyright [2022] <Copyright Eita Aoki (Thunder) >
// 本書のサンプルゲーム以外でも時間制限付きビームサーチをするためにコピー&ペーストで使えるサンプルコード
#include <string>
#include <sstream>
#include <random>
#include <iostream>
#include <queue>
#include <chrono>
#include <utility>
#include <vector>
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<std::chrono::milliseconds>(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<pair<int,int>> actions_{};

    vector<pair<long long,long long>> 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<int,int> 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<pair<int,int>> legalActions() const
    {
        std::vector<pair<int,int>> 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<pair<int,int>> 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<State> now_beam;
    State best_state;

    now_beam.push(state);
    for (int t = 0;; t++)
    {
        std::priority_queue<State> 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, 200, 975);

	cout << actions.size() << endl;
    for (auto &action : actions)
    {
        cout << action.first+1 << " " << action.second+1 << endl;
    }
    
    return 0;
}
0