UTPC 2011埋め

タイトルの通り。
埋めれていない問題を解説を見たりしながら全部埋めました。
解説を見ても、なお難しい問題も多くて大変でした。
あまり誰もソース公開してないっぽいし、本番で解いたもの以外についてソース貼っておく。
本番で解いたものに関しては過去のエントリを参照。

AOJ 2264: Spanning Trees

解説見ました。これはちょっと思い浮かばなさそうな感じでした。
実装楽そうな別解を実装。

void printtree(int nn, int k){
  int n = nn - nn % 2;

  REP(i, n / 2){
    int a = 1 + (i + k) % n;
    int b = 1 + (n - i + k - 1) % n;
    printf("%d %d\n", a, b);
  }

  REP(i, n / 2 - 1){
    int a = 1 + (n - i - 1 + k) % n;
    int b = 1 + (i + k + 1) % n;
    printf("%d %d\n", a, b);
  }

  if(nn % 2) printf("%d %d\n", k + 1, nn);
}

int main(){
  int n = getInt();
  int k = getInt();

  if(n / 2 < k){ puts("-1"); }
  else{
    REP(i,k){
      printtree(n, i);
      puts("");
    }
  }

  return 0;
}

AOJ 2266: Cash Strategy

DPの発想しかなく、考えるものの分からないので解説を見る。
まさか区間の問題で最小費用流になるとは・・・。
最小費用流初めてでバグにはまりものすごく時間がかかりました。

struct Edge{
  int cap; // capacity
  int to;
  int rev; // reverse edge id

  Edge(){}
  Edge(int c, int t, int r) :
    cap(c), to(t), rev(r){}
};

struct CostEdge : public Edge{
  int cost;
  CostEdge() : Edge() {}
  CostEdge(int c, int t, int cs, int r) :
    Edge(c, t, r), cost(cs){}
};
  
template<class E> // Edge type
class Graph{
public:
  typedef std::vector<std::vector<E> > G;

private:
  G g;

public:
  Graph(int n) : g(G(n)) {}

  void addEdge(int from, int to, int cap){
    g[from].push_back(E(cap, to, g[to].size()));
    g[to].push_back(E(0, from, g[from].size() - 1));
  }

  void addEdge(int from, int to, int cap, int cost){
    g[from].push_back(E(cap, to, cost, g[to].size()));
    g[to].push_back(E(0, from, -cost, g[from].size() - 1));
  }

  G &getRowGraph(){
    return g;
  }
};

template<class E>
int minCostFlow(Graph<E> &graph, int s, int t, int f, bool negative = false){
  typedef pair<int, int> P;
  typename Graph<E>::G &g = graph.getRowGraph();
  int n = g.size();
  int res = 0;
  vector<int> h(n, 0);
  vector<int> prevv(n);
  vector<int> preve(n);
  const int inf = 10000000;

  if(negative){
    vector<int> dist(n, inf);
    dist[s] = 0;
    
    bool update = true;
    
    while(update){
      update = false;
      for(int v = 0; v < n; v++){
	if(dist[v] == inf) continue;
	for(int i = 0; i < (int)g[v].size(); i++){
	  E &e = g[v][i];
	  if(e.cap > 0 && dist[e.to] > dist[v] + e.cost){
	    dist[e.to]  = dist[v] + e.cost;
	    prevv[e.to] = v;
	    preve[e.to] = i;
	    update      = true;
	  }
	}
      }
    }

    for(int i = 0; i < n; i++)
      h[i] = dist[i];
  }

  while(f > 0){
    priority_queue<P, vector<P>, greater<P> > que;
    vector<int> dist(n, inf);
    dist[s] = 0;
    que.push(P(0, s));

    while(!que.empty()){
      P p   = que.top(); que.pop();
      int v = p.second;
      if(dist[v] < p.first) continue;
      for(int i = 0; i < (int)g[v].size(); i++){
	E &e = g[v][i];

	if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
	  dist[e.to]  = dist[v] + e.cost + h[v] - h[e.to];
	  prevv[e.to] = v;
	  preve[e.to] = i;
	  que.push(P(dist[e.to], e.to));
	}
      }
    }
    if(dist[t] == inf){
      return -1;
    }

    for(int v = 0; v < n; v++) h[v] += dist[v];

    int d = f;
    for(int v = t; v != s; v = prevv[v]){
      d = min(d, g[prevv[v]][preve[v]].cap);
    }

    f   -= d;
    res += d * h[t];

    for(int v = t; v != s; v = prevv[v]){
      E &e = g[prevv[v]][preve[v]];
      e.cap -= d;
      g[v][e.rev].cap += d;
    }
  }
  return res;
}

int main(){
  int m = getInt();
  int n = getInt();
  int k = getInt();

  vector<int> w(n);
  vector<int> a(k);

  Graph<CostEdge> g(k);

  REP(i,n) w[i] = getInt();
  REP(i,k) a[i] = getInt() - 1;

  int ans = 0;
  REP(i,k) ans += w[a[i]];

  vector<int> prevs(n, -1);

  REP(i,k){
    if(i != k - 1) g.addEdge(i, i + 1, 10000, 0);
    int aa = a[i];
    if(prevs[aa] != -1){
      int j = prevs[aa];
      if(j + 1 == i){
	ans -= w[a[i]];
      }else{
	g.addEdge(j + 1, i, 1, - w[a[i]]);
      }
    }
    prevs[aa] = i;
  }

  ans += minCostFlow(g, 0, k - 1, m - 1, true);

  printf("%d\n", ans);

  return 0;
}

AOJ 2267: Bit Operation

これは本番の解説の時の記憶を便りに解いた。
ほぼ解説通り。

template<class T1, class T2>
string appop(T1 v1, char op, T2 v2){
  stringstream ss;
  ss << "(" << v1 << op << v2 << ")";
  return ss.str();
}

template<class T>
string neg(T a){
  return appop("", '~', a);
}

template<class T>
string toStr(T v){
  stringstream ss;
  ss << v;
  return ss.str();
}

int main(){
  int n = getInt();
  int x[n], y[n];

  REP(i,n){
    x[i] = getInt();
    y[i] = getInt();
  }

  string ans = "";
  REP(k,8){
    REP(i,n){
      if(y[i] & (1 << k)){
	vector<string> buff(k + 1);
	REP(j,k + 1){
	  string s;
	  if(x[i] & (1 << j)){
	    s = appop("x", '*', (1 << (k - j)));
	  }else{
	    s = appop(neg("x"), '*', (1 << (k - j)));
	  }
	  buff[j] = s;
	}
	string buff2 = buff[0];
	for(int j = 1; j < k + 1; j++){
	  buff2 = appop(buff2, '&', buff[j]);
	}
	buff2 = appop(buff2, '&', (1 << k));
	if(ans.size()){
	  ans = appop(ans, '|', buff2);
	}else{
	  ans = buff2;
	}
      }
    }
  }

  if(ans.size() == 0) ans = "0";
  cout << ans << endl;

  return 0;
}

AOJ 2268: Randomized Self-Balancing Binary Search Tree

解説読みました。
まさか競技プログラミングで、FFTを使うなんて・・・。
誤差死するようなので、最後に定数足すという最低な対策をしてしまった。
FFTとか畳み込みの勉強したのでもっそい時間かかった。
しかも畳み込みの部分あってるのかよくわかんね。

// sizeof v must be 2 ^ n
template<class T>
void fft_core(vector<complex<T> > &v, bool rev = false){
  const int n = v.size();

  for(int i = 0; i < n; i++){
    int k = 0;
    int b = (n >> 1);
    int a = 1;

    while(b >= a){
      if(b & i) k |= a;
      if(a & i) k |= b;
      b >>= 1;
      a <<= 1;
    }

    if(i < k) swap(v[i], v[k]);
  }

  int m = 2;

  while(m <= n){
    double arg = -2.0 * M_PI / m;
    complex<T> w(cos(arg), sin(arg));
    if(rev) w = 1.0 / w;

    for(int i = 0; i < n; i += m){
      complex<T> ww(1.0);

      for(int j = 0; j < m / 2; j++){
	int a = i + j;
	int b = i + j + m / 2;
	complex<T> t = ww * v[b];

	v[b] = v[a] - t;
	v[a] = v[a] + t;

	ww *= w;
      }
    }
    m *= 2;
  }

  if(rev){
    double s = (double)n;
    for(int i = 0; i < n; i++)
      v[i] /= s;
  }
}

template<class T> inline void  fft(vector<T> &v){ fft_core(v); }
template<class T> inline void ifft(vector<T> &v){ fft_core(v, true); }

int next(int n){
  int i = 1;
  while(i < n) i *= 2;
  return i;
}


int main(){
  int n  = getInt();
  int m  = next(n + 1);
  int mm = m * 2;
  vector<complex<double> > p(mm, 0.0);
  double prev = 0.0;
  p[0] = 1.0;
  
  for(int i = 1; i <= n; i++){
    if(i < 51){
      fft(p);

      for(int j = mm - 1; j >= 0; j--){
	p[j] = p[j] * p[j];
      }
      
      ifft(p);

      for(int j = mm - 1; j >= 1; j--){
	p[j] = p[j - 1];
      }
      p[0] = 1.0;
      for(int j = 1; j < mm / 2; j++)
	p[j] /= j;
      for(int j = mm / 2; j < mm; j++)
	p[j] = 0.0;
      
      double ans = n >= p.size() ? 0.0 : p[n].real();
      double pans = (ans - prev);
      if(ans > 1e-10) pans += 0.000007;
      printf("%.7f\n", max(0.0, pans) + 1e-10);
      prev = ans;
    }else{
      printf("%.7f\n", 0.0 + 1e-10);
    }
  }

  return 0;
}

AOJ 2269: Traveling Salesman Problem

これは本番の時に解法は分かっていたけど、どうみても実装ゲーなのでパスしてた。
グラフを圧縮してその中で全点間の距離を求めておく。
あとは圧縮した部分を考慮しつつ愚直にやる。
プログラムの書き方によっては単純な一本道の場合だけ少し工夫しないといけない。
いろいろ修正した結果dfsがひどいことになってる。

vector<vector<pair<int, int> > > g;
vector<int> in;
vector<int> out;
vector<bool> ok;
vector<int> id;
vector<int> from;
vector<long long> fromdist;
vector<int> to;
vector<long long> todist;
vector<vector<pair<int, long long> > > dist;
vector<vector<long long> > dijk;

int un;

class UnionFind{
private:
  vector<int> id;

  int getId(int i){
    if(i == id[i]) return i;
    return id[i] = getId(id[i]);
  }
public:
  UnionFind(int size = 0){ init(size); }
  ~UnionFind(){}
  void init(int size){
    id = vector<int>(size);
    for(int i = 0; i < size; i++)
      id[i] = i;
  }
  void unite(int i, int j){
    int next = min( getId(i), getId(j) );
    id[getId(i)] = id[getId(j)] = next;
  }
  int operator [](int i){ return getId(i); }
  int count(){
    set<int> s;
    for(int i = 0; i < (int)id.size(); i++)
      s.insert(getId(i));
    return s.size();
  }
};

UnionFind uf;

int init;
ll dis;

pair<int, long long> dfs(int pos, bool first = true){
  if((!first || pos != init) && ok[pos]){
    dist[id[init]].push_back(mp(id[pos], dis));
    return mp(pos, dis);
  }

  if(!ok[pos]){
    from[id[pos]]     = init;
    fromdist[id[pos]] = dis;
  }

  pair<int, int> last;
  for(int i = 0; i < (int)g[pos].size(); i++){
    int next = g[pos][i].f;
    ll d = g[pos][i].s;

    if(first) un = next;

    dis += d;
    last = dfs(next, false);
    dis -= d;

    if(!ok[pos]){
      uf.unite(id[pos], id[un]);
      to[id[pos]]     = last.first;
      todist[id[pos]] = last.second - dis;
    }
  }

  return last;
}

int main(){
  int n = getInt();
  int m = getInt();

  g = vector<vector<pair<int, int> > >(n);
  in = vector<int>(n);
  out = vector<int>(n);
  ok = vector<bool>(n, false);
  id = vector<int>(n);

  REP(i,m){
    int a = getInt() - 1;
    int b = getInt() - 1;
    int c = getInt();

    bool find = false;
    for(int i = 0; i < g[a].size(); i++){
      if(g[a][i].f == b){
	find = true;
	g[a][i].s = min(g[a][i].s, c);
      }
    }

    if(!find){
      g[a].push_back(mp(b, c));
      in[b]++;
      out[a]++;
    }
  }

  map<int, int> okid;
  map<int, int> trid;

  REP(i,n){
    if(in[i] == 0 || out[i] == 0){
      puts("-1");
      return 0;
    }
    if(in[i] == 1 && out[i] == 1){
      // trivial
      int id2 = trid.size();
      trid[id2] = i;
      id[i] = id2;
    }else{
      // non-trivial
      int id2 = okid.size();
      okid[id2] = i;
      ok[i] = true;
      id[i] = id2;
    }
  }

  // REP(i,n) printf("%d: %d\n", i, (int)ok[i]);

  int N = okid.size();
  int M = trid.size();
  const long long MAX = (1ll << 60);
  long long ans = 0;

  if(N == 0){
    vector<ll> memo(n);

    int cnt = 0;
    int now = 0;
    ll d = 0;
    while(cnt != n){
      if(cnt != 0 && 0 == now){
	puts("-1");
	return 0;
      }
      cnt++;
      d += g[now][0].s;
      now = g[now][0].f;
      memo[now] = d;
    }

    for(int i = 0; i < n; i++){
      int j = i == n - 1 ? 0 : i + 1;

      if(memo[j] > memo[i])
	ans += memo[j] - memo[i];
      else
	ans += memo[0] - memo[i] + memo[j];
    }
    printf("%lld\n", ans);
    return 0;
  }

  // printf("N: %d\n", N);
  if(N > 1000) return 0;

  dist = vector<vector<pair<int, ll> > >(N);
  dijk = vector<vector<ll> >(N, vector<ll>(N, -1));
			     
  to = vector<int>(M, -1);
  from = vector<int>(M, -1);
  
  todist = vector<ll>(M);
  fromdist = vector<ll>(M);

  uf.init(M);
    
  REP(i,n) if(ok[i]){
    init = i;
    dfs(i);
  }
  
  //REP(k,N) REP(i,N) REP(j,N)
  //  dist[i][j] = min((long long)dist[i][j], (long long)dist[i][k] + dist[k][j]);

  REP(i,N){
    typedef pair<long long, int> data;
    priority_queue<data, vector<data>, greater<data> > pq;
    pq.push(mp(0, i));
    int cnt = 0;

    while(!pq.empty() && cnt != N){
      data d = pq.top(); pq.pop();
      long long ds = d.f;
      int pos = d.s;

      if(dijk[i][pos] != -1) continue;
      dijk[i][pos] = ds;
      cnt++;

      for(int j = 0; j < dist[pos].size(); j++){
	int next     = dist[pos][j].f;
	long long dd = ds + dist[pos][j].s;

	if(dijk[i][next] == -1){
	  pq.push(mp(dd, next));
	}
      }
    }
  }

  REP(i,N) REP(j,N) if(dijk[i][j] == -1){
    puts("-1");
    return 0;
  }

  if(N != 0){
    REP(i,M) if(from[i] == -1 || to[i] == -1){
      puts("-1");
      return 0;
    }
  }
    

  // REP(i,N){ REP(j,N) printf("%4d ", (int)dijk[i][j]); puts(""); }
    
  for(int j = 0; j < n; j++){
    int prev = j;
    int next = j == n - 1 ? 0 : j + 1;
    long long tmp = 0;

    if(!ok[prev] && !ok[next] && uf[id[prev]] == uf[id[next]] && fromdist[id[prev]] < fromdist[id[next]]){
      tmp += fromdist[id[next]] - fromdist[id[prev]];
    }else{
      if(!ok[prev]){
	tmp += todist[id[prev]];
	prev = to[id[prev]];
      }

      if(!ok[next]){
	tmp += fromdist[id[next]];
	next = from[id[next]];
      }

      tmp += dijk[id[prev]][id[next]];
    }

    // printf("%d => %d: %lld\n", j + 1, 1 + (j == n - 1 ? 0 : j + 1), tmp);

    ans += tmp;
  }

  printf("%lld\n", ans);
  return 0;

}

AOJ 2270: The L-th Number

最後にして最大の難関。
解説を見ても相当なムズさ。
一番分からなかったのは木の最も近い共通の親を探す方法。
一晩以上悩んだ結果、自分より2^k上の要素へリンクを貼っておけば二分探索できる。
あと解説には書いていなかったが、最後に値を2分探索するときにそのパスにある数値以外が答えにならないように工夫しないといけない。
これはもうひとつ2分木を使うことで対処したが、いろいろコードがひどいことに・・・

template<class T>
struct Node{
  Node *parent;
  Node *left;
  Node *right;
  T val;

  Node(T v, Node *p) :
    parent(p), left(NULL), right(NULL), val(v){}
};

struct Counter{
  int key;
  int cnt;
  Counter(int k, int c = 0) : key(k), cnt(c){}
};

inline bool operator == (const Counter &lhs, const Counter &rhs){
  return lhs.key == rhs.key;
}

inline bool operator != (const Counter &lhs, const Counter &rhs){
  return !(lhs == rhs);
}

inline bool operator < (const Counter &lhs, const Counter &rhs){
  return lhs.key < rhs.key;
}
inline bool operator > (const Counter &lhs, const Counter &rhs){
  return rhs < lhs;
}
inline bool operator <= (const Counter &lhs, const Counter &rhs){
  return !(rhs < lhs);
}
inline bool operator >= (const Counter &lhs, const Counter &rhs){
  return !(lhs < rhs);
}

inline Counter &operator += (Counter &lhs, const Counter &rhs){
  lhs.cnt += rhs.cnt;
  return lhs;
}

typedef Node<Counter> Nd;

Nd *push(Nd *root, Counter val, Nd *parent = NULL){
  if(root == NULL) return new Nd(val, parent);
  if(root->val == val){
    root->val += val;
  }else{
    if(root->val < val){
      root->right = push(root->right, val, root);
    }
    else{
      root->val += val;
      root->left = push(root->left,  val, root);
    }
  }
  return root;
}

void traverse(Nd *root, int depth = 0){
  if(root == NULL) return;
  traverse(root->left, depth+1);
  REP(i,depth) cout << " ";
  cout << root->val.key << ": " << root->val.cnt << endl;
  traverse(root->right, depth+1);
}

int countUnder(Nd *root, int key){
  if(root == NULL) return 0;
  if(key < root->val.key){
    return countUnder(root->left, key);
  }else{
    return root->val.cnt + countUnder(root->right, key);
  }
}

vector<int> x;
vector<int> level;
vector<vector<int> > prevs;
vector<vector<int> > g;
vector<Nd*> table;
vector<Nd*> table2;
Nd *root = NULL;

Nd *gen(Nd *root, Counter val){
  Nd *ret = NULL;
  Nd *now = ret;

  do{
    Nd *next = new Nd(root->val, now);
    next->left  = root->left;
    next->right = root->right;

    if(next->val >= val)
      next->val.cnt++;

    if(now == NULL){
      ret = now = next;
    }else{
      if(now->val < val){
	now->right = next;
      }else{
	now->left  = next;
      }
    }

    now = next;
    if(root->val < val) root = root->right;
    else                root = root->left;
  }while(root);

  return ret;
}

Nd *gen2(Nd *root, Counter val){
  Nd *ret = NULL;
  Nd *now = ret;

  do{
    Nd *next = new Nd(root->val, now);
    next->left  = root->left;
    next->right = root->right;

    if(next->val == val)
      next->val.cnt++;

    if(now == NULL){
      ret = now = next;
    }else{
      if(now->val < val){
	now->right = next;
      }else{
	now->left  = next;
      }
    }

    now = next;
    if(root->val < val) root = root->right;
    else                root = root->left;
  }while(root);

  return ret;
}

void calc(int pos, int prev, int l = 0){
  // printf("root: %x, val: %d\n", (unsigned int)root, x[pos]);
  table[pos]  =  gen(prev != -1 ? table[prev]  : root, Counter(x[pos], 1));
  table2[pos] = gen2(prev != -1 ? table2[prev] : root, Counter(x[pos], 1));
  // traverse(table[pos]);
  prevs[pos][0] = prev;
  level[pos] = l;

  REP(i, g[pos].size()) if(prev != g[pos][i]){
    calc(g[pos][i], pos, l + 1);
  }
}

int parentOf(int a, int b){
  if(level[a] > level[b]) swap(a, b);

  int diff = level[b] - level[a];
  REP(i,20) if(diff & (1 << i)){
    b = prevs[b][i];
  }

  assert(level[b] == level[a]);
  if(a == b) return a;

  for(int i = 19; i >= 0; i--){
    if(prevs[a][i] != -1){
      if(prevs[a][i] == prevs[b][i]){
	// do nothing
      }else{
	a = prevs[a][i];
	b = prevs[b][i];
	i++;
      }
    }
  }

  if(a == b) return a;
  else return prevs[a][0];
}

int find_min(int v, int w, int pr, int l){
  Nd *vr = table2[v];
  Nd *wr = table2[w];
  Nd *prr = table2[pr];
  Nd *pprr = prevs[pr][0] == -1 ? NULL : table2[prevs[pr][0]];
  Nd *tmp = prevs[pr][0] == -1 ? NULL : table[prevs[pr][0]];;

  while(vr){
    int val = vr->val.key;
    int cnt = countUnder(table[v], val) + countUnder(table[w], val)
      - countUnder(table[pr], val) - countUnder(tmp, val);

    int ocnt = vr->val.cnt + wr->val.cnt - prr->val.cnt;
    if(pprr) ocnt -= pprr->val.cnt;

    // printf("val: %d  cnt: %d  ocnt: %d\n", val, cnt, ocnt);

    if(ocnt > 0 && cnt >= l && cnt - ocnt + 1 <= l) return val;

    if(cnt >= l){
      vr = vr->left;
      wr = wr->left;
      prr = prr->left;
      if(pprr) pprr = pprr->left;
    }else{
      vr = vr->right;
      wr = wr->right;
      prr = prr->right;
      if(pprr) pprr = pprr->right;
    }
  }

  return 0;
}

int main(){
  int N = getInt();
  int Q = getInt();

  x.resize(N);
  level.resize(N);
  prevs = vector<vector<int> >(N, vector<int>(20, -1));
  g.resize(N);
  table.resize(N);
  table2.resize(N);

  REP(i,N){ x[i] = getInt(); }
  REP(i,N-1){
    int a = getInt() - 1;
    int b = getInt() - 1;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  
  vector<int> y = x;
  {
    // Construct
    random_shuffle(y.begin(), y.end());
    FOR(it, y){ root = push(root, Counter(*it, 0)); }
  }

  {
    // Calc all
    calc(0, -1, 0);

    for(int l = 1; l < 20; l++){
      REP(i,N){
	if(prevs[i][l - 1] != -1 && prevs[prevs[i][l - 1]][l - 1] != -1){
	  prevs[i][l] = prevs[prevs[i][l - 1]][l - 1];
	}
      }
    }

    /*
    REP(i,N) printf("level[%d] = %d\n", i + 1, level[i]);
    REP(i,N){
      printf("prevs[%d]: ", i + 1);
      REP(j, 20) printf("%d ", 1 + prevs[i][j]);
      puts("");
    }
    REP(i,N) for(int j = i + 1; j < N; j++)
      printf("%d %d : %d\n", i + 1, j + 1, parentOf(i, j) + 1);

    REP(i,N){ printf("%d:\n", i + 1); traverse(table2[i]); }
    */
  }

  sort(y.begin(), y.end());

  REP(i, Q){
    int v = getInt() - 1;
    int w = getInt() - 1;
    int l = getInt();

    int pr = parentOf(v, w);
    int ans = find_min(v, w, pr, l);

    printf("%d\n", ans);
  }
  
  return 0;
}