やー楽しかった。たぶん勝ってるんだと思う。水曜は祝日で木曜は会社休んだ。ゴルフはとにかく膨大な時間を使った者が強いのである。
総じてすごい楽しかった。 ICFPC に匹敵する。平日だったのが残念だったけど、本当は休日にやろうとしてたらしいけどトラブルがあったらしい。来年は休日だろうし楽しみ。まだあんまりコード読んでないので今度読む。
KEY
予約語を 50B 、セミコロンを 10B と考えてゴルフ。予約語無しでセミコロン一個は不可避なので、一個でおさえなければいけない。 154 は提出したものより短いものも含めていくつかあったんだけど、なかなか通らなかった。今日まではセミコロン2つ使って、
f(i,j){i?f(i/2,i%2+j*2):j;}
main(a,i){
~scanf("%d",&i)&&main(0,a||puts(i^f(i,0)?"NO":"YES"));
}
とかだった。まぁ 154 は帰り値をなんとかすればなんとかなるはず…ということで今朝頑張ったらなんとかなった。
SHORTEN
色々すごいことになってた問題。 Carmichael Number というものを出力せよ、という問題。
オリジナルのコードは不要なコードに加えて、バグが色々入ってて、そのバグは律義に再現しないといけないものだ、と思い込んでしまっていて、なかなか縮まなかった。あと 10**6 までは test case に含まれていると思っていて、埋め込みじゃだめだよなーと思って、まぁ縮めなくてもたぶんスコア関数修正されるだろーと思って寝たら修正されてなかった。
朝起きて、修正されないみたいだったのでこれはヤバい (確か私が700点くらいで1位は2000越えてるとかいう状態)と思って、 test case の上限を調べてみたところ、埋め込みでイケるんじゃねーと思った。で埋め込みのコードに変えて、さらに必要だと思っていたバグの再現の数々もいらないと判明しまくって、色々縮めて 1700 くらいまで伸びた。
で、終了間際の17時ちょっと前に、会社からコンテストの状態を見てみたらなんか負けるなーというくらいになっていたので、口惜しくてコードをちょっと見てみた。そしたら1分とかからず自明な短縮を発見して、 300 点ほど増えた。
なんかバグを再現してた時の名残りで、入力を全部読んでから処理してたんだけど、明らかにいらなくなっていた…
てか埋め込みじゃなくて解けるんだなー
INPOUT
特定の input をちょっと変換して特定の output にする問題。 C ゴルファーに勝てる気がしない系。
普通に書いたら普通にトップに立てて、普通に放置してたらなんか最後負けてた気がする。ボーナスの 150 点が…
CODEHASH
なにやら自身のハッシュ値を出力せよ、という問題。
最初は、
main(){puts("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA");}//AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
とかいう感じのコードで、 32B 自由にいじれる場所があれば手作業でも答え見つかるよなーと、そんな感じでやっていた。
もうちょいなんとかするかーと思って、
AAAAAAAAAAAAAAAAAA;main(){puts("
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
");}
というコードをベースにしていじれば、右半分は文字列部分を自由にいじって、左半分は main の前の部分で調整できるよねー、とかそんな感じ。
機械的に探索しようかなーと思ったけど、kik さんがトップにいて勝てる気がしなかったので、勝ちにからまない人がボーナスゲットするぶんには問題なかろーと放置。
CLASS
空白無しでクラス定義と関数を書け、という問題。
C のパーサ書いたことあるはずなのに結構考えてしまった。このへんが k との壁を感じますね。まぁそうは言っても得意分野ではあるので楽勝。
PENGUIN
ペンギンさんの絵を出力する圧縮問題。
なんかちょっと複雑な RLE をやってしまった。普通にやった方が良かったのかな。 1 回しか出現しない文字 2 文字は特定の数値を割当てて、残り 8 文字に 3bit 使って残り 5bit が長さとかそんな。
にはさんがなんか吠えてたけど気にしてもしょうがない気がして放置した。
Palindrome quine 。どう書いたら縮むかは覚えてたので、見ても一緒だろーとゴルフ場を見てしまったのであった。 --i/109|1 は自分では思いつかなかった気がする…ごめんなさい。トップじゃなくて良かった。
write 使えばシステムコールだからぬるぽでもいいんだよねーとかやるのが楽しかった。
空白使うのは考えたけど時間がなかった。ウソじゃないよ! 実際 OCaml の CTQUINE は空白埋め込みだし。
NP
問題が徹底的に理解できない問題だった。入力の仕様が間違っていたのが原因だった。まぁ通るようになったら貪欲で今のスコアが出た。ちょっと priority queue で探索するくらいはやってみたけど、スコアが 1 点も増えないので放棄。
NP!=P
最終日に思い出したように適当に提出。
ARBIT
難読化されたコードを読み解いて、意図を汲んで高速化する問題。
何時間考えたことか…コード解読は最初の方は遅いながらも順調に進んだんだけど、 GCD が特定の数より少ないものを数える、という意図がわかってからありえないくらい時間がかかった。
自分で考えたアルゴリズムは全然良いものではなくて、最大10億の a を上からデクリメントしていって割り切れるものがあれば、その数字とその数字の倍数は gcd が 1 以上である、ということで、それが b より上なら勘定する。その時に、例えば a=12 に対して 6 とかだったら、 6 と 12 が gcd 6 以上のものなんだけど、 12 は既に勘定に入ってるので勘定しないようにする。
よくわからん説明だけどそんなかんじ。10億ぶんまわすと遅いので、最初の1ステップで半分にしてすっとばせばギリギリ TLE 喰らわなかった。これで TLE 喰らってたら解けてなかった気がする。危なかったねー。
THINK
暗号を3つ解く問題。
1問目は簡単。2問目は色々考えた。全然思いつかなかったけど、ふと思い立って1問目の問題文を読んでみたらなんと! ヒントがあるではないですか。というわけで2問目が解けた。奇数番目のを取れって書いてあるのに偶数番目取る必要があっていじわるだなあと思った…いや、えーと、というか、 0 からスタートでカウントしてたけど普通に奇数番目取る問題じゃないか!
あ、ここからネタバレ。暗号とかやってみたい系の人は一応注意。
3問目は、暗号内のアルファベットの出現頻度は2問目解く前に調べてあって、英語のそれに一致してることは確認してあったので、 interleave 、というヒントがあったからたぶん方針は間違っていない、と自信を持ってやれたのが良かったと思う。 interleave は 2 種類あるわけだけど、後半の方を先に持ってくる方が正解で、いじわるだなーと思った。まぁ両方やってみると、後者の方は明らかに 2gram に英語らしい自然なバラつきがあるので(前者はランダムな感じ)、まぁいけるだろう…とカンで適当に探していった。
探していった順序は、とりあえず THE っぽいのを見つけて、 THAT じゃないかなぁ…というのにアタリをつけたもののイマイチで、色々頻出してるものに推測を入れていったけどうまくいかなかった。でなんか、 Txyz というような文字列が頻出してる部分が TION じゃないかーということで入れてみると、 EN****TION とかがたくさん出てきて、どう見ても ENCRYPTION ですねーということで終わった。
後はかなり難しいパズルのハードルがあるぶん、強力な相手のいない、アルゴリズムに工夫の余地の無い純然たるゴルフ勝負。負けるわけがない…と思ったら割と一瞬でトップに立って、そのまま負けなかった。
