Submission #63893180

---

Source Code Expand

/*
	[解法の説明]
	1. 基本的な方針
	- 社員 i にちょうど T[i] 回掃除当番が回ってくると仮定する
	- このとき、社員 a[i], b[i] に T[i]/2 回掃除当番が渡る、と考えらえる
	- したがって、(a[j], b[j] = i となるものに対する T[j]/2 の合計) ができるだけ T[i] に近くなれば良い
	- この "誤差" をできるだけ小さくする a[i], b[i] を決めることを考える
	2. "ビンパッキング問題" のような問題としてとらえる
	- 結局 1. で述べた問題は以下の問題になる
	  - N 個のビンがあって、それぞれ容量 T[0], T[1], ..., T[N-1] である
	  - アイテムが 2N 個あって、それぞれサイズ T[0]/2, T[0]/2, T[1]/2, T[1]/2, ..., T[N-1]/2, T[N-1]/2 である
	  - すべてのアイテムをビンに入れるとき、各ビンの |容量 - 入れたアイテムのサイズの合計| の総和を最小化する
	- これだと、ビン i にサイズ T[i]/2, T[i]/2 のアイテムを入れるのが最適になる
	  - しかし、この解では社員 0 がずっと掃除当番をやることになってしまう
	  - そのため、ビン i にはサイズ T[i]/2 のアイテムを入れてはいけない、という制約を入れた問題を解くことにする
	3. 山登り法で最適化する
	- 適当な初期解から始める
	- 以下の状態遷移を行って解の改善を試みる
	  - 2 つのビンを選び、その中のアイテムを組み替える、という変更を行う
	  - 誤差がより小さくなったら、変更を採用する
	- 改善できなくなる or 実行時間制限を過ぎる まで改善を繰り返す
	- 各ビンには平均 2 個程度しかアイテムがないので、組み替えの方法は全探索できる
	- 平均計算量 O(1) で改善できるかが判定でき、スコアを平均計算量 O(1) で差分更新できる
	4. 山登り法の工夫
	- 焼きなまし法をするとできるが、ここでは別のアプローチを考える
	- 反復局所探索法のアプローチ
	  [1] 2 つのビンの組を全探索して、その中で改善できるものを探す
	  [2] N(N-1)/2 通りのどれでも誤差が改善しなかったら (局所解)、以下の kick 操作を行う
	    - アイテムを 1 つランダムに選んで、それを別のビンに移し替える
	  [3] 局所解に到達するたびに実際のスコアを計算する
	- 時には誤差と比べて実際のスコアが低くなることがあるが、これは手順 [3] で実際のスコアを何回も計算するので対処できる
	- 手順 [1] から [3] までのループは、実行時間制限 2 秒では 100 回程度回る
	- 単純な誤差ではなく、2 乗誤差を最小化する
*/

#include <bits/stdc++.h>
using namespace std;

const int INF = 1012345678;

namespace myrandom {
	uint64_t seed = 1234567891234567891;
	uint64_t xorshift64() {
		seed ^= seed << 13;
		seed ^= seed >> 7;
		seed ^= seed << 17;
		return seed;
	}
	// l 以上 r 未満のランダムな整数を返す関数
	int64_t next_int(int64_t l, int64_t r) {
		int64_t z = xorshift64() % (r - l);
		return l + z;
	}
};

// 社員を表す構造体: a[i], b[i] を表す
class person {
public:
	int a, b;
	person() : a(-1), b(-1) {}
	person(int a_, int b_) : a(a_), b(b_) {}
};

// 求めた答えのスコアを計算する関数
int get_score(int N, int L, const vector<int>& T, const vector<person>& plan) {
	vector<int> count(N, 0);
	int cur = 0;
	for (int i = 0; i < L; i++) {
		if (count[cur] % 2 == 0) {
			cur = plan[cur].a;
		} else {
			cur = plan[cur].b;
		}
		count[cur] += 1;
	}
	int score = 2 * L;
	for (int i = 0; i < N; i++) {
		score -= abs(count[i] - T[i]);
	}
	return score;
}

vector<person> solver(int N, int L, const vector<int> T) {
	// step #1. ビンに入れるアイテムの大きさを計算
	vector<int> X(N * 2);
	for (int i = 0; i < N; i++) {
		X[i * 2 + 0] = (T[i] + 1) / 2;
		X[i * 2 + 1] = (T[i] + 0) / 2;
	}

	// step #2. 山登り法の準備
	const int CAPACITY = 5;
	vector<int> G(N * 2);
	vector<int> C(N);
	vector<int> S(N);
	vector<array<int, CAPACITY> > GL(N);
	for (int i = 0; i < N; i++) {
		fill(GL[i].begin(), GL[i].end(), -1);
	}
	for (int i = 0; i < N * 2; i++) {
		do {
			G[i] = myrandom::next_int(0, N);
		} while (G[i] == i / 2 || C[G[i]] == CAPACITY);
		S[G[i]] += X[i];
		GL[G[i]][C[G[i]]++] = i;
	}

	// step #3. ビン a, b を組み替えて改善できるかを全探索で判定する関数
	auto mixing = [&](int a, int b) -> bool {
		vector<int> V;
		V.reserve(C[a] + C[b]);
		int base_ca = 0, base_sa = 0;
		for (int i = 0; i < C[a]; i++) {
			if (GL[a][i] / 2 == b) {
				base_ca++;
				base_sa += X[GL[a][i]];
			} else {
				V.push_back(GL[a][i]);
			}
		}
		int base_cb = 0, base_sb = 0;
		for (int i = 0; i < C[b]; i++) {
			if (GL[b][i] / 2 == a) {
				base_cb++;
				base_sb += X[GL[b][i]];
			} else {
				V.push_back(GL[b][i]);
			}
		}
		int VS = V.size();
		vector<int> P(1 << VS);
		for (int i = 0; i < VS; i++) {
			for (int j = 0; j < (1 << i); j++) {
				P[j | (1 << i)] = P[j] + X[V[i]];
			}
		}
		int total = P[(1 << VS) - 1];
		pair<int, int> opt = {(S[a] - T[a]) * (S[a] - T[a]) + (S[b] - T[b]) * (S[b] - T[b]), -1};
		for (int i = 0; i < (1 << VS); i++) {
			int ca = base_ca + __builtin_popcount(i);
			int cb = base_cb + (VS - __builtin_popcount(i));
			if (ca <= CAPACITY && cb <= CAPACITY) {
				int sa = base_sa + P[i];
				int sb = base_sb + (total - P[i]);
				int loss = (sa - T[a]) * (sa - T[a]) + (sb - T[b]) * (sb - T[b]);
				opt = min(opt, {loss, i});
			}
		}
		if (opt.second == -1) {
			return false;
		}
		array<int, CAPACITY> gla, glb;
		fill(gla.begin(), gla.end(), -1);
		fill(glb.begin(), glb.end(), -1);
		int nca = 0;
		for (int i = 0; i < C[a]; i++) {
			if (GL[a][i] / 2 == b) {
				gla[nca++] = GL[a][i];
			}
		}
		int ncb = 0;
		for (int i = 0; i < C[b]; i++) {
			if (GL[b][i] / 2 == a) {
				glb[ncb++] = GL[b][i];
			}
		}
		for (int i = 0; i < VS; i++) {
			if ((opt.second >> i) & 1) {
				gla[nca++] = V[i];
				G[V[i]] = a;
			} else {
				glb[ncb++] = V[i];
				G[V[i]] = b;
			}
		}
		C[a] = nca;
		C[b] = ncb;
		GL[a] = gla;
		GL[b] = glb;
		S[a] = 0;
		for (int i = 0; i < nca; i++) {
			S[a] += X[gla[i]];
		}
		S[b] = 0;
		for (int i = 0; i < ncb; i++) {
			S[b] += X[glb[i]];
		}
		return true;
	};

	// step #4. 2 つのビンの組を全探索して、改善できるかを判定する関数
	auto find_improvement = [&]() -> bool {
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (abs(S[i] - T[i]) + abs(S[j] - T[j]) >= 2 && mixing(i, j)) {
					return true;
				}
			}
		}
		return false;
	};

	// step #5. 山登り法のメイン部分
	const double TIME_LIMIT = 1.9;
	time_t start_clock = clock();
	double time_ratio = 0.0;
	int best_score = -INF;
	vector<person> best_ans;
	int64_t loops = 0;
	while (true) {
		time_t cur_clock = clock();
		time_ratio = (cur_clock - start_clock) / (TIME_LIMIT * CLOCKS_PER_SEC);
		if (time_ratio >= 1.0) {
			break;
		}
		loops++;
		int64_t subloops = 0;
		while (find_improvement()) {
			subloops++;
		}
		int loss = 0;
		for (int i = 0; i < N; i++) {
			loss += abs(S[i] - T[i]);
		}
		vector<person> ans(N);
		for (int i = 0; i < N; i++) {
			ans[i] = person(G[i * 2 + 0], G[i * 2 + 1]);
		}
		int score = get_score(N, L, T, ans);
		cerr << "loop #" << loops << ": loss = " << loss << ", score = " << score << endl;	
		if (best_score < score) {
			best_score = score;
			best_ans = ans;
		}
		int a = myrandom::next_int(0, 2 * N);
		int b;
		do {
			b = myrandom::next_int(0, N);
		} while (b == G[a] || b == a / 2 || C[b] == CAPACITY);
		for (int i = 0; i < C[G[a]] - 1; i++) {
			if (GL[G[a]][i] == a) {
				GL[G[a]][i] = GL[G[a]][C[G[a]] - 1];
				GL[G[a]][C[G[a]] - 1] = -1;
				break;
			}
		}
		C[G[a]]--;
		S[G[a]] -= X[a];
		G[a] = b;
		GL[b][C[b]] = a;
		C[b]++;
		S[b] += X[a];
	}

	// 求めた答えを返す
	return best_ans;
}

int main() {
	// 入力
	int N, L;
	cin >> N >> L;
	vector<int> T(N);
	for (int i = 0; i < N; i++) {
		cin >> T[i];
	}

	// 答えを求める
	vector<person> ans = solver(N, L, T);

	// 出力
	for (int i = 0; i < N; i++) {
		cout << ans[i].a << ' ' << ans[i].b << endl;
	}

	return 0;
}

Submission Info

Judge Result