Codeforces Round #321 (Div. 2)

Contest Problems / Contest Standing

A. Kefa and First Steps

n개의 숫자가 주어졌을 때, maximum non-decreasing subsegment를 찾는 게 문제이다.

어떤 수열의 subsegment는 연속한 부분수열을 의미한다. 차례대로 수열의 원소들을 보면서, 새 원소가 이전의 원소보다 더 크다면 이전 원소의 maximum non-decreasing subsegment에 1을 더하여 답에 갱신하고, 아니면 현재의 maximum non-decreasing subsegment을 길이 1로 만들어 계속 진행해 나가는 방법으로 풀린다. O(n)에 풀 수 있다.

#include <stdio.h>
int n, res, cnt, a[100005], bf;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		if (bf <= a[i]) cnt++;
		else cnt = 1;
		if (res < cnt) res = cnt;
		bf = a[i];
	}
	printf("%d", res);
}

B. Kefa and Company

n명의 사람이 있는데, 각 사람마다 가진 money와 friendship이 주어진다. 주인공 Kefa는 몇 명의 무리를 정하려하는데, 임의의 무리 구성원 A, B에 대해서 A가 B보다 d 이상의 money를 가졌다면 B가 우울해한다. 이 때, 우울해하는 사람이 없도록 무리를 정해서 그 구성원들의 friendship의 합을 최대화하는 것이 문제이다.

사람들을 money순으로 정렬해놓고 보면, i번째 사람이 가장 적은 money를 가진 무리의 구성원일 때, 가장 큰 돈을 가진 구성원 B의 구간을 선형에 알 수 있고, 이 구간 안의 사람들은 모두 우울해하지 않는다는 성질을 알 수 있다. 따라서 이 구간을 모든 구간의 작은 index마다 이분탐색으로 찾을 수도 있고 - O(n log n), Loop Invariant를 이용해 구간의 양끝을 이동시켜보면서 모든 가능한 최대 구간을 선형 시간 내에 찾아볼 수 있다 - O(n). 아래의 내 코드는 후자의 방법을 이용하였다.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
pair <int, int> a[100005];
int n, d;
int main() {
	scanf("%d%d", &n, &d);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &a[i].first, &a[i].second);
	}
	sort(a + 1, a + n + 1);
	int L = 1;
	long long sum = 0, res = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i].first - a[L].first < d) {
			sum += a[i].second;
			if (res < sum) res = sum;
		}
		else {
			sum -= a[L].second;
			L++;
			i--;
			continue;
		}
	}
	printf("%I64d", res);
}

C. Kefa and Park

공원은 n개의 정점을 가지고 1번 정점이 루트인 모양의 트리이다. 각 정점에 고양이가 살고있는지 여부가 주어진다. 이 때, 트리의 말단 노드들에 대해서, 1번 정점에서부터 그 말단 노드 정점에 이르는 트리 상의 경로 중, m개보다 많은 연속한 노드들에 고양이가 산다면, 우리는 그 정점을 방문하지 못하는 정점이라고 부른다. 방문할 수 있는 정점의 수를 구하는 것이 문제이다.

DFS나 BFS로 트리를 구성하고, 말단 정점에서부터 올라오면서 연속한 고양이의 수 정보를 갱신하면서 m+1 이상이 된다면 그 경로를 invailid하다고 처리하면 된다. 최종적으로 루트 노드에까지 이르는 valid한 경로의 개수를 counting해서 출력하면 된다.

#include <stdio.h>
#include <vector>
using namespace std;
#define MN 100005
int n, m, a[MN], c[MN], res;
vector <int> v[MN];
void go(int x, int z) {
	if (x != 1) {
		if (z > m) return;
	}
	int cc = 0;
	for (int i = 0; i < v[x].size(); i++) {
		int y = v[x][i];
		if (c[y] == 0) {
			cc++;
			c[y] = 1;
			if (a[y]) go(y, z + a[y]);
			else go(y, 0);
		}
	}
	if (cc == 0) res++;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i < n; i++) {
		int xi, yi;
		scanf("%d%d", &xi, &yi);
		v[xi].push_back(yi);
		v[yi].push_back(xi);
	}
	c[1] = 1;
	go(1, a[1]);
	printf("%d", res);
}

D. Kefa and Dishes

n개의 요리가 있고, 주인공은 m개의 요리만 먹는다.(n≥m) 각 요리마다 만족도가 주어진다. 그리고 어떤 요리를 먹은 후에 특정 요리를 먹으면 만족도가 더해지는 관계가 주어질 때, 최적으로 m개의 요리를 순서에 맞게 잘 먹어서 만족도를 최대화하는 것이 문제이다.

Bitmask Dynamic Programming으로 해결할 수 있다.

"D( status , last dish ) : 현재 먹은 요리의 상태를 2진수로 표현하였을 때의 값이 status이고 마지막으로 먹은 요리의 index가 last dish일 때의 만족도의 최댓값."

#include <stdio.h>
#include <algorithm>
using namespace std;
int n, m, k, d[20], a[20][20], c[20], s[20], sn, t[20], tn;
long long dy[1 << 19][19];
long long res;
void go(int x) {
	if (x == n + 1) {
		int bit = 0;
		sn = tn = 0;
		for (int i = 1; i <= n; i++) {
			if (c[i]) bit |= (1 << i), t[++tn] = i;
			else s[++sn] = i;
		}
		if (tn == 0) {
			for (int j = 1; j <= sn; j++) {
				int q = s[j];
				dy[bit | (1 << q)][q] = max(dy[bit | (1 << q)][q], (long long)(d[q]));
				if (tn + 1 == m) res = max(res, dy[bit | (1 << q)][q]);
			}
		}
		else {
			for (int i = 1; i <= tn; i++) {
				int p = t[i];
				for (int j = 1; j <= sn; j++) {
					int q = s[j];
					dy[bit | (1 << q)][q] = max(dy[bit | (1 << q)][q], dy[bit][p] + d[q] + a[p][q]);
					if (tn + 1 == m) res = max(res, dy[bit | (1 << q)][q]);
				}
			}
		}
		return;
	}
	c[x] = 0;
	go(x + 1);
	c[x] = 1;
	go(x + 1);
	c[x] = 0;
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) scanf("%d", d + i);
	for (int i = 1; i <= k; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		if (a[x][y] < z) a[x][y] = z;
	}
	go(1);
	printf("%I64d", res);
}

E. Kefa and Watch

0부터 9까지의 1자리 숫자로 구성된 n자리의 string이 있다. 여기에 2가지 연산을 각각 m번, k번 수행한다.

1) index L부터 index R까지의 string의 구성 성분을 모두 c( 0 ≤ c ≤ 9 )으로 바꾼다.

2) index L부터 index R까지의 string이 주기 d를 가지는지 그 여부를 출력한다. 주기가 d라면, string S가 index 1부터 N까지의 string에 대해서 모든 i에 대해 S( i ) = S( i + d - 1) ( 1 ≤ i ≤ N-d+1 )를 만족해야한다.

hash값을 가지고 Segment Tree혹은 Merge Tree를 구성하여 문제를 해결할 수 있다. 전처리로 길이가 M인 string의 모든 숫자가 k( 0 ≤ k ≤ 9 )일 때의 hash값을 구한 다음에 1)에 대해서 자릿수에 해당하는 값을 곱하여 O(log n)에 해결할 수 있다. 2)는 S(L ~ R-d)의 hash값과 S(L+d ~ R)의 hash값이 같은 지를 O(log n)에 판별하여 해결할 수 있다. hash값을 합하는 것은 길이와 값을 알면 O(1)에 계산할 수 있으므로 그 과정은 생략한다. 따라서 전체적으로 O( (m+k) log n )에 문제를 해결할 수 있게 된다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
#define MN 100005
const ll base = 257, P = 100000007;
using namespace std;
ll lazy[4 * MN], H[4 * MN], S[10][MN], pw[MN];
char c[MN];
int n;
void upd(int x, int l) {
	H[x] = (H[2 * x] * pw[l] % P + H[2 * x + 1]) % P;
}
void shift(int x, int s, int e) {
	if (lazy[x] != -1) {
		int mid = (s + e) / 2;
		lazy[2 * x] = lazy[2 * x + 1] = lazy[x];
		H[2 * x] = S[lazy[x]][mid - s];
		H[2 * x + 1] = S[lazy[x]][e - mid];
		lazy[x] = -1;
	}
}
bool b = false;
void Set(int l, int r, int val, int s = 0, int e = n, int x = 1) {
	if (l <= s && e <= r) {
		lazy[x] = val;
		H[x] = S[val][e - s];
		return;
	}
	int mid = (s + e) / 2;
	shift(x, s, e);
	if (l < mid) Set(l, r, val, s, mid, 2 * x);
	if (r > mid) Set(l, r, val, mid, e, 2 * x + 1);
	upd(x, e - mid);
}
ll getH(int l, int r, int s = 0, int e = n, int x = 1) {
	if (l <= s && e <= r) return H[x];
	int mid = (s + e) / 2;
	shift(x, s, e);
	ll ans = 0;
	if (l < mid && r > mid) ans = (getH(l, r, s, mid, 2 * x)*pw[min(r, e) - mid] % P + getH(l, r, mid, e, 2 * x + 1)) % P;
	else if (l < mid) ans = getH(l, r, s, mid, 2 * x);
	else ans = getH(l, r, mid, e, 2 * x + 1);
	return ans;
}
int main() {
	int m, k;
	scanf("%d%d%d", &n, &m, &k); m += k;
	fill(lazy, lazy + 4 * n, -1);
	for (int i = 1; i <= n; i++) for (int j = 0; j < 10; j++) S[j][i] = (S[j][i - 1] * base + j) % P;
	pw[0] = 1;
	for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * base%P;
	scanf("%s", c);
	for (int i = 0; i < n; i++) Set(i, i + 1, c[i] - '0');
	b = 1;
	int alarm = 0;
	for (int i = 1; i <= m; i++) {
		int typ, l, r, d;
		scanf("%d%d%d%d", &typ, &l, &r, &d);
		l--;
		if (typ == 1) Set(l, r, d);
		else {
			bool ans = (d == r - l || getH(l, r - d) == getH(l + d, r));
			puts(ans ? "YES" : "NO");
		}
	}
	return 0;
}