hotpepsiの練習帳

Facebook Hacker Cup 2012 R1

02:17

A. Checkpoint

問題

• 始点からチェックポイントを通って終点に移動する
• チェックポイントは始点でも終点でもなく、必ず一回だけ通る
• 1マス単位で移動する。始点の方向には戻らない
• 移動のしかたがちょうどn通りになる最短経路のマンハッタン距離を求める

方針

• 始点からチェックポイントとチェックポイントから終点までを分離して考える
• 各経路においてa通りの最大値はaで、1+aが仮の最大値となる
• a通りが存在する経路であればより小さい値になる
• 図に書いてみると、場合の数(nCrとかnCmとか二項係数とかいうやつ)になっている
• 1から10000000の二項係数の表(nCrからn+rへの最小値の表)を持っておく

#define MAX_S 10000000
#define INF MAX_S*2
typedef pair<int, int> II;
typedef map<int, int> IntMap;
IntMap S_to_dist;
int i, j, k, n;
static int p[MAX_S+1];
p[0] = 1;
for (i = 1; i <= MAX_S; ++i) {
	int prev = 1, next = 1;
	for (j = 1; j <= (i/2); ++j) {
		next = prev + p[j];
		prev = p[j];
		p[j] = next;
		if (next > MAX_S) {
			next = INF;  // これがないと負になる
			break;
		}
		if (next != i) {
			int d = S_to_dist[next];
			if (d <= 0 || i < d) {
				S_to_dist[next] = i;
			}
		}
	}
	p[j] = next;
}
cin >> n;
for (i = 1; i <= n; ++i) {
	cin >> j;
	int res = j + 1;
	for (k = 1; (k*k) <= j; ++k) {
		if ((j % k) == 0) {
			int l = k;
			if (S_to_dist.find(k) != S_to_dist.end()) {
				l = S_to_dist[k];
			}
			int m = j/k;
			if (S_to_dist.find(m) != S_to_dist.end()) {
				m = S_to_dist[m];
			}
			res = min(res, l+m);
		}
	}
	cout << "Case #" << i << ": " << res << endl;
}

B. Recover the Sequence

問題

• マージソートのデバッグ出力が与えられる
• 元の数列を復元してチェックサムを求める

方針

• 与えられたコードをそのままシミュレーションする
• できた数列は、元の数値の位置を示しているので、元に戻す

C. Squished Status

問題

• 数列を文字化して連結する
• 数値の範囲は1からMまで
• 空白がないので、12が1と2なのか12なのかわからない
• 何通りの数列がありうるかを求める
• mod FACEBOOK

方針

• DPで足す

LL solve(int m, const char *s)
{
	int len = strlen(s);
	int res = 0;

	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	int read = 0;
	int write = 1;
	int m2 = min(m, 99);
	int a, b, c, d, e;
	for (a = 1; a <= len; ++a) {
		for (b = 0; b <= MAX_N; ++b) {
			dp[write][b] = dp[read][b];
		}

		for (b = 1; b <= 9; ++b) {
			if (s[a-1] == (b+'0')) {
				dp[write][a] += dp[read][a-1];
			}
		}
		if (a >= 2) {
			for (b = 10; b <= m2; ++b) {
				d = b/10;
				e = b%10;
				if (s[a-2] == (d+'0') && s[a-1] == (e+'0')) {
					dp[write][a] += dp[read][a-2];
				}
			}
			if (a >= 3) {
				for (b = 100; b <= m; ++b) {
					c = b/100;
					d = (b-c*100)/10;
					e = b%10;
					if (s[a-3] == (c+'0') &&
							s[a-2] == (d+'0') &&
							s[a-1] == (e+'0')) {
						dp[write][a] += dp[read][a-3];
					}
				}
			}
		}
		dp[write][a] %= (LL)FACEBOOK;
		read ^= 1;
		write ^= 1;
	}

	return dp[read][len];
}

結果

x-o 敗退

Aはチェックポイントがn個と誤読していて時間かかりすぎ＆不正解。問題文はよく読まないと。二項係数のDPに時間かかりすぎ。

Bは思いつかなかった。だめすぎる。

Cはまあできた。よしとする。