結果
問題 | No.5020 Averaging |
ユーザー |
|
提出日時 | 2024-02-25 15:19:34 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 587 ms / 1,000 ms |
コード長 | 5,332 bytes |
コンパイル時間 | 2,904 ms |
コンパイル使用メモリ | 232,336 KB |
実行使用メモリ | 16,700 KB |
スコア | 16,377,294 |
最終ジャッジ日時 | 2024-02-25 15:20:13 |
合計ジャッジ時間 | 31,418 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ull=unsigned long long;// 128bit整数std::ostream &operator<<(std::ostream &dest, __int128_t value) {std::ostream::sentry s(dest);if (s) {__uint128_t tmp = value < 0 ? -value : value;char buffer[128];char *d = std::end(buffer);do {--d;*d = "0123456789"[tmp % 10];tmp /= 10;} while (tmp != 0);if (value < 0) {--d;*d = '-';}int len = std::end(buffer) - d;if (dest.rdbuf()->sputn(d, len) != len) {dest.setstate(std::ios_base::badbit);}}return dest;}__int128 parse(string &s) {__int128 ret = 0;for (int i = 0; i < s.length(); i++)if ('0' <= s[i] && s[i] <= '9')ret = 10 * ret + s[i] - '0';return ret;}// 128bit整数ここまでconstexpr int MAX_TURN = 50;constexpr __int128 TARGET = 500000000000000000;struct Card {__int128 omote, ura;};class GameState{private:int _turn;vector<Card> _cards;vector<pair<int, int>> _commandHistory;public:int nowScore;pair<int, int> first_action_;GameState(){};GameState(vector<unsigned long long> omotes, vector<unsigned long long> uras): _turn(0), nowScore(0) {for (int i = 0; i < omotes.size(); i++) {_cards.push_back({omotes[i], uras[i]});}}__int128 getEstimatedScore() {__int128 score = 0;// 1枚目のみ別に評価__int128 omotediff = TARGET - _cards[0].omote;if (omotediff > 0) {omotediff *= -1;}score += omotediff;__int128 uradiff = TARGET - _cards[0].ura;if (uradiff > 0) {uradiff *= -1;}score += uradiff;// 満点ならその時点で終了if (omotediff == 0 && uradiff == 0) {score += 9999999999999999;}// 2枚目以降const Card OTHER_TARGET = { TARGET * 2 - _cards[0].omote, TARGET * 2 - _cards[0].ura };for (int i = 1; i < _cards.size(); i++) {__int128 omotediff = OTHER_TARGET.omote - _cards[i].omote;if (omotediff > 0) {omotediff *= -1;}score += omotediff * _turn;__int128 uradiff = OTHER_TARGET.ura - _cards[i].ura;if (uradiff > 0) {uradiff *= -1;}score += uradiff * _turn;// 満点ならその時点で終了if (omotediff == 0 && uradiff == 0) {score += 99999999;}}return score;}// 1ターン進めるvoid advance(int u, int v){_commandHistory.push_back({u, v});_turn++;Card newCard = {(_cards[u].omote + _cards[v].omote) / 2, (_cards[u].ura + _cards[v].ura) / 2};_cards[u] = newCard;_cards[v] = newCard;nowScore = getEstimatedScore();}// 合法手を列挙するvector<pair<int, int>> legalActions() const{vector<pair<int, int>> ret;for (int i = 0; i < _cards.size(); i++) {for (int j = i + 1; j < _cards.size(); j++) {ret.push_back({i, j});}}return ret;}// ゲームが終了しているかどうかbool isDone() const{return _turn == MAX_TURN;}// 結果の出力を行うstring outputCommand() {stringstream ss;ss << _commandHistory.size() << endl;for (auto command : _commandHistory) {ss << command.first + 1 << " " << command.second + 1 << endl;}return ss.str();}// 現在の実スコアを出力するdouble getScore() {ull v = max( max((ull)_cards[0].omote, (ull)TARGET) - min((ull)_cards[0].omote, (ull)TARGET), max((ull)_cards[0].ura, (ull)TARGET) - min((ull)_cards[0].ura, (ull)TARGET) );long long score = 2000000 - 100000 * log10(static_cast<long double>(v));return score;}};bool operator<(const GameState &state1, const GameState &state2){return state1.nowScore < state2.nowScore;}pair<int,int> beamSearchAction(const GameState &initState, const int beamWidth, const int beamDepth){priority_queue<GameState> nowBeam;GameState bestState;nowBeam.push(initState);for (int t = 0; t < beamDepth; t++){std::priority_queue<GameState> nextBeam;for (int i = 0; i < beamWidth; i++){if (nowBeam.empty())break;GameState nowState = nowBeam.top();nowBeam.pop();auto legal_actions = nowState.legalActions();for (const auto &action : legal_actions){GameState nextState = nowState;nextState.advance(action.first, action.second);if (t == 0)nextState.first_action_ = action;nextBeam.push(nextState);}}nowBeam = nextBeam;bestState = nowBeam.top();if (bestState.isDone()){break;}}return bestState.first_action_;}pair<vector<unsigned long long>, vector<unsigned long long>> getFromInput() {int n;cin >> n;vector<unsigned long long> omotes(n), uras(n);for (int i = 0; i < n; i++) {cin >> omotes[i] >> uras[i];}return {omotes, uras};}int main() {// 本番用auto input = getFromInput();GameState state(input.first, input.second);while (!state.isDone()) {auto action = beamSearchAction(state, 3, 3);state.advance(action.first, action.second);// cerr<<state.getScore()<<endl;}cout << state.outputCommand();}