焼きなましテンプレート

#include <bits/stdc++.h>
//#include <atcoder/all>
//using namespace std;
//using namespace atcoder
// 時間管理
class TimeKeeperDouble {
private:
	std::chrono::high_resolution_clock::time_point start_time_;
	double time_threshold_;
	double now_time_ = 0;
public:
	TimeKeeperDouble(const double time_threshold)
		: start_time_(std::chrono::high_resolution_clock::now()),
		time_threshold_(time_threshold) {}
	void setNowTime() {
		auto diff = std::chrono::high_resolution_clock::now() - this->start_time_;
		this->now_time_ = std::chrono::duration_cast<std::chrono::microseconds>(diff).count() * 1e-3;
	}
	double getNowTime() const { return this->now_time_; }
	bool isTimeOver() const { return now_time_ >= time_threshold_; }
};
// 乱数
class Random {
public:
	std::mt19937 mt_;
	// [0,1.0)
	std::uniform_real_distribution<double> dd_{ 0.0, 1.0 };
	// seedを指定して初期化
	Random(const int seed = 0) : mt_(std::mt19937(seed)) {}
	// [0,m)の整数の範囲の乱数
	inline int nextInt(const int m) {
		std::uniform_int_distribution<int> di(0, m - 1);
		return di(mt_);
	}
	// [n,m)の整数の範囲の乱数
	inline int nextInt(const int n, const int m) {
		std::uniform_int_distribution<int> di(0, m - n - 1);
		return di(mt_) + n;
	}
	// [0,1.0)
	inline double nextDouble() { return dd_(mt_); }
	// [0,1.0)に対応するlog
	inline double nextLog() { return log(dd_(mt_)); }
};
void localInOut() {
#pragma warning(disable : 4996)
	//FILE *in = freopen("../../../../017_ahc/xxx_xxx/xxx/in.txt", "r", stdin);
	//FILE *out = freopen("../../../../017_ahc/xxx_xxx/xxx/out.txt", "w", stdout);
}
namespace constant {
	const bool LOCAL_INOUT = true;
	const bool LOCAL_DEBUG = true;
	const int TIME_LIMIT = 1950;
}
struct Input {
	Input() {}
	void readData() {
		// TODO
	}
};
struct State {
	int score;// TODO;
	State() {}
	void output() {
		// TODO;
	}
	bool operator<(const State& other) const { return score < other.score; }// TODO
	bool operator>(const State& other) const { return score > other.score; }// TODO
};
class Solver {
public:
	Solver(Input input) :input(input) {}
	State run(const double start_temp = 1000, const double end_temp = 0) {
		auto state = initialSolution();
		state = simulatedAnnealing(state, start_temp, end_temp);
		return state;
	}
private:
	Input input;
	TimeKeeperDouble time_keeper = TimeKeeperDouble(constant::TIME_LIMIT);
	Random rnd;
	State initialSolution() {
		// TODO
		State state = State();
		if (constant::LOCAL_DEBUG) {
			std::cout << "initialScore" << state.score << std::endl;
		}
		return State();
	}
	State simulatedAnnealing(State state, const double start_temp, const double end_temp) {
		auto nowState = state;
		auto bestState = state;
		int counter = 0;
		int update = 0;
		int accept = 0;
		while (true) {
			time_keeper.setNowTime();
			if (time_keeper.isTimeOver())break;

			// TODO 近傍に移行しスコアの差分を求める
			int diff = 0;

			double temp = start_temp + (end_temp - start_temp) * (time_keeper.getNowTime() / constant::TIME_LIMIT);
			double diff_threshold = temp * rnd.nextLog();
			if (diff > diff_threshold) {
				//TODO スコアの更新が必要なら更新する
				//nowState.score += diff;
				if (nowState > bestState) {
					bestState = nowState;
					accept++;
				}
				update++;
			}
			else {
				// TODO(状態を戻す必要があるなら戻す)	
			}
			counter++;
		}
		if (constant::LOCAL_DEBUG) {
			std::cout << "Start_temp:" << start_temp << std::endl;
			std::cout << "Counter:" << counter << std::endl;
			std::cout << "Update" << update << std::endl;
			std::cout << "Accept:" << accept << std::endl;
			std::cout << "Score:" << bestState.score << std::endl;
		}
		return bestState;
	}
};
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	if (constant::LOCAL_INOUT)localInOut();
	Input input;
	input.readData();
	Solver solver(input);
	auto state = solver.run();
	state.output();
	return 0;
}