IOI 2008 Egypt過去問 TELEPORTERS - TopCoderとJ言語と時々F#

問題概要

数直線上にいくつかの点のペアが存在し、その片方に乗るともう片方に飛ばされるように(テレポートするように)なっている。全ての点の座標は1以上で2,000,000以下。同じ座標に複数の点は存在しない。

この数直線上で0から出発し、どんどん右へ進んで行く。最終的に座標2,000,001に達した時点でテレポートした回数が得点として得られる。

はじめにあるN個のペアの座標が与えられるので、そこにM個以下の新たなペアを追加して、獲得できる得点を最大化せよ。はじめに与えられるN個のペアの座標は整数だが、新たに追加するペアの座標は0より大きく2,000,001より小さい任意の実数で構わない。

1 <= N <= 1,000,000
1 <= M <= 1,000,000

解法

座標が出てくるが、実際は点同士の左右の関係だけが必要なことや、点から点へ移るということからグラフに落とせそうな感じがする。しかし普通に点をそのまま頂点としてペアを辺で結んでも何ら嬉しいことはないので工夫が必要。

そこで、2N個の点によって分けられる2N+1個の区間を頂点とし、ある区間から出る辺はその区間の右端点からテレポートした先の点を左端点とする区間へのものとする。そうするとそのグラフは1本の経路と複数(0個かもしれない)のサイクルからなることがわかる。

新たなペアを付け加えるとこのグラフに何が起きるかを観察すると次のようなパターンがあることがわかる。

同じ連結成分に属する「同じ」区間にそれぞれ新たな点を置くと、その連結成分の辺数が1本増え、さらに1本の辺からなるサイクルが1つ新たに生まれる。
同じ連結成分に属する2つの「異なる」区間にそれぞれ新たな点を置くと、その2つの区間の間の辺がすべてスキップされる。
違う連結成分に属する2つの区間にそれぞれ新たな点を置くと、その2つの連結成分が合体する。

すると最初のケースでは獲得できる得点が1増え、2番目のケースではその2つの区間の間の辺の数-1だけ得点が減り、3番目のケースでは新たに合体する連結成分の辺の数+2だけ得点が増える。

よって基本的には3番目のケースになるように新たにペアを加えていけばよいが、そのうち連結成分が全て合体して1つになってしまう。そうなったら今度は最初のケースのように新たにペアを加え、その結果できた辺数1のサイクルを3番目のケースを使ってまた合体させるということを繰り返せば良い。

ソース

これも微妙に1秒が切れない。死ぬ。ソースは変数使い回しまくりで汚物。

#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;

int W[1000000], E[1000000];
int P[2000050], T[2000050], C[2000050];
int X[2000050], S[2000050];

int main()
{
  int N, M;
  scanf("%d%d", &N, &M);
  for(int i=0; i<N; ++i)
    scanf("%d%d", &W[i], &E[i]);
  for(int i=0; i<N; ++i)
    P[i] = W[i];
  for(int i=0; i<N; ++i)
    P[i+N] = E[i];
  for(int i=0; i<N<<1; ++i)
    T[P[i]]++;
  int pos = 0;
  for(int i=0; i<=2000000; ++i)
    if(T[i])
      P[i] = pos++;
  for(int i=0; i<N; ++i) {
    W[i] = P[W[i]];
    E[i] = P[E[i]];
    T[W[i]] = E[i]+1; C[E[i]+1] = W[i];
    T[E[i]] = W[i]+1; C[W[i]+1] = E[i];
  }
  T[2*N] = -1; C[0] = -1;
  int components = 0, sol;
  for(int i=0; i<=2*N; ++i) {
    if(X[i] == 0) {
      queue<int> que;
      int cnt = 1;
      X[i] = 1;
      que.push(i);
      while(!que.empty()) {
	int v = que.front(); que.pop();
	if(T[v] != -1 && X[T[v]] == 0) {
	  X[T[v]] = 1;
	  cnt++;
	  que.push(T[v]);
	}
	if(C[v] != -1 && X[C[v]] == 0) {
	  X[C[v]] = 1;
	  cnt++;
	  que.push(C[v]);
	}
      }
      if(i == 0) sol = cnt-1;
      else S[components++] = cnt;
    }
  }
  memset(T, 0, sizeof(T));
  pos = 0;
  for(int i=0; i<components; ++i)
    T[S[i]]++;
  for(int i=1; i<=2000000; ++i)
    for(int j=0; j<T[i]; ++j)
      S[pos++] = i;
  while(M > 0 && components > 0) {
    sol += S[--components] + 2;
    M--;
  }
  if(M > 0) {
    sol += M / 2 + M / 2 * 3;
    if(M % 2 == 1) sol++;
  }
  printf("%d\n", sol);
  return 0;
}