天下一プログラマーコンテスト2016予選A,D: グラフィカルグラフ

http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualA_d

構築ゲー。

まずゆるーく考えると適当な頂点を根にして辺の長さを2^n,2^(n-1)...としていけば作れることがわかる。
あとはこれを座標圧縮でキツくすればよい。

構築ゲーで大事なのはお気持ちなので、ゆるーく考えてきつくしたりすれば他のも解けるようになるんじゃないでしょうか。(適当)
でもお気持ちはわからないことのほうが多いですね…精進します。

vectorを使っていますが、基本的に少し遅い程度の認識でいいのかな？

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int op[4] = {2, 3, 0, 1};

int X[30], Y[30];
vector<int> G[30];
int N;

char ans[110][110];

void loop(int v, int p, int x, int y, int pd, int dist) {
	X[v] = x; Y[v] = y;
	vector<bool> used(4, false);
	if(pd != -1) used[op[pd]] = true;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(p == n) continue;
		int to;
		rep(j, 0, 4) {
			if(!used[j]) {
				used[j] = true;
				to = j; break;
			}
		}
		loop(n, v, x + dx[to] * dist, y + dy[to] * dist, to, dist / 2);
	}
}

int fd(const vi& vec, int a) {
	return lower_bound(all(vec), a) - vec.begin();
}

void solve() {
	cin >> N;
	rep(i, 0, N - 1) {
		char c, d; cin >> c >> d;
		int a, b; a = c - 'A'; b = d - 'A';
		G[a].pb(b); G[b].pb(a);
	}
	loop(0, -1, 0, 0, -1, 1 << N);
	vi vx, vy;
	rep(i, 0, N) {
		vx.pb(X[i]);
		vy.pb(Y[i]);
	}
	sort(all(vx)); sort(all(vy));
	vx.erase(unique(all(vx)), vx.end());
	vy.erase(unique(all(vy)), vy.end());

	cout << sz(vx) * 2 << " " << sz(vy) * 2 << "\n";
	rep(i, 0, sz(vx) * 2) 
		rep(j, 0, sz(vy) * 2) ans[i][j] = '.';

	rep(v, 0, N) {
		int x = fd(vx, X[v]) * 2, y = fd(vy, Y[v]) * 2;
		rep(i, 0, sz(G[v])) {
			int n = G[v][i];
			int nx = fd(vx, X[n]) * 2, ny = fd(vy, Y[n]) * 2;
			if(nx == x) {
				for(int yat = min(y, ny); yat <= max(y, ny); yat++) {
					ans[x][yat] = '-';
				}
			}
			else { //ny == y
				for(int xat = min(x, nx); xat <= max(x, nx); xat++) {
					ans[xat][y] = '|';
				}
			}
		}
	}
	rep(v, 0, N) {
		int x = fd(vx, X[v]) * 2, y = fd(vy, Y[v]) * 2;
		ans[x][y] = v + 'A';
	}
	rep(i, 0, sz(vx) * 2) {
		rep(j, 0, sz(vy) * 2) {
			cout << ans[i][j];
		}
		cout << "\n";
	}
}

バグらせ要素全くないのにバグらせまくったのは反省。