Google Codejam Round 1A 2016

Problem A. The Last Word

각 단계마다 그리디하게 앞에 붙이는 것이 좋은지 뒤에 붙이는 것이 좋은지 선택.

char S[1005];
int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	int runs = 1;
	int T; for (scanf("%d", &T); T--;) {
		scanf("%s", S);
		string a = "";
		for (int i = 0; S[i]; i++) {
			string b = a + S[i];
			string c = S[i] + a;
			if (b > c) a = b;
			else a = c;
		}
		printf("Case #%d: %s\n", runs++, a.c_str());
	}
	return 0;
}

Problem B. Rank and File

각 숫자를 카운팅한 후, 홀수번 등장한 수를 순서대로 출력.

int n;
int c[2555];
int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	int runs = 1;
	int T; for (scanf("%d", &T); T--;) {
		scanf("%d", &n);
		memset(c, 0, sizeof(c));
		for (int i = 0; i < 2 * n - 1; i++) {
			int x;
			for (int j = 0; j < n; j++) {
				scanf("%d", &x); c[x]++;
			}
		}
		printf("Case #%d:", runs++);
		for (int i = 1; i <= 2500; i++) if (c[i] & 1) printf(" %d", i);
		printf("\n");
	}
	return 0;
}

Problem C. BFFs

max(크기가 2인 사이클을 포함하는 부분 그래프들의 크기의 합, 크기가 3이상인 사이클들 중에서 최대 크기)

int n, a[1005], res, c[1005], d[1005], cycle[1005], cn, son[1005];
vector  v[1005], r[1005];
int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	int runs = 1;
	int T; for (scanf("%d", &T); T--;) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) v[i].clear(), r[i].clear();
		cn = res = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			v[i].push_back(a[i]);
			d[i] = c[i] = cycle[i] = son[i] = 0;
		}
		for (int i = 1; i <= n; i++) {
			if (cycle[i]) continue;
			if (d[i]) continue;
			vector  x;
			x.push_back(0);
			int p = i; x.push_back(i);
			c[p] = i; d[p] = 1;
			while (c[a[p]] != i) {
				d[a[p]] = d[p] + 1;
				p = a[p];
				c[p] = i;
				x.push_back(p);
			}
			if (son[x[d[a[p]]]] < d[a[p]] - 1) son[x[d[a[p]]]] = d[a[p]] - 1;
			if (cycle[x[d[a[p]]]]) continue;
			cn++;
			for (int j = d[a[p]]; j <= d[p]; j++) {
				cycle[x[j]] = cn;
				r[cn].push_back(x[j]);
			}
		}
		int res2 = 0;
		for (int i = 1; i <= cn; i++) {
			int m = r[i].size();
			if (res2 < m) res2 = m;
			if (m == 2) {
				res += 2;
				int m1 = 0, m2 = 0;
				for (int j = 0; j < m; j++) {
					int x = r[i][j];
					int cost = son[x];
					if (m1 < cost) m2 = m1, m1 = cost;
					else if (m2 < cost) m2 = cost;
				}
				res += m1 + m2;
			}
		}
		if (res < res2) res = res2;
		printf("Case #%d: %d\n", runs++, res);
	}
	return 0;
}