CODE FESTIVAL 2015 本戦 A ~ I

CODE FESTIVAL 2015 決勝に参加しました。
本番では 5 問しか解けませんでしたが, 解説を聞いて 6 ~ 9 問目も解けました。
解説はここから見ることができるので,
各問題に対する自分の簡単なアプローチとコードを書きます。

A - コード川柳 (01:12 AC)
これはフォーム上でコーディングしました。 strlen はタイプ数が多いかな…

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
char s1[12], s2[12], s3[13];
scanf("%s%s%s", s1, s2, s3);
 
if (strlen(s1) == 5 && strlen(s2) == 7 && strlen(s3) == 5) printf("valid\n");
else printf("invalid\n");
 
return (0);
}

B - ダイスゲーム (07:46 AC)
最初は DP をしようとしてましたが, $N \leqq 256$ なので状態数が膨らみすぎると思って断念。
確率分布を考えると中央に寄ることが分かったのでそれで提出。 N + (N * 6 - N) / 2 ってどんだけ焦ってたんだ...

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
	int N;
 
	scanf("%d", &N);
 
	if (N == 1) printf("1\n");
 
	else printf("%d\n", N + (N * 6 - N) / 2);
		
	return (0);
}

C - 寿司タワー (21:21 AC)
今度こそ DP, と思って DP を実装すると, indexing がずれてしまって 1 WA を出してしまいました。
焦り過ぎは良くない...とはいいつつ, 未だに焦ってしまいます。

#include <bits/stdc++.h>
 
using namespace std;
 
int dp[519];
 
int main()
{
	int N;
	char s[519];
 
	scanf("%d", &N);
	scanf("%s", s);
 
	for (int i = 0; i < 2 * N; i++){
		if (s[i] != s[i + 1]) dp[i + 2] = max(dp[i + 2], *max_element(dp, dp + i + 1) + 1);
	}
 
	printf("%d\n", N - *max_element(dp + 1, dp + 2 * N + 1));
 
	return (0);
}

D - 足ゲームII (93:28 AC)
$N - 1$ 点という制約をうまく活かせないかに固執してしまって, 結局考察しきれませんでした…
そこで, 消す区間を全部試したくなって,

区間に値を足す
区間中の最大値を求める

が $O(\log n)$ でできればいい, と思ったものの, すぐに Starry Sky 木が出てきませんでした。実際この問題は上の操作ができればいいところからすぐに考察が進まず, E 問題に写ってしまいました。
これははっきりと自身の劣化を感じました。悔しいなあ。

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX_SIZE = 1 << 18;
 
int segMax[MAX_SIZE - 1], segAdd[MAX_SIZE - 1];
int n;
 
void add(int a, int b, int x, int k = 0, int l = 0, int r = 1 << 17)
{
	if (r <= a || b <= l) return;
	
	if (a <= l && r <= b){
		segAdd[k] += x;
		while (k){
			k = (k - 1) / 2;
			segMax[k] = max(segMax[k * 2 + 1] + segAdd[k * 2 + 1], segMax[k * 2 + 2] + segAdd[k * 2 + 2]);
		}
		return;
	}
	
	add(a, b, x, k * 2 + 1, l, (l + r) / 2);
	add(a, b, x, k * 2 + 2, (l + r) / 2, r);
}
 
int getMax(int a, int b, int k = 0, int l = 0, int r = 1 << 17)
{
	if (r <= a || b <= l) return (INT_MIN);
	
	if (a <= l && r <= b) return (segMax[k] + segAdd[k]);
	
	int left = getMax(a, b, k * 2 + 1, l, (l + r) / 2);
	int right = getMax(a, b, k * 2 + 2, (l + r) / 2, r);
	
	return (max(left, right) + segAdd[k]);
}
 
int main()
{
	int N;
	int s[100000], t[100000];
 
	scanf("%d", &N);
 
	for (int i = 0; i < N; i++){
		scanf("%d %d", s + i, t + i);
		add(s[i], t[i], 1);
	}
 
	int ans = getMax(0, 100001);
 
	for (int i = 0; i < N; i++){
		add(s[i], t[i], -1);
		ans = min(ans, getMax(0, 100001));
		add(s[i], t[i], 1);
	}
 
	printf("%d\n", ans);
 
	return (0);
}

E - ショートコーディング (68:11 AC)
ゆっくり考察をして, 解説に書かれている事項に気づいて AC できました。
欲を言えばもっと早く気づきたかったな…

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
	char s[512];
	int ncount, ecount;
	bool flag = false;
 
	scanf("%s", s);
 
	ncount = ecount = 0;
 
	for (int i = 0; s[i]; i++){
		if (s[i] == '!'){
			ecount++;
			flag = true;
		}
		else if (!flag) ncount++;
	}
 
	if (ncount % 2) printf("-");
	if (ecount % 2) printf("!");
 	else if (ecount) printf("!!");
	printf("\n");
 
	return (0);
}

F - 歩くピアニスト
解説を聞いてときました。
考察が生きる問題ですね。

グラフに落とす
頂点についての制約は辺の制約に変換すると解きやすい

という 2 点を抑えられるとちょっとは見えてくるのかな...と思います。まだまだだなあ。

#include <bits/stdc++.h>
 
using namespace std;
typedef long long Int;
 
Int C[7], E[7];
bool vis[7];
 
bool reachable(int x)
{
	if (vis[x]) return (false);
	if (x == 0) return (true);
	vis[x] = true;
	if (E[(x + 6) % 7] && reachable((x + 6) % 7)) return (true);
	if (E[x] && reachable((x + 1) % 7)) return (true);
 
	return (false); 
}
 
int main()
{
	for (int i = 0; i < 7; i++) scanf("%lld", C + i);
	C[0]--;
	E[0] = 0;
	
	for (int i = 0; i < 7; i++){
		if (i % 2 == 0 && i != 0) E[0] -= C[i];
		else E[0] += C[i];
	}
 
	for (int i = 1; i < 7; i++){
		E[i] = 2 * C[i] - E[i - 1];
	}
 
	for (int i = 0; i < 7; i++){
		if (E[i] < 0 || (E[(i + 6) % 7] + E[i]) % 2) return (!printf("NO\n"));
	}
 
	for (int i = 0; i < 7; i++){
		memset(vis, 0, sizeof(vis));
		if ((E[(i + 6) % 7] != 0 || E[i] != 0) && !reachable(i)) return (!printf("NO\n"));
	}
 
	return (!printf("YES\n"));
}

G - スタンプラリー
本番中は, なんとなく区間 DP をしたくなったものの, 解説で言う dp_forest みたいなものが思いつけず, 遷移が見えなくて実装できませんでした。
解説でやっていた DP はすごく感銘をうけたので, 自分の物にしたいです。

#include <bits/stdc++.h>
 
using namespace std;
typedef long long Int;
 
const int MOD = 1000000007;
 
Int dp[300][300], dp2[300][300];
int a[300];
 
Int func(int l, int r);
Int func2(int l, int r);
 
Int func(int l, int r)
{
	if (l == r) return (1);
	if (dp[l][r] != -1) return (dp[l][r]);
 
	//let l be the root of the tree
	return (dp[l][r] = func2(l + 1, r));
}
 
Int func2(int l, int r)
{
	if (l == r) return (1);
	if (dp2[l][r] != -1) return (dp2[l][r]);
 
	Int res = func(l, r);
 
	for (int i = l; i < r; i++){
		if (a[l] < a[i + 1]) res = (res + func(l, i) * func2(i + 1, r) % MOD) % MOD;
	}
 
	return (dp2[l][r] = res);
}
 
int main()
{
	int N;
 
	scanf("%d", &N);
 
	for (int i = 0; i < N; i++){
		scanf("%d", a + i); a[i]--;
	}
 
	if (a[0] != 0) return (!printf("0\n"));
 
	memset(dp, -1, sizeof(dp));
	memset(dp2, -1, sizeof(dp2));
 
	printf("%lld\n", func(0, N - 1));
 
	return (0);
}

H - 焼肉の達人
これも考察が肝になっていて, 最短経路に落とせることに驚きました。
asi さんから重みつきの区間スケジューリングはよく最短経路問題に落とせると聞いたので, これも自分の中にテクニックとして蓄えたいです。

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX_N = 100000;
 
struct Edge {
	int to, cost;
	Edge(int to, int cost) : to(to), cost(cost){}
	Edge(){}
	bool operator < (const Edge &x) const{
		return (cost < x.cost);
	}
	bool operator > (const Edge &x) const{
		return (x < *this);
	}
};
 
vector<Edge> G[MAX_N + 10];
bool vis[MAX_N + 10];
 
int main()
{
	int N, M;
 
	scanf("%d %d", &N, &M);
 
	for (int i = 0; i < M; i++){
		G[i].push_back(Edge(i + 1, 2));
		G[i + 1].push_back(Edge(i, 0));
	}
 
	for (int i = 0; i < N; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		G[x].push_back(Edge(x + y, y));
	}
 
	priority_queue< Edge, vector<Edge>, greater<Edge> > pq;
 
	pq.push(Edge(0, 0));
	while (pq.size()){
		Edge t = pq.top(); pq.pop();
		if (vis[t.to]) continue;
		vis[t.to] = true;
 
		if (t.to == M) return (!printf("%d\n", 2 * M - t.cost));
 
		for (int i = 0; i < G[t.to].size(); i++){
			Edge e = G[t.to][i];
			pq.push(Edge(e.to, t.cost + e.cost));
		}
	}
 
	return (-1);
}

I - 風船ツリー
どういうことができればいいかは思いつくものの, 各頂点について $O(\log n)$ くらいで切らないといけない辺の数を
数える方法を思いつけませんでした。
この辺は問題をこなさないと見えてこないのかなあと思いました。これからも色々な問題を説き続けたいと思います…

#include <bits/stdc++.h>
 
#define MAX_N (100000)
 
using namespace std;
 
int L[MAX_N + 10];
int mHeight[MAX_N + 10];
int vHeight[MAX_N + 10];
 
struct Edge {
	int to, cost;
	Edge(int to, int cost) : to(to), cost(cost){}
	Edge(){}
};
 
vector<Edge> G[MAX_N + 10];
 
void dfs(int v, int p, int curHeight)
{
	vHeight[v] = curHeight;
 
	int maxi = vHeight[v];
	for (int i = 0; i < G[v].size(); i++){
		if (G[v][i].to != p) dfs(G[v][i].to, v, curHeight + L[G[v][i].to]);
		maxi = max(maxi, mHeight[G[v][i].to]);
	}
	mHeight[v] = maxi;
}
 
int BIT[MAX_N + 10];
 
void add(int p, int x)
{
	for (p++; p <= MAX_N + 9; p += p & -p) BIT[p] += x;
}
 
int sum(int p)
{
	int ret = 0;
	for (p++; p; p &= (p - 1)) ret += BIT[p];
	return (ret);
}
 
vector<int> vs;
map<int, int> mp;
 
void getAns(int v, int p)
{
	int h;
	for (int i = 0; i < G[v].size(); i++){
		h = lower_bound(vs.begin(), vs.end(), mHeight[G[v][i].to]) - vs.begin();
		add(h, 1);
	}
	h = lower_bound(vs.begin(), vs.end(), vHeight[v]) - vs.begin();
	
	if (mp.count(vHeight[v]) == 0) mp[vHeight[v]] = sum(MAX_N) - sum(h);
	mp[vHeight[v]] = min(mp[vHeight[v]], sum(MAX_N) - sum(h));
 
	for (int i = 0; i < G[v].size(); i++){
		h = lower_bound(vs.begin(), vs.end(), mHeight[G[v][i].to]) - vs.begin();
		add(h, -1);
		if (G[v][i].to != p) getAns(G[v][i].to, v);
	}
 
	for (int i = 0; i < G[v].size(); i++){
		h = lower_bound(vs.begin(), vs.end(), mHeight[G[v][i].to]) - vs.begin();
		add(h, -1);
	}
	h = lower_bound(vs.begin(), vs.end(), mHeight[v]) - vs.begin();
	add(h, 1);
}
 
int main()
{
	int N;
 
	scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%d", L + i);
	for (int i = 1; i < N; i++){
		int x; scanf("%d", &x);
		G[x - 1].push_back(Edge(i, L[i]));
	}
 
	dfs(0, -1, L[0]);
 
	for (int i = 0; i < N; i++) vs.push_back(vHeight[i]);
	sort(vs.begin(), vs.end());
	vs.erase(unique(vs.begin(), vs.end()), vs.end());
 
	getAns(0, -1);
 
	int Q;
 
	scanf("%d", &Q);
	for (int i = 0; i < Q; i++){
		int x; scanf("%d", &x);
		if (mp.count(x) == 0) printf("-1\n");
		else printf("%d\n", mp[x]);
	}
 
	return (0);
}

まとめ

良かった点

1 つの問題に捕らわれないで色んな問題に目を向けられた。

悪かった点

結構焦ってしまったことと, 考察がまだまだできていなかったこと。
コンテスト中に問題だけに集中できるように気持ちの整理を素早く出来るようにしたい。 (順位表に踊らされやすい...)

来年以降も機会があれば, 30 位以内を目指したいと考えています。
なんだかんだいって本当に悔しかったので, 問題を解く幅を広げるために今後頑張っていきたいです。

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

CODE FESTIVAL 2015 本戦 A ~ I

まとめ