Competitive Programming Advent Calendar 2015の18日目の記事です。本記事では、私が作問した数少ない問題の一つであり、AOJ-ICPC非公式難易度表でもありがたいことに高い評価を頂いている箱根駅伝に関して、問題の出来た経緯や、当初の想定解法などに関して書いていこうと思います（もう３年前の問題だし今更感漂うけどもうネタが枯渇してきてるんです、すみません･･･）。
※ちなみに、題名の「もうひとつの箱根駅伝」というのは、毎年箱根駅伝が行われた1週間後くらいに放送される箱根駅伝の裏側や出場した選手のインタビューなどをまとめた番組の名前です。
さて、この問題が出来た背景ですが、これはそのまんま問題文に書いてあるとおり、箱根駅伝をテレビで見ているときに思いつきました。
箱根駅伝では各中継所でこの写真のように通過順位・トップとの差に加えて、前の中継所より順位を挙げたか下げたかが表示されるのですが、この情報から前の中継所の順位を推測するのを問題に出来ないか？と思いました。ちなみにこの中継所の写真が第何回大会のどこの中継所か分かる人いますか？もし分かる方がいたら箱根駅伝に関して大いに語り合いましょう（笑）
とりあえず前の中継所でありえた順位の組み合わせの数は、例えば前の中継所の順位を上から見ていって、今の中継所のどの順位のチームを使ったかを記録したbitDPを使えば2^nとかで求められることはすぐに浮かびました。実際に行われている箱根駅伝と同様にn=20とかにすればこの解法でも十分ですが、流石にちょっとつまらないのでもうちょっと高速な解法がないか考えていました。で、色々と考えてみて思いついたのが以下の解法です。
最初に前の中継所の順位を上から見ていきます。で、各チームの前の中継所でありえた順位の範囲を表すと下の図のようになります。ここで、青色で範囲を表したのは順位を落とした（＝前の中継所での順位は今より高い）チーム、赤色で範囲を表したのは順位を上げた（＝前の中継所での順位は今より低い）チームです。
こうすると、前の中継所の順位を上から見ていってそれぞれに各チームを当てはめていくとき、青色のチームに関してはどのチームを当てはめたかを記録しておかなければいけない（でないと次に当てはめられるチームの数が何通りかが違ってきてしまう）のに対し、赤色のチームは単に当てはめたチームの数を記録してさえいればいいことが分かります（当てはめたチームに関わらず次に当てはめられるチームの数が何通りかは一定）。
つまり2^(青色のチームの数)*多項式時間とかで解けるようになり、さらに順位を全部ひっくり返して考えればこの青色のチームと赤色のチームが逆になるので数が少ない方を青色のチームに当てはめればいいので2^(n/2)で出来るようになります。
こうすればn=36くらいまではいけるかなーと思ってこの解法で直前まで準備していたのですが、直前で他の方が多項式時間での解法を見つけたので急遽制限を差し替えての出題となりました。つまり、皆さんに良問と入っていただいてる所以である解法に関しては全く自分が生み出したものではなかったという訳です（汗）。ただまぁ、自分としては、大好きな箱根駅伝を題材にした問題を出してみたら解法が凄い綺麗なことになったので凄い棚から牡丹餅的ですが満足しています。
それにしても、この当初考えてた解法も自分としては割とお気に入りだったんですけどねぇ･･･特に、ひっくり返せるから少ない方を指数の方に乗っけられて計算量の上限が絞れるって辺りが（まぁこの考え方自体は既出だろうけど）。こんな感じの解法でしか解けない問題ってないかなぁ･･･。
ちなみに想定解法の解説に関してはJAGのページにありますし、satashunさんも記事を書かれてるのでそちらを参考にどうぞ。
これだけじゃあまりにもなんなので、出題後に気付いた別解というか、別の見方に基づいた解法に関してもちょっと説明してみたいと思います。
まず、「当初の解法」の項で使った図をもう一回見て見ましょう。
ここで、同様に前の中継所の上の順位のチームからどのチームを当てはめるか考えていきます。ここで青色のチームは具体的に「この順位はこのチーム」と当てはめようとしてしまうと、状態を保存するのに指数オーダーかかってしまいます。
以後青色のチームの並びのみについて考えます。ここで、具体的なチームではなく、各順位に当てはめたチームの「今の中継所での前後関係」が何通りありえるか、というのをDPの値として持つようにします。例えば、前の中継所で1位、2位、･･･、n位だったチームの今の中継所での順位がx_1位、x_2位、･･･、x_n位だった時、x_1,x_2,...,x_nの「大小関係」が何通りあるかを値として持ちます（例えば、3位まで見てx_1>x_2>x_3とx_1>x_3>x_2のみありえて他の大小関係がありえなければ2通りとなる）。
この情報だけで十分であることを説明します。最終的には大小関係が分かれば具体的な当てはめ方も一意に定まります。後は少々つたなくて申し訳ありませんが下の図をご覧下さい。
で、これに加えて最初の図での赤いチームに関しても考慮すると、dp[当てはめた青いチームの数][当てはめた赤いチームの数]=(青いチームの順位の大小関係が何通りか*赤いチームの当てはめ方は何通りか)というDPが出来ます。コードは以下のようになります。
#define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) lint dp[210][210]; int okr[210],okl[210]; lint mo=1000000007; int main() { int n,u=0,d=0;string s[210]; cin>>n; rep(i,n){ cin>>s[u+d]; if(s[u+d]=="U") u++;else if(s[u+d]=="D") d++; } memset(dp,0,sizeof(dp));dp[0][0]=1; rep(i,u+d+1) rep(k,u+d){ if(s[k]=="U" && k<i) okr[i]++; if(s[k]=="D" && k>i) okl[i]++; } rep(i,d+1) rep(j,u+1){ dp[i][j]%=mo; if(d-okl[i+j+1]<=i){ dp[i][j+1]+=dp[i][j]*(okr[i+j]-j); } if(d-okl[i+j+1]<=i+1){ dp[i+1][j]+=dp[i][j]*(i+1-(d-okl[i+j])); } } cout<<dp[d][u]<<endl; }
またこの考え方を用いることで、この箱根駅伝に良く似た問題であるSRM613Hard TaroCheckersも解くことが出来るようになります（元々の箱根駅伝の想定解を変えることで解こうとするのはちょっと大変そう）。
さて、どうだったでしょうか。この記事の知見が少しでも問題を解く時に役立ってくれたら幸いです。そして箱根駅伝本大会ももうすぐですね、この問題を気に入ってくれた方がいれば箱根駅伝自体にも興味を持ってもらえると嬉しいです。
明日の担当はkuuso1さんとhadroriさんです。こちらもお楽しみに！
imosさんの幾何ビジュアライザを使ったのだけど、この記事はjavascriptド素人の自分にはやや説明不足で、追加でちょっと調べる必要があった。多分みなさんは普通に使えると思うけど、一応どうすれば見れるかメモ。
まず、
<html> <head> <script> function line(x,y,a,b){c.b();c.moveTo(x,y);c.lineTo(a,b);c.s();} function circle(x,y,r){c.b();c.arc(x,y,r,0,7,0);c.s();} window.onload=function(){d=document;d.i=d.getElementById;c=d.i('c').getContext('2d');c.b=c.beginPath;c.s=c.stroke;d.i('s').src='data.js?';}; </script> </head> <body><canvas id="c" width="500" height="500" style="border:1px solid #000;"></canvas> <script id="s"></script></body> </html>
というコードを書いて（1,2,8,11行目が追加）、vis.htmlとかのhtmlファイルとして保存する。で、元記事に書いてあるようにdata.jsというファイルにどういう直線や円を書くかという指定を記述して、このhtmlファイルをブラウザで開けば図が見られる。
他にも方法はあると思うけど、とりあえずこの方法をやれば見れるっていうメモってことで。
2010年の国内予選のG問題。光が逆行するのを許してしまっていて答えが合わず苦しんだ。
//10ICPC国内予選G レーザー光の反射 (AOJ1171) //include、ライブラリ略 #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) seg se[8][8]; int zyo[8][8]; double cal(vector<int> a,int n,Pt ta,Pt le){ int m=a.size(); rep(i,m-1){ if(a[i]==a[i+1]) return inf; } rep(i,m) rep(j,n){ if(j!=a[i]) se[i+1][j]=seg(ref(se[i][a[i]].s,se[i][a[i]].t,se[i][j].s),ref(se[i][a[i]].s,se[i][a[i]].t,se[i][j].t)); else se[i+1][j]=se[i][j]; } rep(i,m) ta=ref(se[i][a[i]].s,se[i][a[i]].t,ta); vector<Pt> p;p.pb(le); rep(i,m){ if(!iSSstrict(ta,p[i],se[i][a[i]].s,se[i][a[i]].t)) return inf; p.pb(pLL(ta,le,se[i][a[i]].s,se[i][a[i]].t)); } p.pb(ta); rep(i,p.size()-1){ rep(j,n){ if(iSSstrict(p[i],p[i+1],se[i][j].s,se[i][j].t)) return inf; } } return (le-ta).abs(); } int main() { Pt ta,le; rep(i,7){ zyo[i][0]=1; rep(j,7) zyo[i][j+1]=zyo[i][j]*i; } int px,py,qx,qy,n; while(cin>>n,n){ double ret=inf; rep(i,n){ cin>>px>>py>>qx>>qy; se[0][i]=seg(Pt(px,py),Pt(qx,qy)); } cin>>px>>py;ta=Pt(px,py); cin>>px>>py;le=Pt(px,py); rep(i,6) rep(j,zyo[n][i]){ vector<int> a;int b=j; rep(k,i){a.pb(b%n);b/=n;} double ca=cal(a,n,ta,le); ret=min(ret,ca); } printf("%.12f\n",ret); } }
ある頂点集合が連結である確率をbitDPで求める。求め方は、「その集合の中のindexが最小の要素を含む連結成分が集合より小さい」確率を求めて1から引く。その確率は、全ての（最小の要素を含み、元の集合よりは小さい）部分集合における「部分集合が連結である確率」*「部分集合が補集合と繋がっていない確率」の和。O(N^3*N)
//11年度冬コンテストF NetworkReliability (AOJ2345) #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) double dp[(1<<14)+10]; double pr[16][(1<<14)+10]; double gr[16][16]; int main() { int n,m,p,a,b; rep(i,16) rep(j,16) gr[i][j]=0.0; cin>>n>>m>>p; rep(i,m){ cin>>a>>b;a--;b--;gr[a][b]=gr[b][a]=0.01*(100-p); } rep(i,n) rep(j,(1<<n)){ pr[i][j]=1.0; rep(k,n){ if((j&(1<<k))) pr[i][j]*=1.0-gr[i][k]; } } REP(i,1,(1<<n)){ int lo; while(!(i&(1<<lo))) lo++; dp[i]=1.0; for(int j=i;j>0;j=((j-1)&i)){ if(j==i || !(j&(1<<lo))) continue; double t=dp[j]; rep(k,n){ if((j&(1<<k)) || !(i&(1<<k))) continue; t*=pr[k][j]; } dp[i]-=t; } } printf("%.12f\n",dp[(1<<n)-1]); }
去年の国内予選で引退に追い込まれた憎き問題。
最初vectorで書いてたらTLE喰らった。やっぱりvectorの代入って重いんだな･･･。
//ICPC国内予選14F サイコロ職人(AOJ1197) #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) string inf="impossible"; int t[6],u[6],w[6]; bool ok(void){ rep(i,6){ if(u[i]<0) return false; } int a=u[0]+u[5],b=u[1]+u[3],c=u[2]+u[4]; if(a>b+c || b>a+c+1 || c>a+b+1) return false; return true; } string cal(int a,int b){ rep(j,6) u[j]=w[j]; if(!ok()) return inf; int d,n=0;rep(i,6) n+=w[i]; string ret=""; rep(i,n){ //E rep(j,6) u[j]=w[j]; d=u[0];u[0]=u[1];u[1]=u[5];u[5]=u[3];u[3]=d; u[5]--; if(ok()){rep(j,6) w[j]=u[j];ret+='E';continue;} //N rep(j,6) u[j]=w[j]; d=u[0];u[0]=u[2];u[2]=u[5];u[5]=u[4];u[4]=d; u[5]--; if(ok()){rep(j,6) w[j]=u[j];ret+='N';continue;} //S rep(j,6) u[j]=w[j]; d=u[0];u[0]=u[4];u[4]=u[5];u[5]=u[2];u[2]=d; u[5]--; if(ok()){rep(j,6) w[j]=u[j];ret+='S';continue;} //W rep(j,6) u[j]=w[j]; d=u[0];u[0]=u[3];u[3]=u[5];u[5]=u[1];u[1]=d; u[5]--; if(ok()){rep(j,6) w[j]=u[j];ret+='W';continue;} } return ret; } int main() { int a,b; while(cin>>t[0]>>t[1]>>t[2]>>t[3]>>t[4]>>t[5],t[0]+t[1]+t[2]+t[3]+t[4]+t[5]){ sort(t,t+6); string ret=inf; cin>>a>>b;a--; while(1){ rep(j,6) w[j]=t[j]; string s=cal(a,b); if(ret==inf) ret=s; else if(ret>s) ret=s; if(!next_permutation(t,t+6)) break; } if(ret==inf) cout<<ret<<endl; else cout<<ret.substr(a,b-a)<<endl; } }