kmjp's blog

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

お誕生日コンテスト : D - 先生と遺書

テストケースが事実上公開されていたおかげで何とか自力正解できた。
http://birthday0410.contest.atcoder.jp/tasks/birthday0410_d

問題

数KとLが与えられる。

50以下のN点からなる無向単純グラフで、各辺が自然数コストを持つもののうち、1番の点からN番の点に移るK番目のパスのコストがLとなるものを答えよ。
なお、1番からN番に移るパスは同じ点・辺を複数回通っても良く、最短路である必要はない。

解法

以下の問題が参考になる。
Codeforces Round 228 B. Fox and Minimal path
Codeforces #228 Div1. B. Fox and Minimal path - kmjp's blog

また、この問題はテストケースのファイル名にK,Lが入っているのでそれを参考に解いていこう。

点同士をたすき掛けすることで同じ長さのパスを複数生成できる。
例えば1→2、1→3と辺を張った後、2→4、3→4、2→5、3→5とたすき上にパスを張ることで、その長さのパスを倍々に増やせる。

コストLのパスをK個以上作ってしまうのが一番簡単。
以下、Lの値で大きく分岐できる。

  • L>=5の場合
    • N=37とする。1→(2~6)→(7~16)→(17~26)→(27~36)→37、とたすき掛けをする。
    • 最初だけの1→(2~6)だけコストをL-4とし、残りを1とすると、5*10*10*10=5000通りの長さLのパスを生成できる。
    • これらはもちろん最短路なので、1~5000番目のパスはいずれも長さLである。
  • L==1の場合:
    • N=2として1→2にコスト1の辺を張るしかない。K==1ならこれで良く、K>=2の場合は生成不可。
  • L==2の場合:
    • N=50として1→(2~49)→50とすれば48通りコスト2のパスを生成できる。
    • さらに忘れてはいけないのが、1→50に直接コスト2の辺を追加すればよい。合わせてK<=49まで対応できる。
  • L==3の場合:
    • たすき掛け方式で考えると、N==50で1→(2~25)→(26~49)→50とすればK<=24*24=576まで対応できる。
    • 実はもっとパスを増やす方法がある。-L==2の時生成した1→(2~49)→50において、(2~49)の間も相互に辺を張ると、1→(2~49)→(2~49)→50と移動する48*47通りのパスができる。さらに、同じ点を複数回通れることを考えると、1→50にコスト1の辺を張ると:
      • コスト1:1→50が1通り
      • コスト2:1→(2~49)→50が48通り
      • コスト3:1→(2~49)→1→50 が48通り
      • コスト3:1→50→(2~49)→50 が48通り
      • コスト3:1→50→1→50 が1通り
      • コスト3:1→(2~49)→(2~49)→50 が48*47通り
      • 合わせてK==50~2402の時コスト3のパスとなる。K>2402の場合は生成不可。
  • L==4の場合:
    • たすき掛け方式で考えると、N==50で1→(2~17)→(18~33)→(34~49)→50とすればK<=16*16*16=4096まで対応できる。
    • 先ほどL==3で構成した1→(2~49)→(2~49)→50について、1→(2~49)→(2~49)→(2~49)→50というコスト4のパスが48*47*47通りあることに気づく。よってK>4096の時はこれを流用すればよい。
int K,L;
void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>K>>L;
	
	if(L==1 && K==1) {
		_P("2 1\n1 2 1\n");
	}
	else if(L==2 && K<=49) {
		_P("50 97\n");
		_P("1 50 2\n");
		FOR(i,48) _P("1 %d 1\n",i+2);
		FOR(i,48) _P("%d 50 1\n",i+2);
	}
	else if(L==3 && K<=24*24) {
		_P("50 %d\n",24*26);
		FOR(i,24) _P("1 %d 1\n",i+2);
		FOR(i,24) FOR(j,24) _P("%d %d 1\n",i+2,j+26);
		FOR(i,24) _P("%d %d 1\n",i+26,50);
	}
	else if(L==4 && K<=16*16*16) {
		_P("50 %d\n",16*34);
		FOR(i,16) _P("1 %d 1\n",i+2);
		FOR(i,16) FOR(j,16) _P("%d %d 1\n",i+2,j+18);
		FOR(i,16) FOR(j,16) _P("%d %d 1\n",i+18,j+34);
		FOR(i,16) _P("%d %d 1\n",i+34,50);
	}
	else if((L==3 && K<=2402) || (L==4)){
		_P("50 %d\n",1225);
		_P("1 50 1\n",1);
		FOR(i,48) _P("1 %d 1\n",i+2);
		FOR(i,48) _P("%d 50 1\n",i+2);
		FOR(i,48) for(j=i+1;j<48;j++) _P("%d %d 1\n",i+2,j+2);
	}
	else if(L>=5) {
		_P("37 %d\n",5+5*10+100+100+10);
		FOR(i,5) {
			_P("1 %d %d\n",2+i,L-4);
			FOR(j,10) _P("%d %d 1\n",2+i,7+j);
		}
		FOR(i,10) FOR(j,10) _P("%d %d 1\n",7+i,17+j);
		FOR(i,10) FOR(j,10) _P("%d %d 1\n",17+i,27+j);
		FOR(i,10) _P("%d 37 1\n",27+i);
	}
	else {
		_P("-1\n");
	}
}

まとめ

なかなか面白い問題でした。