kmjp's blog

競技プログラミング参加記です

AtCoder ARC #102 : D - All Your Paths are Different Lengths

遅刻かつ途中離脱なので1問しか解けず。
https://beta.atcoder.jp/contests/arc102/tasks/arc102_b

問題

整数Lが与えられる。
以下の条件の有向グラフを構築せよ。

  • 頂点数Nは20以下であり、各頂点は1~Nのラベルを持つ。
  • コスト付の有向辺を60本まで張ることができる。なお、辺の向きはラベル番号の小さい方から大きい方のみとする。多重辺は許容される。
  • ラベル1からNのパスはL通りであり、総コストは0~(L-1)のL通りを列挙する。

解法

Lの上限が10^6なのがヒントで、NとlogLがほぼ近い値となる。
そこで、2の累乗のコストを持つ辺を組み合わせることを考えよう。

面倒なので頂点数はNに固定する。
2~19の頂点vに対し、以下の辺を張ろう。

  • v→(v+1)にコスト0の辺および2^(19-v)の辺の2本を張る

こうすると、頂点vまでたどり着いたとすると、そこから頂点20にたどり着く手順は2^v通りであり、かつ0~(2^v)-1が網羅できることがわかる。
コストの上限値C=L-1と置く。
Cの各bitの有無を見ていこう。
下から(0-originで)p-bit目が1が立っていたとする。
この際、p-bit目以上がCと一致し、p-bit目が0となるようなコストのパスを作ることを考えよう。
個の場合p-bit目未満は0/1どちらを取ってもよい。よって、頂点1から頂点(20-p)に、Cに対しp-bit目以下を0とした値をコストとする辺を張ろう。

この手順を各ビットに繰り返すと、C未満のコストのパスは全通り列挙できる。
最後に1→20にコストCの辺を張ればよい。
ただ微妙に問題があり、Cの19bit目が立っていると、上記処理に従うと自己ループを張る羽目になってしまう。
この場合、頂点に余りはないが辺は少し猶予があるので、頂点1→2には(2^18)の倍数の辺を(C>>18)-1本だけ張ることでどうにかしよう。

int L;
vector<pair<int,int>> E[21];

vector<int> cand[21];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L;
	L--;
	
	for(i=2;i<=19;i++) {
		E[i].push_back({i+1,0});
		E[i].push_back({i+1,1<<(19-i)});
	}
	
	FOR(i,18) if(L&(1<<i)) if(i!=19) E[1].push_back({20-i,L&~((2<<i)-1) });
	FOR(i,L>>18) E[1].push_back({2,i<<18});
	
	E[1].push_back({20,L});
	
	int N=20,M=0;
	FOR(i,20) M+=E[i].size();
	cout<<N<<" "<<M<<endl;
	FOR(i,20) FORR(e,E[i]) cout<<i<<" "<<e.first<<" "<<e.second<<endl;
	
	cand[1].push_back(0);
	for(i=1;i<20;i++) {
		FORR(c,cand[i]) FORR(e,E[i]) cand[e.first].push_back(c+e.second);
	}

}

まとめ

境界処理が面倒だけど、このNの縛り要る…?
自分の解き方が悪いだけなのかな。