library
This documentation is automatically generated by online-judge-tools/verification-helper
util/marathon/simulated_annealing.cpp
- View this file on GitHub
- Last update: 2022-07-24 18:14:06+09:00
- Link: https://atcoder.jp/contests/chokudai004/submissions/9724794
Depends on
Code
// 利用例: https://atcoder.jp/contests/chokudai004/submissions/9724794
#include "template.hpp"
using namespace std;
// update(), calcScore(), revert(), write()を実装する
struct State {
double score = 0;
State() {}
double update(double progress) { return 0; } // FIXME: 状態を次状態に更新しスコアの差分を返す.
double calcScore() { return 0; } // FIXME: 現在の状態のスコアを返す.
void revert() {} // update()適用前の状態に戻す.
void write() {} // 現在の状態を出力する.
};
struct SASolver {
double startTemp = 30;
double endTemp = 10;
Timer timer = Timer(2.95);
State best;
SASolver() { init(); }
SASolver(double st, double et): startTemp(st), endTemp(et) { init(); }
SASolver(double st, double et, double limit): startTemp(st), endTemp(et), timer(limit) { init(); }
void init() {} // 初期化処理をここに書く
void solve(State &state) {
double t;
best = state;
int step = 0;
// best.write();
while ((t = timer.get()) < timer.LIMIT) // 焼きなまし終了時刻までループ
{
double T = startTemp + (endTemp - startTemp) * t / timer.LIMIT;
double progress = t/timer.LIMIT;
// assert(0 <= progress && progress <= 1);
for (int i = 0; i < 100; ++i) { // 時間計算を間引く
double diff = state.update(progress);
// 最初t=0のときは、スコアが良くなろうが悪くなろうが、常に次状態を使用
// 最後t=timer.LIMITのときは、スコアが改善したときのみ、次状態を使用
// スコアが良くなった or 悪くなっても強制遷移
double tr = T*rng.nextLog();
if (diff >= tr)
{
if (best.score < state.score) {
best = state;
D1(t, step, best.score);
// best.write();
}
}
else { state.revert(); }
++step;
}
}
D1(step, best.score);
}
};
#if 0
int main() {
State state; // 開始状態
SASolver s;
s.solve(state);
s.best.write();
}
#endif#line 1 "util/marathon/simulated_annealing.cpp"
// 利用例: https://atcoder.jp/contests/chokudai004/submissions/9724794
#line 2 "util/marathon/template.hpp"
#include <bits/stdc++.h>
// #define DEBUG
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REPR(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
// ------------------------ DEBUG PRINT --------------------------
template<class T>
void print_collection(std::ostream& out, T const& x);
template<class A>
std::ostream& operator<<(std::ostream& out, std::vector<A> const& x) { print_collection(out, x); return out; }
template<class A, size_t N>
std::ostream& operator<<(std::ostream& out, std::array<A, N> const& x) { print_collection(out, x); return out; }
template<class T, size_t... I>
void print_tuple(std::ostream& out, T const& a, std::index_sequence<I...>);
template<class... A>
std::ostream& operator<<(std::ostream& out, std::tuple<A...> const& x) {
print_tuple(out, x, std::index_sequence_for<A...>{});
return out;
}
template<class T, size_t... I>
void print_tuple(std::ostream& out, T const& a, std::index_sequence<I...>){
using swallow = int[];
out << '(';
(void)swallow{0, (void(out << (I == 0? "" : ", ") << std::get<I>(a)), 0)...};
out << ')';
}
template<class T>
void print_collection(std::ostream& out, T const& x) {
int f = 0;
out << '[';
for(auto const& i: x) {
out << (f++ ? "," : "");
out << i;
}
out << "]";
}
static inline void d1_impl_seq() { std::cerr << "}"; }
template <class T, class... V>
void d1_impl_seq(T const& t, V const&... v) {
std::cerr << t;
if(sizeof...(v)) { std::cerr << ", "; }
d1_impl_seq(v...);
}
static inline void d2_impl_seq() { }
template <class T, class... V>
void d2_impl_seq(T const& t, V const&... v) {
std::cerr << " " << t;
d2_impl_seq(v...);
}
#define D0(x) do { std::cerr << __FILE__ ":" << __LINE__ << ":" << __func__ << " " << x << std::endl; } while (0)
#define D1(x...) do { \
std::cerr << __LINE__ << " {" << #x << "} = {"; \
d1_impl_seq(x); \
std::cerr << std::endl << std::flush; \
} while(0)
#define D2(x...) do { \
std::cerr << "!"; \
d2_impl_seq(x); \
std::cerr << std::endl << std::flush; \
} while(0)
static inline void debug_impl_seq() {
std::cerr << "}";
}
namespace logger {
inline void json_() {}
template<typename Key, typename Value, typename... Rest>
void json_(const Key& key, const Value& value, const Rest&... rest)
{
std::cerr << "\"" << key << "\":\"" << value << "\"";
if (sizeof...(Rest) > 0) std::cerr << ",";
json_(rest...);
}
// example : json("key1", "foo", "key2", 3, "key", 4.0);
// {"key1":"foo","key2":"3","key":"4"}
template<typename... Args>
void json(const Args&... args)
{
#ifdef DEBUG
std::cerr << "{"; json_(args...); std::cerr << "}" << std::endl;
#endif
}
} // namespace logger
// ------------------------ DEBUG PRINT --------------------------
struct Timer {
const double LIMIT; // FIXME: 時間制限(s)
Timer() : LIMIT(0.95) { reset(); }
Timer(double limit) : LIMIT(limit) { reset(); }
chrono::system_clock::time_point start;
void reset() {
start = chrono::system_clock::now();
}
double get() {
auto end = chrono::system_clock::now();
return chrono::duration_cast<chrono::milliseconds>(end - start).count()/1000.0;
}
};
struct XorShift {
unsigned int x, y, z, w;
double nL[65536];
XorShift() { init(); }
void init()
{
x = 314159265; y = 358979323; z = 846264338; w = 327950288;
double n = 1 / (double)(2 * 65536);
for (int i = 0; i < 65536; i++) {
nL[i] = log(((double)i / 65536) + n);
}
}
inline unsigned int next() { unsigned int t=x^x<<11; x=y; y=z; z=w; return w=w^w>>19^t^t>>8; }
inline double nextLog() { return nL[next()&0xFFFF]; }
inline int nextInt(int m) { return (int)(next()%m); } // [0, m)
int nextInt(int min, int max) { return min+nextInt(max-min+1); } // [min, max]
inline double nextDouble() { return (double)next()/((long long)1<<32); } // [0, 1]
};
XorShift rng;
template <typename T>
inline void rough_shuffle(vector<T>& lv) {
int n = lv.size();
for (int i = n; i > 0; --i) {
int id = rng.nextInt(i);
swap(lv[id], lv[i-1]);
}
}
std::size_t calc_hash(std::vector<int> const& vec) {
std::size_t seed = vec.size();
for(auto& i : vec) {
seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
return seed;
}
#if 0
int main() {
// `#define DEGUB` が必要
json("key1", "foo", "key2", 1, "key3", 3.14);
Timer timer(0.45);
while (true) {
double t = timer.get(); // elapsed seconds
if (timer.LIMIT < t) break;
double diff = 1; // SAのdiff. 仮で1としているが実際は計算する
double startTemp = 30;
double endTemp = 10;
double T = startTemp + (endTemp-startTemp)*(t/timer.LIMIT);
if (diff >= T * rnd.nextLog()) {
// FIXME: 更新
}
}
}
#endif
#line 3 "util/marathon/simulated_annealing.cpp"
using namespace std;
// update(), calcScore(), revert(), write()を実装する
struct State {
double score = 0;
State() {}
double update(double progress) { return 0; } // FIXME: 状態を次状態に更新しスコアの差分を返す.
double calcScore() { return 0; } // FIXME: 現在の状態のスコアを返す.
void revert() {} // update()適用前の状態に戻す.
void write() {} // 現在の状態を出力する.
};
struct SASolver {
double startTemp = 30;
double endTemp = 10;
Timer timer = Timer(2.95);
State best;
SASolver() { init(); }
SASolver(double st, double et): startTemp(st), endTemp(et) { init(); }
SASolver(double st, double et, double limit): startTemp(st), endTemp(et), timer(limit) { init(); }
void init() {} // 初期化処理をここに書く
void solve(State &state) {
double t;
best = state;
int step = 0;
// best.write();
while ((t = timer.get()) < timer.LIMIT) // 焼きなまし終了時刻までループ
{
double T = startTemp + (endTemp - startTemp) * t / timer.LIMIT;
double progress = t/timer.LIMIT;
// assert(0 <= progress && progress <= 1);
for (int i = 0; i < 100; ++i) { // 時間計算を間引く
double diff = state.update(progress);
// 最初t=0のときは、スコアが良くなろうが悪くなろうが、常に次状態を使用
// 最後t=timer.LIMITのときは、スコアが改善したときのみ、次状態を使用
// スコアが良くなった or 悪くなっても強制遷移
double tr = T*rng.nextLog();
if (diff >= tr)
{
if (best.score < state.score) {
best = state;
D1(t, step, best.score);
// best.write();
}
}
else { state.revert(); }
++step;
}
}
D1(step, best.score);
}
};
#if 0
int main() {
State state; // 開始状態
SASolver s;
s.solve(state);
s.best.write();
}
#endif