IOI2010 Saveit

最短路長を送る問題。すごく面白かったので思考過程とか書いておきます。

まず、そのまま最短路長を送っても求めるもの1つにつき10Bitsが必要で36*1000*10=360000Bitsくらいかかってしまいまともな点が取れないので、最短路長の持つ性質を考える。

最短路長は、グラフの隣り合う頂点での差の絶対値が1以下という性質を持っている。

この性質をうまく使えば、だいぶBit数を削れそうである。グラフの一部を削って列にすることができれば、各ハブについて最短路長が列の前のものより1大きいか、1小さいかそれとも同じかというデータを送れば全部の答えがわかる。

しかし、グラフの一部を削って列にするのはハミルトン経路問題なのでどうしようもない。ということで、となりあう頂点の組を持っておきたいので、列ではなく適当な根つき全域木にすることを考える。

根つき全域木上で、それぞれのハブについて根についての最短路長と、根以外のノードについて親ノードとの差を送れば、最短路が計算できるので、これを実装する。

この手法だと、木のデータを送るところでは各ノードに関して親ノードの番号を持っておけばいいので1000(頂点数)*10=10000Bitsかかり、根についての最短路長は36(ハブの数)*10=360Bits、各ノードに関してのデータは親ノードに対して最短路長が+1か、-1か、同じかの情報を一つあたり2ビットで表せば36(ハブの数)*1000(頂点数)*2=72000Bitsとなり、全部を足すと82360Bitsとなり少し足りない。(実際は根に関する情報などは送らなくていいのでもう少し削れるが70000Bitsには到底届かない)。

実は本質はここまでである。あとはおまけにすぎない。(それは部分点の制約からも容易に感じ取ることはできる)

いま、無駄に情報を送信している部分がどこかを考える。すると、3通りの情報を送るのに2ビットも使っているのが明らかに無駄である。これを圧縮してけずれれば良い。
いま、3^5<=2^8より、(3通りの情報)を5つ分というものを8ビットに圧縮して送ることができる。これを行うと、先ほどの72000Bitsが4/5倍の57600Bitsになり、全部足しても69960Bitsとなって(かなりぎりぎりだが)満点を取ることができる。(実際には自分自身への最短路は0なので360Bitsは送らなくてもいいが実装を楽にするために送っている)

考えるべきことは多いが、「となりあう頂点の最短路長の差の絶対値は1以下」ということ(典型テク?)にさえ気づければあとは筋道をたてて考えれば解法は見えてくると思う(がIOI2010のボス問だったらしいのでそんなことはないのかもしれない)。実装もかなり楽である。

実装では、根についての親ノードのデータを送っていないので69960Bitsよりほんの少し少ない送信量で解いている。

以下コード

encoder

#include<stdio.h>
#include "grader.h"
#include "encoder.h"
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int>pii;
void encode(int cit, int hab, int way, int *va, int *vb)
{
  vector<int>pat[1000];
  int dist[36][1000];
  for(int i=0;i<way;i++)
    {
      pat[va[i]].push_back(vb[i]);
      pat[vb[i]].push_back(va[i]);
    }
  for(int i=0;i<hab;i++)
    {
      for(int j=0;j<cit;j++)
	{
	  dist[i][j]=-1;
	}
    }
  for(int p=0;p<hab;p++)
    {
      queue<pii>que;
      que.push(make_pair(0,p));
      for(;;)
	{
	  if(que.empty())
	    {
	      break;
	    }
	  pii zan=que.front();
	  que.pop();
	  if(dist[p][zan.second]!=-1)
	    {
	      continue;
	    }
	  dist[p][zan.second]=zan.first;
	  for(int i=0;i<pat[zan.second].size();i++)
	    {
	      if(dist[p][pat[zan.second][i]]==-1)
		{
		  que.push(make_pair(zan.first+1,pat[zan.second][i]));
		}
	    }
	}/*
      for(int i=0;i<cit;i++)
	{
	  printf("%d %d %d\n",p,i,dist[p][i]);
	  }*/
    }
  queue<int>que;
  bool flag[1000];
  int par[1000];
  fill(flag,flag+1000,false);
  fill(par,par+1000,1023);
  que.push(0);
  for(;;)
    {
      if(que.empty())
	{
	  break;
	}
      int zan=que.front();
      que.pop();
      if(flag[zan])
	{
	  continue;
	}
      flag[zan]=true;
      for(int i=0;i<pat[zan].size();i++)
	{
	  if(!flag[pat[zan][i]])
	    {
	      que.push(pat[zan][i]);
	      par[pat[zan][i]]=zan;
	    }
	}
    }
  for(int i=1;i<cit;i++)
    {
      for(int j=9;j>=0;j--)
	{
	  encode_bit((par[i]>>j)&1);
	}
    }
  for(int i=0;i<hab;i++)
    {
      for(int j=9;j>=0;j--)
	{
	  encode_bit((dist[i][0]>>j)&1);
	}
    }
  for(int i=0;i<hab;i++)
    {
      int now=0;
      for(int j=1;j<cit;j++)
	{
	  now*=3;
	  if(dist[i][par[j]]==dist[i][j])
	    {
	      now+=0;
	    }
	  if(dist[i][par[j]]==dist[i][j]+1)
	    {
	      now+=1;
	    }
	  if(dist[i][par[j]]==dist[i][j]-1)
	    {
	      now+=2;
	    }
	  if(j%5==0||j==cit-1)
	    {
	      for(;;)
		{
		  if(j%5!=0)
		    {
		      j++;
		      now*=3;
		    }
		  else
		    {
		      break;
		    }
		}
	      for(int k=7;k>=0;k--)
		{
		  encode_bit((now>>k)&1);
		}
	      now=0;
	    }
	}
    }
}

decoder

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#include "grader.h"
#include "decoder.h"
using namespace std;
void decode(int cit, int hab)
{
  int par[1000];
  vector<int>ko[1000];
  int st[36];
  par[0]=-1;
  for(int i=1;i<cit;i++)
    {
      int now=0;
      for(int j=0;j<10;j++)
	{
	  now*=2;
	  now+=decode_bit();
	}
      par[i]=now;
      ko[now].push_back(i);
    }
  for(int i=0;i<hab;i++)
    {
      int now=0;
      for(int j=0;j<10;j++)
	{
	  now*=2;
	  now+=decode_bit();
	}
      st[i]=now;
    }
  for(int p=0;p<hab;p++)
    {
      int data[1000];
      data[0]=st[p];
      int cod[1000];
      for(int i=0;i<(cit-1+4)/5;i++)
	{
	  int now=0;
	  for(int j=0;j<8;j++)
	    {
	      now*=2;
	      now+=decode_bit();
	    }
	  for(int j=0;j<5;j++)
	    {
	      if(i*5+1+4-j<cit)
		{
		  cod[i*5+1+4-j]=now%3;
		}
	      now/=3;
	    }
	}
      for(int i=1;i<cit;i++)
	{
	  if(cod[i]==0)
	    {
	      data[i]=0;
	    }
	  if(cod[i]==1)
	    {
	      data[i]=-1;
	    }
	  if(cod[i]==2)
	    {
	      data[i]=1;
	    }
	}
      queue<int>que;
      que.push(0);
      for(;;)
	{
	  if(que.empty())
	    {
	      break;
	    }
	  int zan=que.front();
	  que.pop();
	  if(zan!=0)
	    {
	      data[zan]+=data[par[zan]];
	    }
	  hops(p,zan,data[zan]);
	  for(int i=0;i<ko[zan].size();i++)
	    {
	      que.push(ko[zan][i]);
	    }
	}/*
      for(int i=0;i<cit;i++)
	{
	  printf("%d %d %d\n",p,i,data[i]);
	  }*/
    }
}