テストケースが事実上公開されていたおかげで何とか自力正解できた。
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"); } }
まとめ
なかなか面白い問題でした。