kwm_t

kwm_tのメモ

焼きなましテンプレート

Tips 
#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;
}

ABC339

■A - TLD
はい
■B - Langton's Takahashi
実装面倒系。
■C - Perfect Bus
シュミレーションして最小が負になるなら補正
■D - Synchronized Players
dpをする
■E - Smooth Subsequence
セグ木
■F - Product Equality
解けるわけ無いだろこれと思ってboost使ったりしたが
複数modとったら通ってオイオイオイと思ったら正当らしい
■G - Smaller Sum
MergeSortTreeというらしい
ライブラリにしました。

ABC338

■A - Capitalized?
やる
■B - Frequency
やる
■C - Leftover Recipes
料理Aを作れる個数を全探索する
■D - Island Tour
どの橋を壊すと最短と比べてどれだけコストが掛かるかを考える
imosでいいが面倒なので遅延セグ木で
■E - Chords
典型90のNo17を引っ張ってくる
■F - Negative Traveling Salesman
ワーシャルフロイドを行い、頂点距離をすべて調べておき
巡回セールスマン問題
■G - evall
a + b * cを考える

AHC短期メモ

Tips

AHC短期メモ
解説記事を読んだ上での改善含むので自力ではない
■AtCoder Heuristic Contest 002
時間：004:00
概要：フィールド上を与えられた初期位置移動してポイント稼ぎ
perf：3512(1位)
やったこと：焼きなまし
初期解をdfsをすることで発見する
初期解をベースにし、初期解の中間地点の２箇所を選択する
選んだ２点を始点、終点としdfsを再度行う
これによって新たな解を生成し焼きなましを行う。

■AtCoder Heuristic Contest 004
時間：006:00
概要：文字列が大量に与えられる。その文字列を多く含む行列を作成する。
perf：2976(6位)
やったこと：山登り法
ひとまとめに出来る文字列は纏めたほうが効率良さそう。
しかし、高々１文字とかのために結合すると自由度が減るだけなのでルールを設ける必要がある。
最低4文字とか。
文字列の連結は乱数を使用し、山登りのたびに行う。

■AtCoder Heuristic Contest 005
時間：004:00
概要：グリッドが与えられる、全ての移動可能マスが見えるような最短コストの経路を作れ
perf：3578(1位)
やったこと：kick+山登り
まず、交差点と道を全列挙する
すべての道に一度は訪れる必要があり、道から道に移動するためには
交差点から交差点に移動する。
経路はvector>で管理できる
1.山登り
経路を１つ消して、適当に挿入する
2.kick
経路から複数消して、適当に挿入する
1だけだと局所解にすぐハマるので、2で大幅な変更を定期的に行う。

■AtCoder Heuristic Contest 006
時間：004:00
概要：配達をしろ
perf：2996(4位)
やったこと：焼きなまし
貪欲で初期解を生成する
経路を１つ消して、適当に挿入する。挿入する候補は5つ程度試す。
これだけだと局所解にハマる可能性があるので2-optもたまに行う。

■AtCoder Heuristic Contest 007
時間：004:00
概要：オンラインで最小全域木を作れ
perf：2817(8位)
やったこと：モンテカルロ法
採用するか、採用しないか
採用しないならどの長さのものをかわりに採用することになり
コストがどれぐらいかかるかをかをシミュレーションする

■AtCoder Heuristic Contest 009
時間：004:00
概要：確率DPぽいもの
perf：3025(4位)
やったこと：焼きなまし
ランダム初期解を適当に作って、焼きなまし

■AtCoder Heuristic Contest 010
時間：004:00
概要：閉路を２つ作る
perf：2922(4位)
やったこと：焼きなまし
基本的にはAHC002とほぼ同じ。
実装がHard

■AtCoder Heuristic Contest 012
時間：004:00
概要：ケーキを切り刻んで分ける
perf：2998(4位)
やったこと：焼きなまし
初期解は縦横均等に切るところから始める。
差分計算をアルゴで培ったテクで頑張る

■AtCoder Heuristic Contest 015
時間：004:00
概要：果物を塊にしろ
perf：3043(4位)
やったこと：モンテカルロ法
ルールベースモンテカルロというらしい

■AtCoder Heuristic Contest 020
時間：004:00
概要：放送局を選択して全ての住民に配信しろ
perf：2921(6位)
やったこと：やきなまし
初期状態を各頂点に最も近い頂点におまかせした状態にする
そこから10頂点の出力を0にして同じことを繰り返す。
部分グラフの最小全域木みたいなのは頂点数が少ないので毎回やってもしれてる

■AtCoder Heuristic Contest 021
時間：004:00
概要：ピラミットをきれいにしろ
perf：3513(1位)
やったこと：
eijirouさんの提出を全部読みました
二重連鎖木の上でビームサーチをする

■AtCoder Heuristic Contest 024
時間：004:00
概要：地図をグラフとして同型にする
perf：2506(18位)
やったこと：
行を削って、適当に書き換えてコピーして消しての山登り

■AtCoder Heuristic Contest 026
時間：004:00
概要：ダンボールを運び出す
perf：3001(3位)
やったこと：
賢い貪欲をして、ビームサーチをする
ビームサーチがほとんど回らないが十分に効果がある

■AtCoder Heuristic Contest 028
時間：004:00
概要：部分文字列をいい感じに
perf：2873(8位)
やったこと：
toamさんの提出を全部読みました
ビームサーチをする

■AtCoder Heuristic Contest 032
時間：004:00
概要：Mod Stamp
perf：2660(18位)
やったこと：
貪欲が強いので、それをビームサーチにする
最後は時間の限り全探索をする
asi1024さんの実装をパクリ

■TOYOTA Programming Contest 2023 Summer final
時間：003:50
概要：コンテナを詰めて運び出す
perf：2834(5位)
モンテカルロシュミレーションをする

ARC170

■A - Yet Another AB Problem
貪欲にペアを決めていく
■B - Arithmetic Progression Subsequence
左端を固定したとき最低どこまで伸ばせば等差数列が作れるかを考える
■C - Prefix Mex Sequence
これ解けないの駄目
dp[i][j]:=iまでみた、j種類使ったでdp