AtCoder 天下一プログラマーコンテスト0216予選A D グラフィカルグラフ
chokudaiしゃんに投げられたので解きましたー
問題
https://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualA_d
いわゆる構築
解法
常に最高効率で構築するのはとても大変
無駄があったり制約を満たさない解法であっても、必ず成立させられる構築方法を考えるのはとても重要
今回の場合であれば、「点の位置を必ず辺に到達できないようにする」ことで達成できるので
2^n >= 2^(n-1) + 2^(n-2) + ... + 1
を使って、
辺の長さを2^n,2^(n-1),2^(n-2)
というように変化させることで
辺が交差しないように構築できます
が,H,W<=100
を達成できません
これは座標圧縮をすることで解決できます
コード
https://tenka1-2016-quala.contest.atcoder.jp/submissions/2702775
#include <bits/stdc++.h> using namespace std; using i64 = long long; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) vector<vector<int>> G; i64 X[100]; i64 Y[100]; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; int vis[100]; void rec(int v,int n,int before_cnt){ vis[v] = 1; int cnt = -1; for(int to : G[v]){ if(vis[to]) continue; cnt++; if(cnt == (before_cnt ^ 1)) cnt++; X[to] = X[v] + dx[cnt] * (1LL << n); Y[to] = Y[v] + dy[cnt] * (1LL << n); rec(to,n - 1,cnt); } } char ans[100][100]; void rec2(int v,int n,int before_cnt){ ans[X[v]][Y[v]] = v + 'A'; vis[v] = 1; int cnt = -1; for(int to : G[v]){ if(vis[to]) continue; int ddx = (X[to] - X[v] > 0 ? 1 : -1); int ddy = (Y[to] - Y[v] > 0 ? 1 : -1); if(X[to] == X[v]) ddx = 0; if(Y[to] == Y[v]) ddy = 0; for(int x = X[v] + ddx,y = Y[v] + ddy;x != X[to] || y != Y[to];x += ddx,y += ddy){ ans[x][y] = (ddx != 0 ? '|' : '-'); } rec2(to,n - 1,cnt); } } int main(){ rep(i,0,99){ rep(j,0,99) ans[i][j] = '.'; } int N; cin >> N; G.resize(N); rep(i,0,N - 2){ char c,d; cin >> c >> d; int a,b; a = c - 'A'; b = d - 'A'; G[a].push_back(b); G[b].push_back(a); } rec(0,N,10); vector<i64> xs,ys; rep(i,0,N - 1){ xs.push_back(X[i]); ys.push_back(Y[i]); } sort(xs.begin(),xs.end()); sort(ys.begin(),ys.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end()); ys.erase(unique(ys.begin(),ys.end()),ys.end()); rep(i,0,N - 1){ X[i] = lower_bound(xs.begin(),xs.end(),X[i]) - xs.begin(); Y[i] = lower_bound(ys.begin(),ys.end(),Y[i]) - ys.begin(); X[i] *= 2; Y[i] *= 2; vis[i] = 0; } rec2(0,N,10); cout << 100 << " " << 100 << endl; rep(i,0,99){ rep(j,0,99){ cout << ans[i][j]; } cout << endl; } }
感想
・2進数ってすごいなぁ...
・制約以上のを考えたときは圧縮を考える