올해 킥스타트 B라운드는 주말 아침8시에 시작을 해서, 어째저째 술먹고 새벽에 퍼질러 자다가 비몽사몽한상태에서 용캐 일어나서 한번 풀어보았다.

 

코드잼 1Round에서 엄청 발렸던 기분을 Kickstart를 풀면서 조금 달래주려 했는데, 확실히 Kickstart는 Codejam에 비해서는 난이도가 낮은 듯 한 느낌을 많이 받았다.

 

총 4문제가 나왔고, 예전에는 Large set은 Full feedback을 안주고 Hidden verdict형식이었는데, 이번에는 다 Visible verdict로 진행이 되었다.

 

Bike Tour

봉우리 갯수를 새는 문제이다. for loop로 순회하면서 좌우 값을 봐서 그 보다크면 봉우리로 갯수를 카운트 하면 되는 간단한 문제이다.

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

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'

int arr[105];
void solve() {
	int n;
	int ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	for (int i = 1; i < n - 1; i++) {
		if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) ans++;
	}
	cout << ans << endl;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

Bus Routes

버스가 오는 시간 주기를 알때, 마지막 버스를 탈 수 있는 가장 늦은 시간을 구하는 문제이다. 배수개념으로 접근하면 될 것 같은데, 파라메트릭 서치를 이용하면 간단하게 풀 수 있다. 쿼리를 바이너리 서치로 확인하는건데, 쿼리 확인시에는 floor(v/x) * x를 해서 가장 가까운 배수를 찾아내면 된다.

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

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'

ll a[1005];
int n;
ll d;
bool q(ll v) {
	
	for (int i = 0; i < n; i++) {
		ll x = a[i];
		v = max(v, (v + x - 1) / x * x);
		if (v > d)
			return false;
	}
	return true;
}
void solve() {
	ll l, r;
	l = 1;
	//r = (ll)1e12;
	cin >> n >> d;
	r = d;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	while (l < r) {
		ll m = (l + r + 1) / 2;
		//printf("%lld %lld %lld\n", l, r, m);
		if (q(m)) {
			l = m;
		}
		else {
			r = m - 1;
		}
	}
	cout << l << endl;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

Robot Path Decoding

문제 내용 자체보다는, Operation code 파싱이 더 어렵다. (를 만나면 같은 depth의 )의 인댁스를 찾아서 재귀로 짜보려다가 //(O(N^2)//)인데 TLE안나려나 궁금했다가 그냥 스택으로 짜는게 더 나을거 같아서 머리를 쥐어 짜면서 스택으로 파서를 만들어 보았다. 생각보다 파서가 간단하게 만들어 졌던 것 같다. 좌표계가 wrap-around되므로 그 부분을 처리해주는 함수를 따로 만들어서 썼다.

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

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
const ll MOD = 1e9;
ll nor(ll v) {
	if (v < 0)
		v += MOD;
	if (v >= MOD)
		v %= MOD;
	return v;
}
struct Data {
	int op;
	ll x, y;
	void add(struct Data& rhs) {
		x += rhs.x;
		y += rhs.y;
		x = nor(x);
		y = nor(y);
	}
	void mult(int v) {
		x *= v;
		y *= v;
		x = nor(x);
		y = nor(y);
	}
};
Data calc(char c) {
	if (c == 'N') {
		return { 0, -1, 0 };
		//return make_pair(-1, 0);
	}
	else if (c == 'S') {
		return { 0, 1, 0 };
		//return make_pair(+1, 0);
	}
	else if (c == 'W') {
		return { 0, 0, -1 };
		//return make_pair(0, -1);
	}
	else if (c == 'E') {
		return { 0, 0, 1 };
		//return make_pair(0, +1);
	}
	else {
		assert(false);
	}
}

void solve() {
	string s;
	cin >> s;
	//ll x, y;
	//x = y = 0;
	stack<Data> ss;
	ss.push({ 0, 0, 0 });
	for (int i = 0; i < s.length(); i++) {
		char c = s[i];
		if (c >= '0' && c <= '9') {
			ss.push({ c - '0', 0, 0 });
			ss.push({ 0, 0, 0 });
		}
		else if (c == ')') {
			Data operand = ss.top(); ss.pop();
			Data mult = ss.top(); ss.pop();
			Data prev = ss.top(); ss.pop();
			operand.mult(mult.op);
			prev.add(operand);
			ss.push(prev);
		}
		else if (c >= 'A' && c <= 'Z') {
			Data cur = ss.top(); ss.pop();
			Data delta = calc(c);
			cur.add(delta);
			ss.push(cur);
		}
	}
	ll y = (ss.top().y + 1);
	ll x = (ss.top().x + 1);
	cout << y << ' ' << x << endl;
	while (ss.size()) ss.pop();
	//x++; y++;
	//cout << y << ' ' << x << endl;

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

Wandering Robot

kickstart때는 못풀어서 나중에 Analysis랑 남의 코드들을 보고 업솔빙을 좀 했다. 아이디어 자체는 대충 냈었는데, 어차피 디테일부분을 못따라가서 구현법 팁을 알았어도 당시에는 못 풀었을 듯 하다.

1등한 사람의 코드도 좀 참고를 하고 이해안가는 부분을 동기형한테는 물어보고 해서 도움을 꽤 받았다.(사실 아직도 100%는 이해 안 된 것 같기도하고...)

 

이항계수를 구하는 부분에서 Precision Error가 많이 날 것 같았는데 결국 요구하는 정확도가 //(10^{-5}//)정도로 낮은 수준이기도 하고, log로 축소시켜서 계산한 뒤 다시 역로그(exp함수)로 되돌려서 계산하는 부분들이 신박했다.

 

근데 여기서 좀 쟁점이 되는 부분은 대각선이 딱 맞아떨어지지 않는 경우가 쟁점인데, 아래 그림을 보자.

참고로 아래 문단에서 구한다고 하는 것은 시작점을 //((0,0)//)라고 가정하고 도착지점 좌표를 //((x,y)//)라고 가정하면

//(\frac{1}{2}^{x+y}*\binom{x+y}{x}//)를 의미한다. 이를 //(f(x,y)//)라고 하자.

파란색들은 독립적으로 되기 때문에 각자 구해서 더하면 되는데, 파란색 위쪽에 비어있는 칸으로 가는 경우는 쟁점이 된다.

오른쪽 끝에 다다른 경우 무조건 아래로만 가기 때문에 해당 부분에 대한 내용들도 더해줘야 하는데, 이는 빨간색 박스에 도달하는 경우(실제로는 벽을 뚫을 순 없지만 뚫을 수 있다고 가정할 시)를 더해주면 된다. 어차피 벽을 뚫는경우 아래로 내려가는걸로 취급하면 되므로 그러하다.

 

근데 1등 코드를 확인해보면 노란색으로 가는 확률(f(노랑칸))에 1/2를 곱해서 더해버리는 식이다. 사실 노랑색 바로 아래 파란색(C) 입장에서는 바로 위 노란색(B)에서 아래로 1/2확률로 내려오는 것만 포함되어 있는데, 바로 위 노란색(B)에서 오른쪽으로 가는 경우의 확률도 더해져야 하므로 노란색으로 도달하는 확률에 1/2를 곱해서 더한다.

그리고 마찬가지로 가장 아래 노란색(B)으로 가는 확률은 바로 위 노란색(A)에서 1/2확률로 내려온경우는 포함되지만, 맨 위 노란색에서 오른쪽으로 가서 내려오는 경우확률이 빠져있으므로 이도 더해주는 식이라고 한다.(thanks for jrj) 각 부분의 정의를 명확하게 해줘야지 안햇갈린다고 한다.

 

설명하면서도 내가 약간 햇갈려서 첨언을 하자면, 대각선으로 구역을 나누는 경우 서로 겹치는 경우가 없으므로(독립이므로) 확률을 구해서 더해버리면 되는데, 노란색(B)의 경우와 아래 파란색(C)의 경우는 겹치는 경우가 있다. 그러므로 겹치지 않는 경우 중에 세어지지 않은 부분만 추가적으로 더해주는 것이다. 노란색(A, B)의 경우에서는 오른쪽으로 갈 확률이 0%이므로 이 부분만 따로 추가로 더해주는 것이고, 아래로 가는 확률이 100%, 오른쪽이 0%인데 이것이 50% 50%으로 더해져 있으므로, 부족한 아래로 가는 50%를 더해주는 것이다.

내가 착각을 했던 것이, A,B의 경우가 무조건 C까지 가야만 한다고 생각을 했는데, 어차피 C에는 A,B 경우의 수 중 절반은 더해져 있는 상황이고, 이 남은 절반만 더해주면 된다는 것이다. 이 남은 절반의 확률은 맨 오른쪽에서는 아래로만 내려가는 선택지만 생긴다는 특수한 상황때문에 생기는 것이기도 하다.

 

그리고 역으로 전체에서 중간 구멍으로 빠질 확률을 빼줘도 되는데, f(초록칸)을 죄다 구한 뒤 1/2를 곱해서 더하면 된다고 한다. 그리고 1에서 그 값을 빼줘도 될 것 같은데 아직 구현은 안해봤다.

 

아래 코드는 빨간칸을 구해서 다 더하는 방식의 코드이다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 200005
double lnfact[MAXN];
double bicof(int a, int b) {
	return lnfact[a] - lnfact[a - b] - lnfact[b];
}
void solve() {
	int W, H, L, U, R, D;
	cin >> W >> H >> L >> U >> R >> D;

	int dist = L + D - 2;
	double ans = 0;
	if (D < H) {
		for (int i = 1; L - i > 0; i++) {
			int x = L - i;
			int y = D + i;
			double logval = bicof(dist, x - 1);
			logval -= dist;
			ans += pow(2, logval);
		}
	}
	dist = R + U - 2;
	if (R < W) {
		for (int i = 1; U - i > 0; i++) {
			int x = R + i;
			int y = U - i;
			double logval = bicof(dist, x - 1);
			logval -= dist;
			ans += pow(2, logval);
		}
	}
	cout << fixed << setprecision(8);
	cout << ans << endl;
}
int main() {
	for (int i = 2; i < MAXN; i++) {
		lnfact[i] = lnfact[i - 1] + log(i) / log(2);
	}
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cout << "Case #" << t << ": ";
		solve();
	}
}

 

 

저저번주쯤 주말에 올해 2020년의 첫 킥스타트 라운드 A가 있었는데, 아무것도 모르고 주말에 잠을 퍼질러 자다가 참여를 못하게 되었다.

 

A라운드는 근데 문제 난이도가 낮아서 빨리풀기 대회였다니 뭐 이런이야기들을 들었는데, 대회 당시에는 참여를 못했지만 나중에 업솔빙이라도 해볼 겸 시간 날때 풀어보았다.

 

이번해의 킥스타트는 저번과는 다르게 Large dataset도 제출한 뒤 바로 full-feedback을 준다고 한다. 맞았는지 틀렸는지를 바로 알려준다는 것은 뭔가 좋은 것 같으면서도 안 좋은것 같기도 하다.

 

바로 한번 문제 풀어보도록 하겠다.

 

문제들은 여기에서 확인하고 다시 풀어볼 수 있다.

 

총 4문제가 있다. 정답률을 보니 난이도가 왼쪽 < 오른쪽 문제로 가는 것 같다.

1. Allocation

문제는 간단하다. N개의 집이 있고, 각각의 집의 가격은 Ai원이다. 그리고 총 B달러가 있을때 가장 많은 집을 사고 싶다고 한다. 몇개를 살 수 있는가?

 

그냥 Ai를 오름차순으로 소팅한 뒤 예산을 넘지 않는 만큼만 진행하면 된다. //(O(NlgN)//)로 풀리며, N이 //(10^5//)이므로 쉽게 풀린다.

 

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

typedef long long ll;
int A[100005];
void solve() {
	int N, B;
	cin >> N >> B;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A, A + N);
	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (B >= A[i]) {
			B -= A[i];
			ans++;
		}
		else {
			break;
		}
	}
	printf("%d\n", ans);
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

 

2. Plates

접시를 골라서 그 값들을 최대로 해야하는데, 접시는 위에서부터 연속된 것들만 고를 수 있다. 접시를 고르는 총 개수도 정해져있다.

 

dp문제인데, 맨처음에 dp인 것 같다가 시간복잡도가 안될 것 같았다는 생각이 좀 들어서 약간 긴가민가 했었다. 근데 문제를 부분문제로 나눌 수 있고 독립되게 풀린다는 것이 보여서  dp가 맞는 듯 했다.

 

2차원 dp로 풀 수 있는데 각 항의 정의는 다음과 같다.

//(dp[i][j]//)는 i번째 줄까지 쭉 진행했을 때, j개의 접시를 골라서 낼 수 있는 최대 점수

 

이러면 //(dp[i][j]//)를 이용해서 다음 줄에서 k개의 접시를 구하는 경우//(dp[i+1][j+k]//)를 쉽게 구할 수 있다.

for-loop를 돌리는 식으로 구현해보았다.

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

typedef long long ll;
int a[55][33];
int dp[55][1505]; //dp[i][j]는 i번째 라인까지 j개의 plate를 골라서 얻을 수 있는 최대 점수.
void solve() {
	int N, K, P;
	cin >> N >> K >> P;
	memset(dp, 0, sizeof(dp));
	memset(a, 0, sizeof(a));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			cin >> a[i][j];
			a[i][j] += a[i][j - 1];
		}
	}

	
	for (int i = 1; i <= K; i++) {
		dp[1][i] = a[1][i];
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= i * K; j++) {
			for (int k = 0; k <= K; k++) {
				dp[i + 1][j + k] = max(dp[i + 1][j + k], dp[i][j] + a[i + 1][k]);
			}
		}
	}
	printf("%d\n", dp[N][P]);
	return;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

 

3. Workout

이거는 증가하는 수열에서 인접한 수열 사이의 차이를 일정 값 이하로 만들고 싶은 상황이다. 이 때  수열 사이 사이에 임의의 값을 갖는 녀석을 끼워넣을 수 있다. 이 때 인접한 수열 사이의 차이값의 최소값을 구하는 그런 문제이다.

 

최소값 구하는 문제, 최대값 구하는 문제 중 이러한 류의 문제들, 차이값의 최소 와 같은 좀 복잡한 값의 최소/최대문제는 보통 결정문제로 변경해서 푸는 파라메트릭 서치 문제이다.

 

인접한 값의 차이를 d 이하로 만들 수 있는가? 의 결정 문제로 바꾼 뒤 이녀석을 통해서 binary search를 돌리면 풀린다.

그리고 이 결정 문제는 보통 그리디나 선형 시간복잡도로 풀리게 된다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;

int M[100005];
int N, K;
bool ok(int v) {
	int k = K;
	for (int i = 1; i < N; i++) {
		int diff = M[i] - M[i - 1];
		k -= (diff + v - 1) / v - 1;
	}
	return k >= 0;
}
int solve() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> M[i];
	}
	int l = 1;
	int r = 1e9;
	while (l < r) {
		int m = (l + r) / 2;
		if (ok(m)) {
			r = m;
		}
		else {
			l = m + 1;
		}
	}
	return r;
}
int main() {
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cout << "Case #" << t << ": " << solve() << endl;
	}
}

 

4. Bundling

문자열들을 같은 크기의 Group들로 균일하게 나눈 뒤, 그 그룹들의 Longest prefix의 길이만큼 점수를 얻는데 이 점수를 최대화하는 그런 문제이다. 그룹을 어떻게 나눌 것인가까지는 알 필요 없이 점수만을 계산할 수 있다고 한다. 맨처음 이 문제를 보고 문자열 그냥 소팅한 뒤 K개씩 그룹핑 하면 되지 않을까 했는데 조금 생각해보니 바로 반례가 나왔다..

 

K가 만약 3이라고 하면 문자열이 다음과 같이 나왔을때 그리디하게 하면 최적화되지 않은 그룹핑이 된다.

A A A B C C C D E E E F

 

이런 경우 하나씩만 있는 B, D, F는 어차피 점수를 낼 수 없으므로 자기내들끼리 묶여서 남에게 피해를 주지 않아야 하는데 greedy하게 묶으면 망한다.

 

솔루션을 보니, Trie를 구축한 뒤, Trie Node별로 나타난 횟수를 체크해놓고, 나타난 횟수를 A라고 할때 각 노드별 floor(A/K)를 더하면 된다고 한다.

 

A % K에 해당하는 K개가 되지 못한 그룹녀석들은 어차피 어디에 끼여도 점수를 낼 수 없으므로 버리게 된다.

조금 생각해보니 correct한 알고리즘인 것이 이해가 되었다.

 

Trie는 malloc으로 구현하는 것이 귀찮아서 배열을 두고 정적할당과 같은 테크닉으로 구현을 해 보았다.

 

그리고 dfs로 모든 노드를 순회하면서 점수를 계산했다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;

#define MAXN 2000006
class Node {
public:
	char c;
	int num;
	int next[28];
	Node() {
		clear();
	}
	void clear() {
		memset(next, 0, sizeof(next));
		num = 0;
		c = 0;
	}
};
Node nodes[MAXN];
int cnt;
int dfs(int v, int k) {
	auto& cnode = nodes[v];
	int ret = cnode.num / k;
	for (char c = 'A'; c <= 'Z'; c++) {
		if (cnode.next[c - 'A'])
			ret += dfs(cnode.next[c - 'A'], k);
	}
	return ret;
}
int solve() {
	int n, k;
	cin >> n >> k;
	//clear prev data
	for (int i = 0; i <= cnt; i++) {
		nodes[i].clear();
	}
	cnt = 0;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		int ptr = 0;
		for (char c : s) {
			auto& next = nodes[ptr].next[c - 'A'];
			if (!next) {
				next = ++cnt;
				nodes[next].c = c;
			}
			ptr = next;
			nodes[ptr].num++;
		}
	}
	
	return dfs(0, k);
}
int main() {
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cout << "Case #" << t << ": " << solve() << endl;
	}
}

이번 주말에는 아무것도 없는 줄 알았다가, 킥스타트 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은 도저히 어떻게 해야할 지 생각이 안나서 스킵해놓은 상태이다. 이따가 풀이보고 공부해봐야겠다.

+ Recent posts