diverta 2019 Programming Contest 2 : F - Diverta City

うーん、これはEditorialを見ると「そりゃそうだ…」って感じの問題。
https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_f

問題

整数Nが与えられる。
N要素の完全グラフの各辺に、正整数の距離を付与したとする。
このグラフの全ハミルトン経路を考える。
その際、全経路の長さが異なるようにしたい（訪問順が逆の物は同一とみなす）。
各経路の長さが10^11を超えない範囲で、そのようなグラフを構築せよ。

解法

N≦9の場合は容易。辺が36本なので、異なる2の累乗値2^0～2^35までの長さをそれぞれ付与すれば、異なる辺を使う経路の長さは異なる。
ただN≦10の場合同じようにすると、2^44の長さの辺が登場してしまい10^11を超える。

そこでもう少し短くすることを考えよう。
今n頂点の条件を満たすグラフがあったとき、(n+1)番の頂点を追加することを考える。
(n+1)番の頂点を通るパスは、(n+1)番とつながる辺のうち1本か2本しか通らない。
よって、要素を1個か2個選んだ時、和が異なる整数集合を考えよう。
すると数列{1, 2, 4, 7, 12, 20, 29, 38, 52, 73}が該当する。
n頂点のグラフにおける最長経路長をMとするとき、(n+1)番の頂点と他の頂点の辺の距離を、先ほどの数列を用いて((M+1)*1,(M+1)*2,(M+1)*4,....)とすればこのグラフは明らかに経路長が重複しない。
また辺毎に倍々で長さを増やさなくてよいので、総長を抑えることができる。

int N;
ll W[10][10];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	W[1][0]=W[0][1]=1;
	for(N=3;N<=10;N++) {
		vector<int> V;
		FOR(i,N-1) V.push_back(i);
		ll ma=0;
		do {
			if(V[0]>V.back()) continue;
			ll ret=0;
			FOR(i,N-2) ret+=W[V[i]][V[i+1]];
			ma=max(ma,ret);
		} while(next_permutation(ALL(V)));
		
		ma++;
		int cand[]={1,2,4,7,12,20,29,38,52,73};
		FOR(x,N-1) {
			W[N-1][x]=W[x][N-1]=ma*cand[x];
		}
	}
	
	cin>>N;
	vector<int> V;
	FOR(i,N) V.push_back(i);
	set<ll> C;
	
	do {
		if(V[0]>V.back()) continue;
		ll ret=0;
		FOR(i,N-1) ret+=W[V[i]][V[i+1]];
		assert(C.count(ret)==0);
		
	} while(next_permutation(ALL(V)));
	
	
	FOR(y,N) {
		FOR(x,N) cout<<W[y][x]<<" ";
		cout<<endl;
	}
}

まとめ

こういうのどうやれば思いつくんだろ。