GCJ Round 1C Problem B. Slides!

GCJ はなんか苦手(得意なのもないけど)。

問題

Dashboard - Round 1C 2016 - Google Code Jam

B 個の頂点からなる有向グラフを考える。頂点 1 から頂点 B までの経路の数を M 個にしたい。これを満たすグラフは作れるか。作れるなら 1 つそのようなグラフを示せ。

解法

よくわからないまま解いてしまいました。

閉路を作ると経路の数が∞になるので, 閉路は作らないようにしないといけません。
なので, i 番目の辺は, i+1, i+2, ..., B に対して貼ることにします。

で, 答えを M に合わせたいので, 以下のように頂点 i から辺を貼っていきます。

• i+1 から順 v に見ていく。
• dp[i] + (v から B への経路数)が M を超えないとき, i -> v の辺を張り, dp[i] += (v から B への経路数) とする

これでうまくいきました。

本番想定されていた解はおそらく上のようなものではありません。

調べるとわかりますが,
1 -> 2, ..., 1 -> B
2 -> 3, ..., 2 -> B
3 -> 4, ..., 3 -> B
...
(B-1) -> B
に辺を張ると, 1 から B への経路数は 2^(B-2) になります(1, B 以外にどの頂点を通るかが 2^(B-2) あるので)。

これを利用して, 2 から後は i -> j (i < j) の辺はすべて貼っておくことにすると, 1 から貼るべき辺というのは, M の 2^(i-2) の bit が立っているなら M-i+1 に辺を張るようにすれば良さそうです(微妙に index ずれてるかも)。

void solve() {
	int B;
	ll M;
	cin >> B >> M;
	ll maxi = 1ll<<(B-2);
	if (maxi < M) {
		cout << "IMPOSSIBLE" << endl;
		return;
	}
	cout << "POSSIBLE" << endl;
	vector<ll> dp(B);
	vector<vi> ans(B, vi(B));
	dp[B-1] = 1;
	for (int i = B-2; i >= 0; i--) {
		ll rest = M;
		for (int j = i+1; j < B; j++) {
			if (rest >= dp[j]) {
				rest -= dp[j];
				dp[i] += dp[j];
				ans[i][j] = 1;
			}
		}
	}
	for (int i = 0; i < B; i++) {
		for (int j = 0; j < B; j++)
			cout << ans[i][j];
		cout << endl;
	}
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
    	cout << "Case #" << t << ": ";
    	solve();
    }
    return 0;
}