#273404 (C++11) No.719 Coprime

提出ソース

結果

問題	No.719 Coprime
ユーザー	startcpp
提出日時	2018-07-17 19:27:23
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	4,695 bytes
コンパイル時間	938 ms
コンパイル使用メモリ	70,316 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-05-04 18:18:51
合計ジャッジ時間	3,128 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	3 ms 5,376 KB
testcase_22	AC	3 ms 5,376 KB
testcase_23	AC	3 ms 5,376 KB
testcase_24	AC	3 ms 5,376 KB
testcase_25	AC	4 ms 5,376 KB
testcase_26	AC	5 ms 5,376 KB
testcase_27	AC	6 ms 5,376 KB
testcase_28	AC	7 ms 5,376 KB
testcase_29	AC	10 ms 5,376 KB
testcase_30	AC	13 ms 5,376 KB
testcase_31	AC	15 ms 5,376 KB
testcase_32	AC	18 ms 5,376 KB
testcase_33	AC	21 ms 5,376 KB
testcase_34	AC	22 ms 5,376 KB
testcase_35	AC	34 ms 5,376 KB
testcase_36	AC	40 ms 5,376 KB
testcase_37	AC	47 ms 5,376 KB
testcase_38	AC	54 ms 5,376 KB
testcase_39	AC	80 ms 5,376 KB
testcase_40	AC	88 ms 5,376 KB
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	WA	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	WA	-
testcase_55	WA	-
testcase_56	WA	-
testcase_57	WA	-
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-

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

ソースコード

raw source code

//嘘解法。以下のパターンを試し、最もよかったものを取る。
//1. N ≦ 45なら、全探索
//2. N,N-1,…,2の順で見ていき取れるなら取る。
//3. 2,3,…,Nの順で見ていき取れるなら取る。
//4. 最大素因数がp_iの数のうち取ることができる最も大きいものを取る、をi=k,…,2,1の順でおこなう。
//kはN以下の素数の個数 。p_iはi番目に小さい素数。(p_1 = 2)
//5. 最大素因数がp_iの数のうち取ることができる最も大きいものを取る、をi=1,2,3…の順でおこなう。
//6. 素数だけを取る。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

//0. 最大素因数の表を作る
vector<int> primes;
vector<vector<int>> numbers;

void setPrimes(int n) {
	int i, j;
	vector<bool> isprime(n + 1);
	
	isprime[0] = isprime[1] = false;
	for (i = 2; i <= n; i++) isprime[i] = true;
	
	for (i = 2; i <= n; i++) {
		if (isprime[i]) {
			for (j = i * 2; j <= n; j += i) {
				isprime[j] = false;
			}
		}
	}
	
	for (i = 2; i <= n; i++) if(isprime[i]) primes.push_back(i);
	
	numbers.resize(primes.size());
	for (i = 2; i <= n; i++) {
		for (j = primes.size() - 1; j >= 0; j--) {
			if (i % primes[j] == 0) {
				numbers[j].push_back(i);
				break;
			}
		}
	}
}

//1. 全探索(2,3,…,Nの順で取る・取らないを決める）
int dfs(int val, int n, long long taked) {
	if (val > n) return 0;
	
	int i, res, ret = 0;
	for (i = 2; i < val; i++) {
		if ((taked >> i) % 2 == 0) continue;
		if (gcd(i, val) != 1) break;
	}
	if (i == val) {	//取る
		res = val + dfs(val + 1, n, taked + (1LL << val));
		ret = max(ret, res);
	}
	res = dfs(val + 1, n, taked);
	ret = max(ret, res);
	return ret;
}

//2. N,N-1,…,2の順で見ていき、取れるなら取る
int greedy_bigTake(int n) {
	int i, j;
	vector<bool> taked(n + 1, false);
	int ret = 0;
	
	for (i = n; i >= 2; i--) {
		for (j = i + 1; j <= n; j++) {
			if (taked[j] && gcd(j, i) != 1) break;
		}
		if (j > n) {	//iを取れる
			taked[i] = true;
			ret += i;
		}
	}
	return ret;
}

//3. 2,3,…,Nの順で見ていき、取れるなら取る
int greedy_smallTake(int n) {
	int i, j;
	vector<bool> taked(n + 1, false);
	int ret = 0;
	
	for (i = 2; i <= n; i++) {
		for (j = 2; j < i; j++) {
			if (taked[j] && gcd(j, i) != 1) break;
		}
		if (j >= i) {	//iを取れる
			taked[i] = true;
			ret += i;
		}
	}
	return ret;
}

//4. 最大素因数がp_iの数のうち取ることができる最も大きいものを取る、をi=k,…,2,1の順でおこなう。
//kはN以下の素数の個数 。p_iはi番目に小さい素数。(p_1 = 2)
int greedy_bigNumbers(int n) {
	int i, j, k;
	vector<int> taked;
	int ret = 0;
	
	for (i = numbers.size() - 1; i >= 0; i--) {
		for (j = numbers[i].size() - 1; j >= 0; j--) {
			int val = numbers[i][j];
			for (k = 0; k < taked.size(); k++) {
				if (gcd(val, taked[k]) != 1) break;
			}
			if (k == taked.size()) {
				taked.push_back(val);
				ret += val;
			}
		}
	}
	return ret;
}

//5. 最大素因数がp_iの数のうち取ることができる最も大きいものを取る、をi=1,2,3…の順でおこなう。
int greedy_smallNumbers(int n) {
	int i, j, k;
	vector<int> taked;
	int ret = 0;
	
	for (i = 0; i < numbers.size(); i++) {
		for (j = numbers[i].size() - 1; j >= 0; j--) {
			int val = numbers[i][j];
			for (k = 0; k < taked.size(); k++) {
				if (gcd(val, taked[k]) != 1) break;
			}
			if (k == taked.size()) {
				taked.push_back(val);
				ret += val;
			}
		}
	}
	return ret;
}

//6. 素数だけを取る。(primes…n以下の素数の集合）
int greedy_primeTake(int n) {
	int i;
	int ret = 0;
	for (i = 0; i < primes.size(); i++) ret += primes[i];
	return ret;
}

signed main() {
	bool debug_mode = false;
	int n;
	cin >> n;
	
	setPrimes(n);
	
	int ans = 0, res;
	
	if (n <= 45) {
		res = dfs(2, n, 0);
		if (debug_mode) cout << "score[dfs] = " << res << endl;
		ans = max(ans, res);
	}
	
	res = greedy_bigTake(n);
	if (debug_mode) cout << "score[greedy_bigTake] = " << res << endl;
	ans = max(ans, res);
	
	res = greedy_smallTake(n);
	if (debug_mode) cout << "score[greedy_smallTake] = " << res << endl;
	ans = max(ans, res);
	
	res = greedy_bigNumbers(n);
	if (debug_mode) cout << "score[greedy_bigNumbers] = " << res << endl;
	ans = max(ans, res);
	
	res = greedy_smallNumbers(n);
	if (debug_mode) cout << "score[greedy_smallNumbers] = " << res << endl;
	ans = max(ans, res);
	
	res = greedy_primeTake(n);
	if (debug_mode) cout << "score[greedy_primeTake] = " << res << endl;
	ans = max(ans, res);
	
	cout << ans << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード