Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined)

A. Perfect Squares

sqrt 함수를 이용하여 제곱수인지 확인하고 그 중에서 최대값을 찾으면 된다.

#include <cstdio>
#include <cmath>
int max_v(int a, int b) { return a > b ? a : b; }
int main() {
	int n, D,ans=-1e9;
	double tD;
	scanf("%d", &n);
	while(n--) {
		scanf("%d", &D);
		if (D >= 0) {
			tD = sqrt(D);
			if (tD != (int)tD)
				ans = max_v(ans, D);
		} else ans = max_v(ans, D);
	}
	printf("%d", ans);
	return 0;
}

B. Conan and Agasa play a Card Game

Greedy하게 접근한다. 모든 카드의 수가 짝수라면 Conan은 반드시 지게되어 있다.

반면 카드 중 하나라도 홀수가 있다면 Conan은 반드시 이기게 되어 있다.

홀수가 있다하더라도 Conan이 반드시 이기려면 홀수 개의 카드 중 번호가 가장 큰 카드를 선택해야만 한다.

#include <cstdio>
#include <set>
using namespace std;

int main() {
	int n, f = 0, cnts[100000] = {},i,D;
	set<int> datas;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &D);
		datas.insert(D);
		cnts[D]++;
	}
	for (auto it = datas.rbegin(); it != datas.rend() && !f; it++) {
		if (cnts[*it] % 2) f = 1;
	}

	printf("%s", f ? "Conan" : "Agasa");
	return 0;
}

C. Travelling Salesman and Special Numbers

?? 웰케 어렵지 C부터.. 굉장히 재밌는 문제긴하다.

완전 탐색부터 생각을 해보면, 앞에서부터 시작해서 현재의 위치에 '1' 또는 '0'이 올 수 있다. 여기서 n보다 크면 안되기 때문에 가지치기까지 생각을 해보자. 우선 n은 문자열로 받아야하기 때문에 문자열로 받아 놓는다.

재귀함수를 설계해보자. 현재 위치 pos(0부터 시작)까지 n과 prefix가 같다는 것을 이용하여 설계해보자. 그러면 다소 편리해지는데, 현재 위치 pos에서 '0'은 당연하고, '1'을 넣었을 때, n보다 작거나 같아야하는데, 현재 위치 pos까지 n과 prefix가 같으므로 n[pos]가 '1'이면 넣어도 되는 식으로 판단할 수 있다.

또한 '0'을 넣었을 때는 현재 위치 pos까지 n과 prefix가 같으므로(몇 번을 말하는거야..ㅋㅋ), 그 뒤로부터는 0을 꽉채우는 것부터 시작해서 1을 꽉채우는 것까지 모두 가능하다. 가령 n = 1101111, pos = 3이라면 pos에 0을 채워넣는다면, prefix는 110 그리고

1100000

1100001

1100010

...

1100111

위 경우가 모두 가능하단 소리다. 이 말은 즉, 재귀를 다시금 돌릴필요 없이 iterative하게 구조화 시킬 수 있단 소리다.

여기까지 정리하자면, 재귀를 이용하되 n[pos] == '1'에 따라 분기가 나뉜다. 재귀를 돌 때마다 데이터는 반드시 n과 prefix가 같도록 설정하여 진행한다. 또한 앞에서 설명하진 않았지만, cnt 변수를 따로 두어 1의 개수를 세어 주도록한다. 이러면 현재 pos-1까지의 1의 개수를 알 수 있다.

그렇다면 이제 1로 만들기 위한 과정에 대해 생각해보자.

과정이 k와 같아야 한다. 또한 cnt 변수로 이미 파악했기 때문에(연산을 이미 했기 때문에) 1을 추가하여 k와 비교해줘야한다.

(이 설계는 k=0,1에 대해서 예외처리를 해줘야한다. 이건 마지막에 설명하겠다.)

따라서 가능한 1의 최대 개수는 999개가 된다(2^1000-1). 이는 int형 범위 안에 들어오므로 bitwise-mask연산으로 진행해준다. 이 또한 재귀적인 특성을 지니고 있으므로 재귀함수를 설계한다. 1이 될때까지 bitmask 연산을 통해 개수를 세어주고 이 과정을 반복하게 해주면 된다. 단, 그 개수가 0이 될 수도 있기때문에 반환값을 말도안되게 큰 값으로 반환해줘서 처리해준다. (이 경우는 수 0밖에 없긴하다.)

게다가 계산되는 cnt 값이 한정적이고, 101과 110이 1이되기 위한 연산수도 동일하기 때문에 이 부분을 dynamic programming 처리를 해준다.

또, n[pos] = '1'이고 현재 pos를 '0'으로 처리할 때, 그 뒤에 가능한 경우를 cnt+i개로 처리해줘서 간단하게 처리 가능하다. 또한 그 위치에 대해 여러가지 있을 수 있으므로 조합(Combination)을 따로 계산해둔다음 이 값에 곱해준다. 굳이 수식으로 나타내면 아래와 같다.

마지막으로 말하지만 prefix가 같은 것에 대해 따로 처리해주므로 부문제가 겹칠 일이 없다.

이 알고리즘은 k=0,k=1에 대해서 처리해주지 않는다. n 은 1보다 크거나 같은 수이기 때문에 k=0인 수는 1밖에 없다.

또 k=1에 대해 숫자 1도 k=1에 속하게 되기 때문에(cal(cnt)+1에서 +1 때문) 하나를 제거하는 식으로 해주면 된다.

#include <cstdio>
#include <cstring>
const int MOD = 1e9 + 7, MAX_V = 1005;
char n[MAX_V];
int k, L, bi[MAX_V][MAX_V], cache[MAX_V];

void binomial() {
	int i, j;
	bi[0][0] = 1;
	
	for (i = 1; i < MAX_V; i++) {
		bi[i][0] = 1;
		for (j = 1; j <= i; j++) bi[i][j] = (bi[i - 1][j - 1] + bi[i - 1][j])%MOD;
	}
}

int cal(int c) {
	if (c == 0) return 5000;
	if (c == 1) return 0;

	int& ret = cache[c];
	if (ret == -1) {
		int cnt = 0;
		for (int bit = 1 << 30; bit > 0; bit >>= 1)
			if ((c&bit) > 0) cnt++;
		ret = cal(cnt) + 1;
	}
	return ret;
}

int rec(int pos, int cnt) {
	if (pos == L) return (cal(cnt) + 1) == k;
	int ret = 0;
	if (n[pos] == '1') {
		for (int i = 0; i < L - pos; i++) {
			ret += (1LL*bi[L - pos - 1][i] * ((cal(cnt + i) + 1) == k)) % MOD;
			ret %= MOD;
		}
	}
	ret += rec(pos + 1, cnt + (n[pos] == '1'));
	ret %= MOD;
	return ret;
}

int main() {
	scanf("%s%d", n, &k);
	L = strlen(n);
	memset(cache, -1, sizeof(cache));
	binomial();
	if (k == 0) printf("1");
	else printf("%d", rec(0, 0) - (k == 1));
	return 0;
}

D. Bash and a Though Math Puzzle

  Segment tree로 풀었다. 단 query를 날릴 때, 단 한번에 결과를 알 수 있어야한다. 처음에 구간 [l, r]에 대해서 하나씩 x를 대입(Greedy)해서 해결해봤다가 바로 TLE를 받았다.

Greedy 설명

  만약 변경해야할 노드가 하나라면 그 값을 x로 치환하기만 하면 된다.

  변경해야할 노드가 하나라는 소리는 나머지 값들은 모두 x보다 크거나 같고, x의 배수이기 때문이며, gcd 결과가 x이기 위해서는 반드시 변경해야할 노드가 x가 되야한다는 소리이기 때문.

  segment tree에서 query 구간 [l, r]에 대해서 모두 x로 나눠떨어져야 한다는 것을 이용한다. 만약 두 개 이상의 노드에 대해서 x에 대해서 나눠떨어지지 않는다면, 예측 실패다. 따라서 어떤 노드가 x에 나눠떨어지지 않는다는 소리는 gcd(왼쪽 자식, 오른쪽 자식)의 결과가 x로 나눠떨어지지 않는다는 소리이므로, 왼쪽과 오른쪽 둘다 나눠서 다시금 탐색하게된다. 만약 두 자식 모두 x로 나눠떨어지지 않는다면 실패를 뜻하기 때문이다.

  

  x로 나눠떨어지지 않는 노드를 실패 노드라고 한다면, 실패 노드를 찾는 과정은 다음과 같다.

1. 구간에 대해서 left의 부모가 구간을 대표하지 못한다면 left을 실패 노드인지 확인한다.

2. 구간에 대해서 right의 부모가 구간을 대표하지 못한다면 right을 실패 노드인지 확인한다.

3. 하나의 실패 노드로 걸러졌다면, 그 자식들을 모두 순회하며 x로 나눠지지 않는 자식 실패 노드를 하나씩 찾아간다. 이 과정에서 자식 실패 노드가 두 개라면 결과는 fail

      

     왼쪽의 경우 실패 노드가 하나이기 때문에 almost correct가 된다. 반면 오른쪽의 경우 실패노드가 두 개이기 때문에 맨 위에서 들어온 시점부터 almost correct가 아니게 된다.

소스는 codeforce segment tree tutorial를 공부했다.

http://codeforces.com/blog/entry/18051

#include <cstdio>
using seg_data = int;
int gcd(int a, int b) {
	int t;
	while (b) {
		t = a%b;
		a = b;
		b = t;
	}
	return a;
}
struct seg_tree {
	seg_data* aTree;
	int n;
	seg_tree(int size) {
		n = size;
		aTree = new seg_data[(n+1)*2]{};
	}
	void build() {
		int i;
		for (i = 0; i < n; i++) scanf("%d", &aTree[i + n]);
		for (i = n - 1; i; i--)
			aTree[i] = gcd(aTree[i << 1], aTree[i << 1 | 1]);
	}

	bool query(int l, int r, int x) {
		int unroot=0, child;
		for (l += n, r += n; l<=r; l >>= 1, r >>= 1) {
			if ((l & 1)){
				if (aTree[l] % x) {
					if (unroot) return 0;
					else unroot = l;
				}
				l++;
			}
			if (r % 2 == 0) {
				if (aTree[r] % x) {
					if (unroot) return 0;
					else unroot = r;
				}
				r--;
			}
		}
		while (unroot) {
			if (unroot >= n) return 1;
			child = 0;
			if (aTree[unroot << 1] % x) child = unroot << 1;
			if (aTree[unroot << 1 | 1] % x) {
				if (child) return 0;
				else child = unroot << 1 | 1;
			}
			unroot = child;
		}
		return 1;
	}

	void update(int idx, seg_data d) {
		for (aTree[idx += n] = d; idx > 1; idx >>= 1)
			aTree[idx >> 1] = gcd(aTree[idx], aTree[idx ^ 1]);
	}

	~seg_tree() { delete[] aTree; }
};
int main() {
	int n, q,m,l,r,x,i,y;
	scanf("%d", &n);
	seg_tree st(n);
	st.build();
	scanf("%d", &q);
	while (q--) {
		scanf("%d", &m);
		if (m == 1) {
			scanf("%d%d%d", &l, &r, &x);
			printf("%s\n",st.query(l - 1, r - 1, x) ? "YES" : "NO");
		}
		else {
			scanf("%d%d", &i, &y);
			st.update(i-1, y);
		}
	}
	return 0;
}

E. Palindromes in a Tree

F. Substrings in a String

G. Sum the Fibonacci

H. Ember ans Storm's Tree Game