#953787 (C++14) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	e869120
提出日時	2024-02-23 15:51:14
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	835 ms / 1,000 ms
コード長	10,436 bytes
コンパイル時間	1,784 ms
コンパイル使用メモリ	118,676 KB
実行使用メモリ	220,704 KB
スコア	94,974,672
最終ジャッジ日時	2024-02-25 12:56:54
合計ジャッジ時間	37,521 ms
ジャッジサーバーID （参考情報）	judge11 / judge12
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	379 ms 220,704 KB
testcase_01	AC	785 ms 220,704 KB
testcase_02	AC	814 ms 220,704 KB
testcase_03	AC	815 ms 220,704 KB
testcase_04	AC	835 ms 220,704 KB
testcase_05	AC	814 ms 220,704 KB
testcase_06	AC	812 ms 220,704 KB
testcase_07	AC	813 ms 220,704 KB
testcase_08	AC	487 ms 220,704 KB
testcase_09	AC	332 ms 220,704 KB
testcase_10	AC	791 ms 220,704 KB
testcase_11	AC	614 ms 220,704 KB
testcase_12	AC	485 ms 220,704 KB
testcase_13	AC	479 ms 220,704 KB
testcase_14	AC	743 ms 220,704 KB
testcase_15	AC	806 ms 220,704 KB
testcase_16	AC	812 ms 220,704 KB
testcase_17	AC	813 ms 220,704 KB
testcase_18	AC	511 ms 220,704 KB
testcase_19	AC	713 ms 220,704 KB
testcase_20	AC	567 ms 220,704 KB
testcase_21	AC	572 ms 220,704 KB
testcase_22	AC	395 ms 220,704 KB
testcase_23	AC	509 ms 220,704 KB
testcase_24	AC	808 ms 220,704 KB
testcase_25	AC	654 ms 220,704 KB
testcase_26	AC	813 ms 220,704 KB
testcase_27	AC	812 ms 220,704 KB
testcase_28	AC	373 ms 220,704 KB
testcase_29	AC	681 ms 220,704 KB
testcase_30	AC	434 ms 220,704 KB
testcase_31	AC	812 ms 220,704 KB
testcase_32	AC	813 ms 220,704 KB
testcase_33	AC	390 ms 220,704 KB
testcase_34	AC	363 ms 220,704 KB
testcase_35	AC	813 ms 220,704 KB
testcase_36	AC	813 ms 220,704 KB
testcase_37	AC	398 ms 220,704 KB
testcase_38	AC	618 ms 220,704 KB
testcase_39	AC	632 ms 220,704 KB
testcase_40	AC	816 ms 220,704 KB
testcase_41	AC	727 ms 220,704 KB
testcase_42	AC	812 ms 220,704 KB
testcase_43	AC	417 ms 220,704 KB
testcase_44	AC	813 ms 220,704 KB
testcase_45	AC	611 ms 220,704 KB
testcase_46	AC	813 ms 220,704 KB
testcase_47	AC	812 ms 220,704 KB
testcase_48	AC	739 ms 220,704 KB
testcase_49	AC	788 ms 220,704 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <map>
#include <cmath>
#include <ctime>
#include <tuple>
#include <vector>
#include <algorithm>
using namespace std;

const long long MaxVal = 1000000000000000000LL;
const long long MinVal = 100000000000000000LL;
const long long Target = 500000000000000000LL;
long long N;
long long A[59], LA[59];
long long B[59], LB[59];
long long FinalScore = MaxVal;
vector<pair<int, int>> FinalAns;

// 終盤探索用
vector<int> backtrack;
vector<pair<vector<int>, int>> Possibility;
map<long long, bool> Possibility_Record;
int IndexCount = 0;
int Masks[1 << 20];
long long MaximumA[1 << 19], MaximumB[1 << 19];
long long MinimumA[1 << 19], MinimumB[1 << 19];
int ListIndex[4000][2009];
int ListCount[4000][2009];
tuple<int, int, int> List[4000][2009];
tuple<int, int, int> ListTemp[4000][2009];

// ========================================================================================================== 初期解探索
void init_dfs(int depth, vector<long long> ArrayA) {
	for (int i = 0; i < 4; i++) {
		if (Possibility_Record[ArrayA[i]] == false) {
			Possibility_Record[ArrayA[i]] = true;
			backtrack.push_back(i + 1);
			int hash_val = 0;
			for (int j = 0; j < backtrack.size(); j++) hash_val += (backtrack[j] << (4 * j));
			Possibility.push_back(make_pair(backtrack, hash_val));
			backtrack.pop_back();
		}
	}
	if (depth == 6) return;
	for (int i = 0; i < 4; i++) {
		for (int j = i + 1; j < 4; j++) {
			if (ArrayA[i] == ArrayA[j]) continue;
			vector<long long> ArrayC = ArrayA;
			long long avg1 = (ArrayC[i] + ArrayC[j]) / 2LL;
			ArrayC[i] = avg1;
			ArrayC[j] = avg1;
			backtrack.push_back(i + (j << 2));
			init_dfs(depth + 1, ArrayC);
			backtrack.pop_back();
		}
	}
}

void Initialize(int mask, vector<int> idx) {
	Masks[mask] = IndexCount;
	vector<long long> ArrayA(4, 0);
	vector<long long> ArrayB(4, 0);

	// Enumerate Part
	int cnt = 0;
	for (int i = 0; i < Possibility.size(); i++) {
		ArrayA[0] = A[idx[0]]; ArrayB[0] = B[idx[0]];
		ArrayA[1] = A[idx[1]]; ArrayB[1] = B[idx[1]];
		ArrayA[2] = A[idx[2]]; ArrayB[2] = B[idx[2]];
		ArrayA[3] = A[idx[3]]; ArrayB[3] = B[idx[3]];
		for (int j = 0; j < Possibility[i].first.size(); j++) {
			if (j + 1 == Possibility[i].first.size()) {
				int num = Possibility[i].first[j] - 1;
				ListIndex[IndexCount][(ArrayA[num] >> 49) + 1]++;
				ListTemp[IndexCount][cnt] = make_tuple(ArrayB[num] >> 41, ArrayA[num] >> 41, Possibility[i].second);
				cnt += 1;
			}
			else {
				int idxA = (Possibility[i].first[j] & 3);
				int idxB = (Possibility[i].first[j] >> 2);
				long long avgA = (ArrayA[idxA] + ArrayA[idxB]) >> 1;
				long long avgB = (ArrayB[idxA] + ArrayB[idxB]) >> 1;
				ArrayA[idxA] = avgA; ArrayB[idxA] = avgB;
				ArrayA[idxB] = avgA; ArrayB[idxB] = avgB;
			}
		}
	}

	// Add Part
	for (int i = 1; i <= 2000; i++) ListIndex[IndexCount][i] += ListIndex[IndexCount][i - 1];
	for (int i = 0; i <= 2000; i++) ListCount[IndexCount][i] = ListIndex[IndexCount][i];
	for (int i = 0; i < cnt; i++) {
		int idx = get<1>(ListTemp[IndexCount][i]) >> 8;
		List[IndexCount][ListCount[IndexCount][idx]] = ListTemp[IndexCount][i];
		ListCount[IndexCount][idx]++;
	}
}

// ========================================================================================================== 基本関数
long long GetScore(vector<int>& Order) {
	long long TotalScore1 = (A[1] >> (N - 1));
	long long TotalScore2 = (B[1] >> (N - 1));
	for (int i = 0; i < N - 1; i++) TotalScore1 += (A[Order[i]] >> (N - 1 - i));
	for (int i = 0; i < N - 1; i++) TotalScore2 += (B[Order[i]] >> (N - 1 - i));
	return max(abs(Target - TotalScore1), abs(Target - TotalScore2));
}

long long GetActual(vector<pair<int, int>>& Operation) {
	for (int i = 1; i <= N; i++) LA[i] = A[i];
	for (int i = 1; i <= N; i++) LB[i] = B[i];
	for (int i = 0; i < Operation.size(); i++) {
		int idx1 = Operation[i].first;
		int idx2 = Operation[i].second;
		long long avgA = (LA[idx1] + LA[idx2]) / 2LL;
		long long avgB = (LB[idx1] + LB[idx2]) / 2LL;
		LA[idx1] = avgA; LA[idx2] = avgA;
		LB[idx1] = avgB; LB[idx2] = avgB;
	}
	long long gosa = max(abs(Target - LA[1]), abs(Target - LB[1]));
	return gosa;
}

long double Randouble() {
	double s = 0.0, t = 1.0;
	for (int i = 0; i < 3; i++) {
		t /= 1024.0;
		s += 1.0 * (rand() % 1024) * t;
	}
	return s;
}

// ========================================================================================================== 序盤・中盤探索
vector<int> GetBestOrder() {
	vector<int> Order(N - 1, 0);
	vector<int> BestOrder(N - 1, 0);
	for (int i = 0; i < N - 1; i++) Order[i] = i + 2;

	// 準備
	long long CurrentScore = GetScore(Order);
	long long BestScore = CurrentScore;
	int StartTime = clock();

	// 焼きなまし法開始
	while (clock() - StartTime <= 10 * CLOCKS_PER_SEC / 100) {
		int idx1 = rand() % (N - 1);
		int idx2 = rand() % (N - 1);
		swap(Order[idx1], Order[idx2]);
		long long CandScore = GetScore(Order);
		double Diff = log10(CurrentScore) - log10(CandScore);
		if (Randouble() < exp(Diff / 0.17)) {
			if (BestScore > CandScore) {
				BestScore = CandScore;
				BestOrder = Order;
			}
			CurrentScore = CandScore;
		}
		else {
			swap(Order[idx1], Order[idx2]);
		}
	}
	return BestOrder;
}

// ========================================================================================================== 終盤探索
vector<int> CurrentOrder;
int StartTime;
int NumLoops;

void dfs(int depth, int mask, long long CurrentA, long long CurrentB, vector<int>& Cand, vector<int>& PostOrder) {
	if ((NumLoops & 1023) == 0) {
		if (clock() - StartTime > 80 * CLOCKS_PER_SEC / 100) return;
	}
	NumLoops += 1;
	if (depth == 4) {
		int idx = Masks[(1 << Cand.size()) - 1 - mask];
		int Remain = max(0LL, min(1999LL, (Target - CurrentA) / 256LL));
		for (int pos = ListIndex[idx][Remain]; pos < ListIndex[idx][Remain + 1]; pos++) {
			long long gosaA = abs(Target - (CurrentA + 1LL * get<1>(List[idx][pos])));
			long long gosaB = abs(Target - (CurrentB + 1LL * get<0>(List[idx][pos])));
			if (max(gosaA, gosaB) > FinalScore + 100LL) continue;

			// 手順の計算
			vector<int> MaskOrd;
			vector<pair<int, int>> Final;
			for (int i = 0; i < Cand.size(); i++) {
				if (!((mask >> i) & 1)) MaskOrd.push_back(Cand[i]);
			}
			for (int i = 0; i < 8; i++) {
				int val1 = (get<2>(List[idx][pos]) >> (4 * i)) & 15;
				int val2 = (get<2>(List[idx][pos]) >> (4 * i + 4)) & 15;
				if (val2 == 0) {
					Final.push_back(make_pair(1, MaskOrd[val1 - 1]));
					for (int j = CurrentOrder.size() - 1; j >= 0; j--) Final.push_back(make_pair(1, CurrentOrder[j]));
					for (int j = 0; j < PostOrder.size(); j++) Final.push_back(make_pair(1, PostOrder[j]));
					break;
				}
				else Final.push_back(make_pair(MaskOrd[val1 & 3], MaskOrd[val1 >> 2]));
			}

			// スコアの計算
			long long Score = GetActual(Final);
			if (FinalScore > Score) {
				FinalScore = Score;
				FinalAns = Final;
			}
		}
		return;
	}

	// 枝刈り探索
	int dep = PostOrder.size() + CurrentOrder.size() + 1;
	int cur = (1 << Cand.size()) - 1 - mask;
	for (int i = 0; i < Cand.size(); i++) {
		if ((mask >> i) & 1) continue;
		long long NextA = CurrentA + (A[Cand[i]] >> dep);
		long long NextB = CurrentB + (B[Cand[i]] >> dep);
		if (NextA < Target - MaximumA[cur - (1 << i)] || NextA > Target - MinimumA[cur - (1 << i)]) continue;
		if (NextB < Target - MaximumB[cur - (1 << i)] || NextB > Target - MinimumB[cur - (1 << i)]) continue;
		CurrentOrder.push_back(Cand[i]);
		dfs(depth - 1, mask + (1 << i), NextA, NextB, Cand, PostOrder);
		CurrentOrder.pop_back();
	}
}

int main() {
	// Step 1. 入力
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i] >> B[i];

	// Step 2. 初期化
	vector<long long> Random(4, 0);
	Random[0] = 123456789123456789;
	Random[1] = 314159265358979323;
	Random[2] = 869120869120869120;
	Random[3] = 999999999999999999;
	init_dfs(0, Random);

	// Step 3. 焼きなまし法
	StartTime = clock();
	vector<int> BestOrder = GetBestOrder();

	// Step 4. 終盤探索 (初期化)
	for (int i = 0; i < 18; i++) {
		for (int j = i + 1; j < 18; j++) {
			for (int k = j + 1; k < 18; k++) {
				for (int l = k + 1; l < 18; l++) {
					Initialize((1 << i) + (1 << j) + (1 << k) + (1 << l), vector<int>{BestOrder[i], BestOrder[j], BestOrder[k], BestOrder[l]});
					IndexCount += 1;
				}
			}
		}
	}
	vector<pair<long long, int>> SortedA;
	vector<pair<long long, int>> SortedB;
	for (int i = 0; i < 18; i++) SortedA.push_back(make_pair(A[BestOrder[i]], i));
	for (int i = 0; i < 18; i++) SortedB.push_back(make_pair(B[BestOrder[i]], i));
	sort(SortedA.begin(), SortedA.end());
	sort(SortedB.begin(), SortedB.end());
	for (int i = 0; i < (1 << 18); i++) {
		int cntA = 0;
		int cntB = 0;
		MinimumA[i] = -10000;
		MinimumA[i] = -10000;
		MaximumA[i] = 10000;
		MaximumB[i] = 10000;
		for (int j = 17; j >= 0; j--) {
			if ((i >> SortedA[j].second) & 1) {
				if (cntA <= 3) MinimumA[i] = (SortedA[j].first >> 41);
				else MinimumA[i] += (SortedA[j].first >> (44 - cntA));
				cntA += 1;
			}
			if ((i >> SortedB[j].second) & 1) {
				if (cntB <= 3) MinimumB[i] = (SortedB[j].first >> 41);
				else MinimumB[i] += (SortedB[j].first >> (44 - cntB));
				cntB += 1;
			}
		}
		cntA = 0;
		cntB = 0;
		for (int j = 0; j <= 17; j++) {
			if ((i >> SortedA[j].second) & 1) {
				if (cntA <= 3) MaximumA[i] = (SortedA[j].first >> 41);
				else MaximumA[i] += (SortedA[j].first >> (44 - cntA));
				cntA += 1;
			}
			if ((i >> SortedB[j].second) & 1) {
				if (cntB <= 3) MaximumB[i] = (SortedB[j].first >> 41);
				else MaximumB[i] += (SortedB[j].first >> (44 - cntB));
				cntB += 1;
			}
		}
	}

	// Step 5. 終盤探索
	for (int depth = 6; depth <= 18; depth++) {
		long long SumA = (A[1] >> (N - 4));
		long long SumB = (B[1] >> (N - 4));
		for (int i = depth; i < N - 1; i++) SumA += (A[BestOrder[i]] >> (N - 1 - i));
		for (int i = depth; i < N - 1; i++) SumB += (B[BestOrder[i]] >> (N - 1 - i));
		vector<int> Vec1;
		vector<int> Vec2;
		for (int i = 0; i < depth; i++) Vec1.push_back(BestOrder[i]);
		for (int i = depth; i < N - 1; i++) Vec2.push_back(BestOrder[i]);
		dfs(depth, 0, SumA, SumB, Vec1, Vec2);
		// printf("% 3d% 9lld% 9d% 7d\n", depth, min(99999999LL, FinalScore), NumLoops, clock() - StartTime);
		if (clock() - StartTime > 80 * CLOCKS_PER_SEC / 100) break;
	}

	// Step 6. 出力
	cout << FinalAns.size() << endl;
	for (pair<int, int> ans : FinalAns) cout << ans.first << " " << ans.second << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード