2599(A funny game)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2599
問題文の詳しい説明はTrisGさんの http://d.hatena.ne.jp/TrisG/20060608 を参考にしてくらはい。
まず、コメントで書いたことを詳しく補足。
ある節に何も接続されていなければ、その節にたどり着いた奴の負けなので、その場合0を返却する。逆に、ある節に接続されている節のうち一つでも0を返却したならば、その節にいる奴はそっちに進めば勝てるので、1を返却する。そして、接続されている節の全てが1を返却した場合、相手に勝たせることしかできず結局負けるのでゼロを返却することになる。
さらに、自分が勝利できる場合は、勝利できる接続先の空港のナンバーを答えてやる必要があるので、その辺も考慮する。
「どら」は最初、入力を文字列で受け取って1000個のchar配列に格納し、sscanfで取り出すというアホなことをやっていた。おかげでTLE(処理時間超過)ギリギリのAcceptになってたようだ。
この問題で再帰の次に重要な点は、入力された接続情報の扱いだろう。再帰する際、例えば3番の空港の接続先を辿ろうとして、元の道を戻ってしまっては本末転倒である。そこで、テロリストよろしく接続情報を消して進みながら探索を行うという方法を取ることにした。
s,n,i,t,a[2000]; d(b){ int i,f,w,u,v,x=1000; for(i=f=w=0;i<n*2-2;i+=2){ u=a[i];v=a[i+1]; if(b==u||b==v){ //どっちの項に自分の接続先が入っているか分からないので両方見る w=b==u?v:u; a[i]=a[i+1]=0; //今辿ってきた接続情報を消す if(!d(w)){if(b!=s)return 1;x>w?x=w:0;f=1;} //TLE対策として、最上段での呼び出しの時にだけ最小のナンバーを検索 } } return f?x:0; } main(){ for(i=!scanf("%d %d",&n,&s);i<n*2-2;scanf("%d %d",a+i,a+i+1),i+=2); (t=d(s))?printf("First player wins flying to airport %d\n",t) :printf("First player loses\n"); }
縮める余地はところどころにあると思うけど、とりあえずこんなんでどうでしょう?
今回の問題、何が嬉しいかって、いつもPascal組に占領されてるメモリ消費量のランキングにCで1ページ目に入ってこれたってこと。ある程度テストケースにも左右されるんだろうけど……。