아인스트라세의 SW 블로그

이번 주말에는 아무것도 없는 줄 알았다가, 킥스타트 Remind 메일을 보고 토요일 밤에 구글 킥스타트가 있는것을 알고 참여했다.

구글 킥스타트는 구글 코드잼과 비슷한 대회인데, 다른 점은 각각의 라운드가 독립적인 하나 뿐이라는 것.

구글 코드잼은 예선전(Qualification Round)부터 Round 1,2,3이후 월드파이널 온사이트 대회로 넘어가는 방식으로 각 단계에서 사람수를 줄여가는 식의 서바이벌 방식의 대회라고 볼 수 있다.

킥스타트는 대학생들 대상으로 채용을 목적으로하는 대회로, 각각의 독립 라운드가 날짜별로 시간대별로 포진되어있다.

A,B,C 등등과 같은 방식으로 라운드를 구분한다.

따라서 하려는 라운드가 우리 한국시각으로는 새벽이더라도, 다른 한국시각으로 낮이나 저녁시간대인 다른 대회를 참여하면 되는 것이다.

결론부터 말하면 385등으로 총 3문제 중, 2.5문제를 풀었다.

뭔가 거의 다 푼 것 같아서 기분은 좋다.

3번째 문제 Hidden Test case는 날려먹엇는데, 풀이가 올라왔으니 차근차근 읽어봐야 할듯.

1번 문제 Book Reading은 대충 설명해보면, 배수를 찾는 문제이다.

1~N 페이지인 책 중 M개의 페이지가 찢겨져 나가있고, Q명의 독자는 각각 자신이 원하는 수의 배수에 해당하는 책 페이지만 읽는다 했을때, 독자들이 읽은 페이지의 총 개수를 구하면 된다.

책이 찢겨지지 않았다고 했을때는, 배수만 구해서 죄다 더해버리면 된다. 다만 찢긴 페이지를 어떻게 처리하냐가 관건이다.

Visible을 맞추기 위해서는 각각 독자별로 찢겨진 페이지에 얼마나 해당되는지만 체크하면 된다. Brute Force로 풀리는 크기로 N,M,Q가 1000이하이다.

Visible을 맞추기 위한 코드이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
ll solve() {
	int N, M, Q;
	scanf("%d%d%d", &N, &M, &Q);
	ll ans = 0;
	vector<int> torn(M);
	vector<int> reader(Q);
	for (int i = 0; i < M; i++) {
		cin >> torn[i];
	}
	for (int i = 0; i < Q; i++) {
		cin >> reader[i];
		ans += (ll)N / reader[i];
	}

	for (auto tt : torn) {
		for (auto rdr : reader) {
			if (tt % rdr == 0) {
				ans--;
			}
		}
	}
	return ans;
}
int main() {
	int tc;
	scanf("%d", &tc);
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: %lld\n", t, solve());
	}
}

Hidden을 맞추기 위해서는 좀 더 효율적인 코드가 필요하다.

찢겨진 페이지들을 소인수 분해한 뒤, 약수를 모두 다 구해서 해당 약수들에 cnt배열 값을 1씩 증가시키는 방식으로 독자를 쿼리를 최적화 해 보았다. 될지 안될지는 긴가 민가 했는데, 대충 통한듯.

소수들은 에라토스테네스의 채를 이용해서 구했다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define MAXN 100005
bool sieve[MAXN]; //false == prime
int cnt[MAXN];
vector<int> primes;
bool is_prime(int n) {
	if (n < 2) return false;
	if (n == 2) return true;
	for (int i = 2; i*i <= n; i++) {
		if (n % i == 0) return false;
	}
	return true;
}
void get_sieve() {
	sieve[0] = sieve[1] = true;
	for (int n = 2; n < MAXN; n++) {
		if (sieve[n] == false && is_prime(n)) {
			int base = n * 2;
			while (base < MAXN) {
				sieve[base] = true;
				base += n;
			}
		}
	}
	for (int i = 2; i < MAXN; i++) {
		if (sieve[i] == false) {
			primes.push_back(i);
		}
	}
}
void factorize(int n, vector<pair<int, int>>& factors) {
	while (n > 1) {
		for (int prime : primes) {
			if (prime > n) break;
			int cnt = 0;
			while (n % prime == 0) {
				n /= prime;
				cnt++;
			}
			if (cnt) {
				factors.push_back(make_pair(prime, cnt));
			}
		}
	}
}
void get_divisors(int n, vector<pair<int, int>>& factors, int k) {
	if (k == (int)factors.size()) {
		cnt[n]++;
		//cout << "got divisor = " << n << endl;
		return;
	}
	get_divisors(n, factors, k + 1);
	int exp = factors[k].second;
	for (int dec = 1; dec <= exp; dec++) {
		factors[k].second -= dec;
		n /= factors[k].first;
		get_divisors(n, factors, k + 1);
		factors[k].second += dec;
	}
	n *= pow(factors[k].first, exp);
	

}
ll solve() {
	memset(cnt, 0, sizeof(cnt));
	int N, M, Q;
	scanf("%d%d%d", &N, &M, &Q);
	ll ans = 0;
	vector<int> torn(M);
	vector<int> reader(Q);
	for (int i = 0; i < M; i++) {
		cin >> torn[i];
	}
	for (int i = 0; i < Q; i++) {
		cin >> reader[i];
		ans += (ll)N / reader[i];
	}
	for (int i = 0; i < M; i++) {
		vector<pair<int, int>> factors;
		factors.clear();
		factorize(torn[i], factors);
		get_divisors(torn[i], factors, 0);
	}

	for (auto rdr : reader) {
		ans -= cnt[rdr];
	}
	return ans;
}
int main() {
	get_sieve();
	int tc;
	vector<pair<int, int>> factors;

	scanf("%d", &tc);
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: %lld\n", t, solve());
	}
}

2번 문제는 약간 수학적인 문제같이 생겻는데, N개의 A숫자가 있고 숫자 M이 있을때

(A1 ^ k) + (A2 ^ k) + ... + (An ^ k) <= M을 만족하는 최대 k를 구하면 된다.

Visible은 모든 k에 대하여 다 해보고 최대 값을 구하는 완전탐색으로 풀린다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
ll A[1003];
int bitmap[20];
ll solve() {
	memset(bitmap, 0, sizeof(bitmap));
	ll ans = -1;
	int N;
	ll M;
	cin >> N >> M;
	ll sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	for (ll k = 0; k <= 1000; k++) {
		ll ss = 0;
		for (int i=0; i < N; i++) {
			ll& a = A[i];
			ss += (a^k);
			if (ss > M) break;
		}
		if (ss <= M) {
			ans = max(ans, k);
		}
	}
	return ans;
	
	
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: %lld\n", t, solve());
	}
}

Hidden은 좀더 효율적인 방법이 필요한데, 어차피 10^16이면 50비트 남짓이라는 것을 이용해서, 받는 A 숫자들을 비트별로 개수를 다 세어놓는다.

해당 비트 사용수가 과반수이면, 즉 N/2보다 크면, k의 해당 비트를 1로 해서 비트 들을 Inverse시켜주는 식으로 한번 전처리 한뒤,

M과 지금 다 합친 값과 여유분을 계산을 해서 , k의 가장 큰 bit를 xor해서 inverse해줘도 되는 경우 bit를 1로 set하는 식으로 구해보았다.

멍청하게 bitmap 배열을 20으로 잡아서(10^20을 생각) 런타임 에러가 막 났었는데 2^50이니 50이상 잡았어야 했다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
ll A[1003];
int bitmap[60];
ll solve() {
	memset(bitmap, 0, sizeof(bitmap));
	ll ans = 0;
	int N;
	ll M;
	cin >> N >> M;
	ll sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		sum += A[i];
		for (int j = 0; j <= 50; j++) {
			if (A[i] & (1LL << j)) {
				bitmap[j]++;
			}
		}
	}

	for (int i = 0; i <= 50; i++) {
		if (bitmap[i] * 2 >= N) {
			ans |= (1LL << i);
			sum += (1LL << i) * (N - bitmap[i] * 2);
		}
	}
	//if (sum > M) return -1LL;

	for (int i = 50; i >= 0; i--) {
		if ((1LL << i) & ans) continue;
		ll diff = M - sum; //여유분
		ll cost = (1LL << i) * (N - bitmap[i] * 2);
		if (cost <= diff) {
			ans |= (1LL << i);
			sum += cost;
		}
	}
	if (sum > M) return -1LL;
	return ans;

}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: %lld\n", t, solve());
	}
}

3번 문제는 교대근무를 하는 2명의 직원이 있고, 각 근무시간은 최소 한명이상 근무해야하며, 근무 시 얻는 Happiness를 합한 값이 각각 H를 넘는 경우의 수를 구하는 그런문제다.

문제를 딱 보고 어렵다 생각했는데 Visible N값이 12로 완전탐색을 조져도 될 것이라는 생각이 들었다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
ll A[22], B[22];
ll solve() {
	ll ans = 0;
	int N;
	ll H;
	cin >> N >> H;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}
	ll AH, BH;
	for (int bit = 1; bit < (1 << N); bit++) {
		AH = 0;
		//BH = 0;
		for (int i = 0; i < N; i++) {
			if (bit & (1 << i)) {
				AH += A[i];
			}
			
		}
		if (AH < H) continue;
		
		
		for (int bbit = 1; bbit < (1 << N); bbit++) {
			BH = 0;
			for (int i = 0; i < N; i++) {
				if (bbit & (1 << i)) {
					BH += B[i];
				}
			}
			if (BH < H) continue;
			if ((bit | bbit) != ((1 << N) - 1)) continue;
			ans++;
		}
		
	}
	return ans;
}
int main() {
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: %lld\n", t, solve());
	}
}

Hidden으로 N=20은 도저히 어떻게 해야할 지 생각이 안나서 스킵해놓은 상태이다. 이따가 풀이보고 공부해봐야겠다.