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

問題

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

N頂点の木がある。
頂点0から順にA,B,...とラベルづけ。
与えられた木を以下のように視覚的に表示せよ。

8 12
............
...D...E....
...|...|....
.C-A---B---F
.|.....|...|
.|.....G.J-I
.H..........
............

2 <= N <= 26

帰納的考察（解説見た）

1. ぶっちゃけ何から手を付けていいか分からなかった
2. 愚直解もさっぱりだった

――壁――

3. 解説に書かれている事がすごい

適当な頂点を根とし、適当な位置に置きます。
その頂点と隣接する頂点を、根の上下左右 2^N マス離れたところに置きます。
さらに、いま置いた頂点と隣接する頂点を、上下左右 2^(N-1) マス離して置きます。
このようにすれば、重なることなくすべての頂点を配置できます。

4. なるほどという印象しか受けない
5. 以上のように配置すればとりあえず置けます -> bfs()

6. しかし、このままだと100×100に収めよという制約に反するので、座標圧縮します -> zaatsu()

7. 最後に座圧した情報を元に解答を作って行きます -> bfs2()

実装

http://tenka1-2016-quala.contest.atcoder.jp/submissions/823486

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
 
int N;
vector<int> E[26];
//-----------------------------------------------------------------
typedef long long ll;
ll pow(int x, int n) { ll ret = 1; rep(i, 0, n) ret *= x; return ret; }
//-----------------------------------------------------------------
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { -1, 0, 1, 0 };
ll X[26], Y[26];
int D[26];
void dfs(int i, ll x, ll y, int dir, int dpt) {
	X[i] = x;
	Y[i] = y;
	D[i] = dpt;
	
	for (int j : E[i]) if (!D[j]) {
		dir = (dir + 1) % 4;
		ll s = pow(2, N + 2 - dpt);
		ll xx = x + dx[dir] * s;
		ll yy = y + dy[dir] * s;
		dfs(j, xx, yy, (dir + 2) % 4, dpt + 1);
		
	}
}
//-----------------------------------------------------------------
int H, W;
vector<string> ans;
void zaatsu() {
	map<ll, int> XX, YY;
 
	rep(i, 0, N) {
		XX[X[i]] = 0;
		YY[Y[i]] = 0;
	}
	int idx = 0;
	for (auto p : XX) XX[p.first] = idx * 2, idx++;
	idx = 0;
	for (auto p : YY) YY[p.first] = idx * 2, idx++;
 
	rep(i, 0, N) {
		X[i] = XX[X[i]];
		Y[i] = YY[Y[i]];
	}
 
	W = XX.size() * 2 - 1;
	H = YY.size() * 2 - 1;
	ans.resize(H, string(W, '.'));
}
//-----------------------------------------------------------------
void dfs2(int i) {
	int x = X[i];
	int y = Y[i];
	ans[y][x] = char('A') + i;
	for (int j : E[i]) if (D[i] < D[j]) {
		int xx = X[j];
		int yy = Y[j];
		
		if (x == xx)
			rep(yyy, min(y, yy) + 1, max(y, yy)) ans[yyy][x] = '|';
		else
			rep(xxx, min(x, xx) + 1, max(x, xx)) ans[y][xxx] = '-';
 
		dfs2(j);
	}
}
//-----------------------------------------------------------------
int main() {
	cin >> N;
	rep(i, 0, N - 1) {
		char v, w; cin >> v >> w;
		int a = v - 'A';
		int b = w - 'A';
		E[a].push_back(b);
		E[b].push_back(a);
	}
 
	dfs(0, 0, 0, 0, 1);
	zaatsu();
	dfs2(0);
 
	cout << H << " " << W << endl;
	for (string s : ans) cout << s << endl;
}