DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦 : E - 飾りつけ (Decoration)

本番に詰めるのは大変そう。
https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_e

問題

1～2000の整数の部分集合が与えられる。
N頂点(53以下)の有向距離付グラフのうち、1番からN番の頂点への移動距離の集合が、入力とちょうど一致するようなものを構成せよ。

解法

92頂点用意してsourceとsink以外を２等分し、source→45頂点→45頂点→sinkとすると、真ん中の45頂点×45頂点の部分で2000通り以上の辺を生成できるので、これは明らかに条件を満たせる。
ただこれでは92頂点もかかるのでもっと減らさないといけない。

組み合わせがかかる部分が1回だけなのがまずいので、(Source含む4頂点)→A頂点→(sink含むB頂点)とし、4+A+B≦53となるようにしよう。
まず部分集合を分割する。1つの分割分には、最大で3までの差がある要素のみ入れる。(最大4要素入る)
そうすると、各分割分について、分割内の最小値以外に、(最小値+1)(最小値+2)(最小値+3)のそれぞれがあるなし8通りが考えられる。
各分割分をこの8通りに分割しよう。

A頂点をそれぞれこの8通りで分割する。
この際、f(mask) := 8通りのbitmaskに該当する要素数　としたとき、sum(ceil(f(mask)/B))≦AかつA+B+4≦53となるA,Bを求めておこう。

あとは最初の4頂点をW,X,Y,Zとする。W→X→Y→Zとそれぞれ長さ1の頂点で辺で結ぼう。
A頂点は8通りに分割したが、それぞれW,X,Y,ZのうちWおよびbitmaskの3bitに対応するX,Y,Zから、A中の各要素に長さ0の辺を張ろう。
あとはA→Bの間に、各分割の最小値に対応する長さの辺を張ろう。

int Q;
int ok[2020];
vector<int> T[16];
vector<vector<int>> E;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	srand(time(NULL));
	FOR(i,Q) {
		cin>>x;
		//x=rand()%1999+1;
		ok[x]=1;
	}
	
	for(i=1;i<=2000;) {
		if(ok[i]==0) {
			i++;
		}
		else {
			int mask=0;
			mask |= ok[i++]<<0;
			mask |= ok[i++]<<1;
			mask |= ok[i++]<<2;
			mask |= ok[i++]<<3;
			T[mask].push_back(i-4);
		}
	}
	
	int best=1010,need=1010;
	for(i=1;i<=1010;i++) {
		int tot=0;
		for(j=1;j<=15;j++) tot+=(T[j].size()+i-1)/i;
		if(tot+i<need) {
			best=i;
			need=tot+i;
		}
	}
	
	need+=4;
	E.push_back({0,1,1});
	E.push_back({0,2,2});
	E.push_back({0,3,3});
	int cur=4,end=4+(need-best-4);
	for(i=1;i<=15;i++) if(T[i].size()) {
		FOR(x,T[i].size()) {
			if(x%best==0) FOR(j,4) if(i&(1<<j)) E.push_back({j,cur+(x/best),0});
			E.push_back({cur+(x/best),end+x%best,T[i][x]});
		}
		
		cur+=(T[i].size()+best-1)/best;
	}
	for(i=end;i<need-1;i++) E.push_back({i,need-1,0});
	
	cout<<need<<" "<<E.size()<<endl;
	FORR(e,E) cout<<e[0]+1<<" "<<e[1]+1<<" "<<e[2]<<endl;
	
	
	
}

まとめ

こういう構築ゲー、文章での説明が面倒でだいぶ省略してしまう。