2599その後(2006/06/16)
まず、「どら」が通した201byteのコード。
i,a[998]; d(b,j,w,x){ for(j=*a*2,x=a;--j-1;) a[j^1]==b?a[j]-=w=a[j],x=d(w)|x<w?x:w:1; i=x<a?x:0; //returnが無いのに関数が評価できるのはなぜ……? //x<a?i=x:(i=0); //これだけで通らなくなる。同じ意味じゃないの? i=i;とかを後に入れても同じ。 } main(){ for(;~scanf("%d",a+i++);); printf(d(a[1])?"%swins flying to airport %d" :"%sloses","First player ",i); }
Ozyさんのコードとの違いは、ゼロを代入する部分が一つ減っていること、あとなぜか<b>returnが無い</b>こと。
とりあえず前者。スタートの空港が3番だとすると、3番が含まれている2つの数字を検索しにいく。(5,3)とかを発見したら関数に5を入れて再帰していくわけだが、この際、もう一度(5,3)を発見すると無限ループになる。そのため(5,3)の部分にゼロを入れる必要がある。このとき、5と3を両方ゼロにする必要は無くて、再帰で呼び出した5の方をゼロにしておけば無限ループは起こらない。(0,3)という組はもちろん5の検索には影響しないし、3の組としてゼロが選ばれることも起こらない(3の検索の続きはその次からなので)。また、それ以降の5からの呼び出しで3に繋がることは問題の定義上あり得ない(全ての空港は一意に接続されているから)。よって、片方にゼロを入れておけば済むということが分かる。
後者については、なぜ通るのかが「どら」には理解できない。returnしない関数ってどうやって評価されるの?(<b>追記:関数の最後で代入された式の値が返るようです</b>)
Ozyさんのコードがヤバイのは関数の再帰呼び出しの引数の部分で演算をしつつ値を渡しているところ。後ろの方にある引数が先に評価されていきながら値が渡されるワケだ。あと、最小値探索で発見できない場合も最小値xに自分自身を代入すれば良いというのには全然気付かなかった……。
それと、Ozyさんの話ではダウンカウンタで回ったときは最後に発見した値を空港の番号の最小値にしても平気らしい。あと空港の数は最大1000なので、配列は1000*2=2000のサイズが要るはずなのだが、そんな限界ぎりぎりのケースもないらしい……。「どら」も998で通った時にはびっくりした。いいのかなぁこれ?
以上を統合すると、
i,a[998]; d(b,j,w,x){ for(j=*a*2,x=a;--j-1;) x=a[j^1]-b||d(w,a[j]-=w=a[j])?x:w; i=x<a?x:0; } main(){ for(;~scanf("%d",a+i++);); printf(d(a[1])?"%swins flying to airport %d": "%sloses","First player ",i); }
これで195byte! returnの部分がもっとはっきりすればまだ縮むかも? 例えば、i=0をforの初期化の部分に入れておいて、xの代入の部分でiにも代入するとか。理論上は同じ動作のはずなのだが、なんでかWAになる。うーむ……。
今回縮めていくモチベーションを保てたのは、ひとえにOzyさんのおかげ。「ぴったり追いついたら止めよう」って思ってたけど、なぜか逆転しちゃうし、そしてすぐに抜かれるし……。「より短くなる」って分からないと縮める気力ってなかなか出ない。
また追記。最小値探さなくてもいいならまだ削れた。何度かコードが変わったのでちょっと整理。
i,a[998]; d(x,b,j,w){ for(j=*a*2;--j-1;)x=a[j^1]-b||d(a[j]=0,w=a[j])?x:w; i=x; } main(){ for(;~scanf("%d",a+i++);); printf(d(0,a[1])?"%swins flying to airport %d": "%sloses","First player ",i); }
以上が186byte。xの初期値を用意して引数の順序を変えてこんなんになった。けどテストケース依存。問題の定義に合わせると、最小値比較の部分を入れる必要がある。よく見たら「引数の順序を変える」って、Ozyさんが示したコードが既にそうなってました。合わせるときに見逃してました……。
以下、今回のなんとなくまとめ。時系列ごとにちゃんとコードを手元に残しておけばよかったかな……。
- やねさんのBlogのコメント欄から辿ったTrisGさんのBlogから、2599番に出会う。
- 再帰することで問題が明快に解けることに気付く。490くらいのコードを通す。
- そこから果てしないShort Codeの道のりが始まる……。
- 最初に300を切ったとき、「自分ならここから280切れば御の字で、他の人なら250を切るだろう」などと考える。
- 最小値判定の初期値に配列のアドレスを使うというアイデアが効き、あっという間に270台に突入する。
- ところどころで、ドモルガンの法則で条件を反転させるという方法にお世話になる。三項演算子に影響が大きい。
- Ozyさんが250を切っているにも関わらず自分が260台だったので、アルゴリズムの変更を検討する。
- 関数d中の配列の巡回を2個飛ばしではなく1個ずつの移動でも題意を満たせることに気付く。240台へ。
- ダウンカウンタで巡回すれば条件判定が簡単になると気付くが、なぜかうまくいかない。
- もしかして、入力の最後あたりにWAを導くような類のダミーデータが入っているのでは? と思いInput解析で確かめる。どうもそれっぽい?(あとで運営へ指摘があり修正が行われたそうです)
- おかげで、配列への入力を正確にn列分で停止させるか、あるいは配列巡回の範囲を制限するかのどちらかを行う必要が出てきた。
- しばらくの間、その2通りの方法を行ったり来たりする。
- 巡回範囲の判定に、最初に読み込んだ空港の数が使えることに気付いたので、最終的に巡回範囲を制限する方にした。scanfが単純になるのが大きい。
- 配列の巡回方法も、ダウンカウンタとアップカウンタをしばらく行ったり来たりする。
- この頃printfとscanfの個数を減らせることに気付く。かなり効果が大きく、220台へ。
- 階段からすっころび、尾てい骨を酷く痛める。( TωT)
- PKUにメールメッセージ機能があることを知る。問題ごとの掲示板もあるし、これって一種のSNSなのかな?
- この辺よりかなり前から「もう、Ozyさんにぴったり追いついたらそこで止めよう」と思い始めた。
- なぜか逆転する。
- すぐに逆転される。長いことその繰り返しが続く。
- 再帰関数内での変数の宣言を、仮引数の宣言に移すという短縮を思いつく。
- 再帰呼び出しの前に、呼び出し元の数値が入っている所をゼロクリアしていたが、逆に呼び出そうとする方を保存してゼロクリアした方が、関数呼び出しにゼロが入ってこなくなり条件判定が単純になるという事実に気付く。
- 配列の巡回方法を「部分的に」逆転することによってゼロクリアのコードが短くなることに気付く。
- printfでの条件判定前の代入で括弧が余計に必要なのに困っていたが、代入を再帰関数内に移すという奇策を思いつく。
- 再帰関数のreturnを削ったのになぜかAC。
- Ozyさんのコードと合わせ199に。
- テストケースの貧弱さに依存して186に……。いいのかなぁ?
- ちなみにテストケースをきちんとすると200っぽい。rejudgeが不安なので一応それで通しておいた。
2599(A funny game)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2599
問題文の詳しい説明はTrisGさんの http://d.hatena.ne.jp/TrisG/20060608 を参考にしてくらはい。