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進数ってすごいなぁ...

・制約以上のを考えたときは圧縮を考える