最初から最後まで全力でがんばりました。8問あって、1問は誰も解けなかったので全7問で、そのうち6問がトップなので割と文句なく1位です。最初の方は期間が2日しか無い予定だったのでとりあえず問題を全部解くのを重視してやってて、後の方は3日に期限がのびたのでゆっくりと一問一問よく見る感じでやりました。
どうでもいいコード群
http://shinh.skr.jp/dat_dir/tle2011/
ARRNG
数字の列をなんか特定の法則に従って並べる。
submit 可能になるまでには解いてたはずなんだけど、何故か通らない。 output の spec とか説明が詳しくなったりして、よく見るとフォーマット違うなーとかいう感じだったけどまだ通らない。しばらく放置してたんだけど、 tanakh さんも通らないとおっしゃってるのを見て、とりあえず ruby で解くかーと解いてみて、どうも C 的なバグは無いっぽいからそもそもなんかおかしい…とわかったあたりで kinaba さんがサンプル入力が偶数だから解釈違っても通るかもーとかおっしゃってたのを見て、あーたしかに別解釈あるかもみたいな感じで解けた。
この問題はセミコロン使うと減点とかループ使うなとかのしばりがあるので、かなり妙な感じのゴルフになった。まぁ割と速い段階で1位ぽい感じになったのであまり細かく縮めてない。
notogawa さんの解答 とか見るとバッファサイズ指定しなくても向こう環境では通ったのかーとか、数値並べるための式とか僕みたいに外部関数使ってないなーとか色々負けてる気がするけど、何故か勝ってる…
COUNTI, ODDEVEN
COUNTI は数字が入力として与えられるので、とある文字列の中のその数字番目の文字が、その文字列の中に何回登場するか答えなさい。とある文字列というのはあなたのソースコードですよ、と。
ODDEVEN は自分のコードの偶数番目のコードと、奇数番目のコードを出力しなさい、と。
普通に Quine 書いてほげほげしてたんだけど、どうも普通に書くと長くなるなーと。あーそういえば sprintf する系の quine は #define と #X とかでの文字列化の方が短くなったりしたなーと書いてたのが
#define q(c)char*d=#c"\nq("#c")";i;main(r,a){for(gets(a);~scanf("%d",&a);printf("%d\n",r))for(i=r=0;i<260;)r+=d[a%260]==d[i++];} q(#define q(c)char*d=#c"\nq("#c")";i;main(r,a){for(gets(a);~scanf("%d",&a);printf("%d\n",r))for(i=r=0;i<260;)r+=d[a%260]==d[i++];})
このあたり。絶望的に長い。
これをほげほげいじったりしていてもラチがあかないので、 COUNTI の方は
printf("%d\n","不思議な文字列"[index/2]>>(index%2?8:0)&255);
みたいな感じで一発解決できる「不思議な文字列」を生成できないもんか! と数時間。壮大な時間のムダ。
結局、 Quine って同じコード2回書くのがだるいわけだよねーということで、
#define q(x,y,z)x#y"\nq("#x","#y","#z")"z q(char*d=,#define q(x,y,z)x#y"\nq("#x","#y","#z")"z,;i;main(r,a){for(gets(a);~scanf("%d",&a);printf("%d\n",r))for(i=r=0;i<191;)r+=d[a%191]==d[i++];})
みたいな形や
#define q(y,z)e=#y"\nq("#y","#z")"z q(#define q(y,z)e=#y"\nq("#y","#z")"z,;char*d;main(r,a){for(gets(a);gets(&a);printf("%d\n",r))for(d=e,a=d[atoi()%175],r=0;*d;)r+=a==*d++;})
みたいなのを考えて、これでも同じコードが入ってる部分があるなーということであくせくして今の形へ。
COUNTI は gets を無理矢理1個にしたり sprintf の戻り値を使ったりしてるうちに一位に。ただしあきらかに落とせる &a が残っていたり。
ODDEVEN の方は使えるバッファはどこかいねーかーと .data 領域を適当に間借りしてたりしてて単独首位に。
HASH
とあるハッシュを計算して、ファイルの前半と後半のハッシュが一致してるかを判定するプログラムを書きなさい。ただし、そのプログラム自体も前半と後半のハッシュが一致してる必要があります。
COUNTI や ODDEVEN と同様、なんでこんな大差がついてるんだ…とずっと悩んでいた問題。 for ループ合成まで動員してこいうコードを書いてた。
l;v,i; char b['XX']; main(w){ for(;gets(b+l)||i++<l&&~(v=(v*256+b[l-i])%1009);i==l/2?w=v,v=0:0)l=strlen(b); puts(l%2|v-w?"no":"yes"); }
でまぁ全然縮まないので、前から改行の位置に関係なくハッシュ求める方法があるに違いない…とか色々考えたけどダメ。
で、どうもバッファに一度保存してから後ろかなめるのがキツい! ということで main 再帰して帰りしなに計算していく力技に。4人もこんなアホコード書いてるわけねーとか思ってたけど、他の人のコード見るに前半と後半同時に計算できるんですね…
アルゴリズムでの負けをゴルフ力だけで乗り切った希有な例と言える…
あとコード自身のハッシュとかは適当に変数名いじって探索してやれば OK 。
HEART
デカい画像をなるべく小さいコードで出力しなさいと。こいうのよくあるんだけど、他との違いは多少誤差があってもペナルティにはなるけどリジェクトされないのと、あと画像がやたらデカいとお。
まずいつも通り RLE した。なんか昔書いた RLE するコードがそのまま使えた。しかしデカい。
誤差許すっていうんだからここは jpeg の真似をして離散コサイン変換だろう…! ということで期限の延期が決まった時点で全力で実装。圧倒的に時間を使った問題なのに唯一トップ取れてないという壮大な時間の無駄。
最終的には、
- 32x32 のブロックに切って離散コサイン変換。ブロックサイズはこんなもんが良いっぽかった。オフラインで実行できるし、数十秒もあれば終わるので O(N^2) のナイーブなやつ
- 係数が小さい項を適当に落として量子化
- DCT が出力したデータを適当に読んで、画質に影響を与えずに捨てていいデータがあるかのチェックと、適当に値を変えるだけで画質が上がるところが無いかを適当に計算するフィルタを通す。このフィルタは3回くらい通したあたりで変化なくなった
- データを見るにハフマンコードが効きそうだったので固定ハフマン
- 画像表示する方はまぁ普通に逆DCTすればOK。
KD
行列に対して、ここの値をアップデートしますよーって命令と、ここの範囲の値を合計して出力してくださいねーという命令があるので、それを実行しなさい、と。
最初書いたやつはナイーブに行列をアップデートしていくもの。全然遅くてお話にならない。
しばらく考えて、オペレーションを全部保存しておいて、アップデートする命令が影響する範囲の出力命令に対して値計算すればいいのかーとか気付いてそのコードを書いた。長い。
かなりしばらく考えて、コンビニとか言ってる間に、ああそうだアップデートする方のオペレーションだけ保存しておいて、出力する方は見た時に今までのアップデート命令をなめるだけでいいのかーと気付いて実装。短くなった。
こうなればもう負ける気しないよねーという感じで適当に縮めてたのだけど、どうも TLE が発生しまくるようになって、縮めたコードがサブミットできなくなってしまった…
notogawa さんのコードと比べると for 文と scanf が一個ずつ僕の方が少ないのできっと無理矢理合成したんでしょうね…
そうそう scanf の %*d はいつも忘れるなあ…
LETTER
A-Z の文字が 13x9 くらいのグリフで与えられるんで、そこから読み取って出力して下さい、どれにもあてはまらない文字に対しては ? を出力してね、と。
ありとあらゆる入力に ? を出力させるとか試すとかはできないだろうから、入力依存なコードになって、 ? を返すべきところに A とか返すとかなってしまってもいいので、グリフから適当なハッシュを計算して、そのハッシュが一致した文字があったらそれを出力するみたいな。
ハッシュはだいたい 2^16 程度のサイズがあればそれなりに通るデータが作れるみたいだったので、うーん short …とかやってた。ああ strstr とかあったよねーとか思って、そういえば memmem とかなかったっけ…とか思い出したあたりで相当良くなった。
この問題は HEART を一時的に1位にしてる間に kinaba さんたちが追い上げてきて抜かされて、せっかく HEART が1位になった時にも 1400 点 (つまり全問題1位) にならなかったという。
ただその時にはずっと h&='\xff\xff' とかいう、 memmem 使ってたらそんなもんいらんやろってコードが残っていて、単にそれを消せば良かったのだったんだけど、それに気付いた頃には HEART が抜かれていた…
OPTI
行列の累乗を計算して下さい、と。ただしタイムリミット厳しいから普通じゃない方法を使う必要がありますよ、と。
アドバイスを無視して普通に実装。うん遅い。ちょっと考える。うーん無理。結局最後まで誰も解いてないから相当な難問なんでしょうね…
まとめ
がんばっただけあって大変良い結果でした。たぶん誰よりも時間使ったんじゃないかなーと予想します。ゴルフは時間ゲーなんですよ結局みたいな。あと気合い入った C golfer がいたらここまでなんでもかんでもトップ取るとかできなかったでしょうね…
思ったのは気分転換は大事だなーということで、メシ喰いに行ったりコンビニ行ったりしてる間に結構アイデア思いついた気がする。 COUNTI と ODDEVEN も会社で縮んだし。
TLE 自体も大変問題も良くて楽しかったと思います。思ったのはもうちょっとオープンエンドな感じの問題があっても良かったかなーというのと (HEART とかは良かったのだけど)、 COUNTI と ODDEVEN が結局似たような問題だったのはちょっと残念だったかなぁと。
