Codeforces #700 Div1 : C. Continuous City

定番な気はする。
https://codeforces.com/contest/1479/problem/C

問題

正整数区間[L,R]が与えられる。
以下を満たすグラフを構築せよ。

• 32頂点以下であるのDAGを成す有向グラフである。
• 各辺は正の重みをもつ。
• N頂点のグラフの場合、1番の頂点からN番の頂点に至る経路は、総長がL～Rのものが1つずつある。

解法

• Rが30以下の場合
  • 1～R番の頂点間対し、にi→(i+1)に重さ1の辺を張ろう。
  • あとはL～R番の頂点から、N番の頂点に重さ1の辺を張ればよい。
• Rが31以上の場合
  • [1,2^20]を実現できる20頂点の構成を1つ作る。
  • [L,R]をいくつかの[m,m+2^k-1]の区間の和に分け、上記20点の構成に初手重さmを考慮した辺を張っていくと良い。

int L,R;
int d[32][32];
int N;

vector<ll> D[33];

void add(int f,int t,int v) {
	d[f][t]+=v;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>R;
	if(R<=30) {
		N=32;
		for(i=0;i<=29;i++) add(i,i+1,1);
		for(i=L;i<=R;i++) {
			add(i-1,31,1);
		}
	}
	else {
		int dif=L-1;
		L-=dif;
		R-=dif;
		int ma=0;
		while((1<<(ma+1))<=R) ma++;
		N=ma+3;
		add(0,1,(1<<ma)-2+dif+1);
		for(i=2;i<=ma+2;i++) {
			if(i==ma+2) add(0,i,1+dif);
			else add(0,i,(1<<(ma+1-i))+dif);
			for(j=i+1;j<=ma+2;j++) {
				if(j==ma+2) x=1;
				else x=1<<(ma+1-j);
				add(i,j,x);
			}
		}
		int R2=R-(1<<ma);
		for(i=2;i<=ma+2;i++) {
			if(i==ma+2) x=1;
			else x=1<<((ma+1)-i);
			
			if(R2>=x) {
				add(1,i,R2-(x-1));
				R2-=x;
			}
		}
	}
	
	/*
	D[0].push_back(0);
	FOR(i,N) {
		FORR(e,D[i]) FOR(j,N) if(d[i][j]) D[j].push_back(e+d[i][j]);
	}
	sort(ALL(D[N-1]));
	FORR(v,D[N-1]) cout<<v<<" ";
	cout<<endl;
	*/
	
	
	cout<<"YES"<<endl;
	int M=0;
	FOR(x,N) FOR(y,N) if(d[x][y]) M++;
	cout<<N<<" "<<M<<endl;
	FOR(x,N) FOR(y,N) if(d[x][y]) cout<<(x+1)<<" "<<(y+1)<<" "<<d[x][y]<<endl;
}

まとめ

これ系の問題、大体倍々ゲームでバリエーションを増やすイメージ。