naiの日記

ソフトウェアエンジニアから放射線科診断医にジョブチェンジしました。趣味のことを書きます。

TLE 2k14

programming shortcoding

TLE 2k14に参加しました。TLE (Time Limit Exceeded) とは、インドの会社が毎年やっているC/C++のCode Golfの大会です。単なるCode Golfではなく、非常に頭のおかしい問題が多数出題されることが特徴です。多分去年は無かったんだけど隔年になったのかな？

最終結果は3位でした。以下、各問題について感想をつらつらと。

IMPRINTS

  • "Threads 2k14"と出力してね。

問題文には「最初だから簡単に行こう」とか書かれてたけど、ちょっと簡単すぎないでしょうか。今回のTLEは全体的に簡単になった傾向が強く、この問題も難易度調整の煽りを受けているのかもしれません。あるいは、CでのGolfをあまりやったことのない方でも気軽に参加できるようにという配慮でしょうか。
なお、この大会では最後に0を返さないとRuntime Errorとなってしまいますが、exit(0)やreturn 0は長いため、グローバル変数に0を代入することでeaxレジスタを0にしています。

i;main(){i=!puts("Threads 2k14");}

ASCII

毎年恒例の巨大アスキーアート問題ですが、この問題もいつもより随分簡単になっています。アスキーアートをよく見ると改行以外には'@'と'1'の2種類の文字しか出現せず、改行も一定文字ごとで固定です。よって、改行を無視した長さのみを覚えておけば元のアスキーアートを復元できます。
長さはおおよそ256以下なのでほとんど1個1Bでデータを持てます。これで600B強、終了直前に少し縮めて585Bでした。
kinabaさんの解法を読むと、結構真面目に各ビットを使って圧縮しているようです。おそらくuntanglerさんも同じような手法を使っているのでしょう。すごいなあ。それにしても、ビットを細かく使う圧縮はこういう風に書くのか。勉強になります。

n=1481;c=64;i;k;main(w){for(;++i%480;n=i-478?"GANBATTEASSHUKUSHITAYO."[i]-43&255?:457:1499,c^=113)for(k=n;k--;w++%246||puts(""))putchar(c);}

QUEEN

  • 整数Nが与えられると、自分自身のソースコードをN回出力するプログラムを書いてね。

よくあるQuineの変形ですが、「ソースコードの最後に改行が必要」というトラップが仕掛けられていました（問題文にはこのことに対する言及はありません）。とはいえ、この手のトラップには2年前のTLEで慣れているのでエスパーして解決。
あとはprintfを使った普通のQuineをN回出力するコードを書いて……と思いきや、この問題ではopen()が使えるため自分自身を読み込んでN回書き出すというちょっとつまらないコードとなりました。

a;main(n){for(scanf("%d",&n);a=n--;write(1))read(open(__FILE__,0),&a,75);}

REGEX

  • 与えられた'a','b'からなる文字列が ( (ab)* (aab*|aabbaabb) )* にマッチするかどうか調べるプログラムを書いてね。ただし、できるだけソースコード内のアルファベット・数字(alnum)の数を少なくしてね。

アンダースコアを用いれば、変数・関数に使用するalnumの数はゼロにできます。forは再帰に置き換えることで、charはintで無理矢理処理するコードを書くことで消去できます。最終的にはmain, gets, putsの12文字のみになりました。
開発するにつれアンダースコアが多くなりすぎてわけがわからなくなるため、普通のソースコードの変数および関数名をアンダースコアに置換する補助コードを書くと便利です。
ちなみにアルゴリズムは特に工夫なく、前から貪欲に取って行くだけでOKです。

_['~~'];*__,___['~~'];____;_____;______;_______;________;_________;__________;___________;____________;_____________;______________;_______________(________________,_________________){___[_________________]=___[_________________+____]=____-____;___[_________________++]=_[________________]%_____________;___[_________________++]=_[________________]/_____________%_____________;___[_________________++]=_[________________]/_____________/_____________%_____________;___[_________________++]=_[________________]/_____________/_____________/_____________;_[________________]&&_______________(________________+____,_________________);}__________________(){______________=gets(_);_______________(____-____,____-____);__=___;}___________________(){*__==_______&&(__++,___________________());}____________________(){(*__==______&&__[____]==_______)&&(__++,__++,____________________());}_____________________(){(_________&&*__)?(____________________(),(*__==______&&__[____]==______&&__[____+____]==_______&&__[____+____+____]==_______&&__[____+____+____+____]==______&&__[____+____+____+____+____]==______&&__[____+____+____+____+____+____]==_______&&__[____+____+____+____+____+____+____]==_______)?__+=________:(_________=(*__!=______||__[____]!=______)?____-____:(__++,__++,___________________(),____)),_____________________()):____;}______________________(){(__________________(),______________)&&(_________=____,_____________________(),puts(*__?&__________:&___________),______________________());}main(_______________________){____=_______________________;_____=____+____;______=_____+_____;________=______+______;_______=______;_______++;_______++;______=______*______*_______;______++;_______=______;_______++;____________=_____+_____;_____________=________*________*____________;__________=________*________+________+________-____-____;___________=__________+________+____+____+____;__________________();______________________();}

以降の問題では私のコードは省略します。

COINS

  • 数字Nがいくつか与えられるので、それぞれに対してN*(N+1)/2の値を出力してね。ただし、できるだけソースコード内のカッコ (){}[]<> とセミコロン ; の数を少なくしてね。

問題文はすぐには答えがわからないように書かれていますが、小さい数字に対して試してみると上記の式がすぐにわかります。なので解くのは簡単です。問題はカッコとセミコロンの数を最小化するという制限です。

セミコロンはif(){}の中に式を書くことで書かずに済みますし、と<>については使わなくても済むので(){}の四種を使えば自由にプログラムを書くことができます。あとは、それぞれを#defineで適当な文字列に置換すればスコア4の解は作れます。

スコア3以下は人間の領域ではありません。まず[http://shinh.skr.jp/t/tle_coins.c:title=shinhさん(スコア3)]。アセンブリを用いて書くことで{}を2種を省略しています。頭がおかしい（褒め言葉）。その代わりセミコロンが増えてスコアは3です。
アセンブリってこういう風に書くんですね。一応自分も、const char main="\x31\xc0\xc3";がWrong Answerになる！　きた！！　とか思ったりもしましたが、あいにくアセンブリにそこまで造詣が深くないのでここまで到達することができませんでした。文字列定数で書くと__asm__で書くより大変ですしね。これは大変勉強になりました。

さて、もっと頭がおかしいのがkikさん(スコア1; 実質スコア0)。インクルードファイル内の構造体をマクロで書き換えて関数にしています。やばい（困惑）
こういう方法もあるんですね。大変勉強に…………ならねえ……（将来TLEみたいな大会で使う機会があるかもですが）。しかし、大層感銘いたしました。

TRIPLETS

  • 数列Aが与えられると、数列中でi<j<kかつA[i]<A[j]<A[k]となるような(i,j,k)の組の数を出力するプログラムを作ってね。数列の長さと数字の大きさはどちらも1以上10万以下だよ。得点Sは、ソースコードの文字列Bでi<j<kかつB[i]<B[j]<B[k]となるような(i,j,k)の組の数をKとしたときに、S=K/(ソースコードの長さ)だよ。

ナイーブに書くとO(N3)で、N<=10万なのでさすがに間に合いません。なので普通に解くのが結構難しいです。真ん中の数字に注目すると、位置jを固定した時に、可能な(i,j,k)の組み合わせの数は【imax)時間で求めることができます。【j<kかつA[j]<A[k]となるようなkの個数】は、あらかじめ数列全体の頻度表を作っておき、数字が出現する毎に逆にt[A]の値を1減らしていけばOKです。この方法で時間内に答えを求めることができます。

で、問題になるのがScoringです。ソースコードの長さをNとすると、上記のKはO(N3)なので、SはO(N2)です。つまり、ソースコードが長ければ長いほど得点が高くなるというわけのわからないことになります。ショートコーディングとはなんだったのか。なお、ソースコードには50kB以下のサイズ制限があるため、際限なく得点を高くすることはできません。

実際は、問題を解くコードの後にコメントで適当な文字列をくっつけて50kB近くにしました。不等式に等号がついていないため、できるだけ同じ文字を使うのは避けたほうがいいのですが、ASCII文字の種類には制限があるためそうもいきません。本来なら最適なものを探したほうがいいのでしょうが、時間も気力もあまり残っていなかったため適当なものをくっつけてSubmitしました。

PRIME

  • 1015以下の回文素数（回文数であるような素数）を、時間内（10秒以内？）にできるだけ沢山出力してね。(正解の数)-(不正解の数)が得点になるよ。

普通の素数判定（順番に割るとか）ではあまりに遅すぎて、大した得点を得られません。不正解を出力することは認められているので、今回は確率的素数判定、特にその中でも処理が高速なフェルマーテストを採用しました。（巨大数の素数判定法をフェルマーテストぐらいしか知らなかったというのもある）
問題は、Nの最大値が1015と大きすぎるため、累乗計算途中でlong longでもオーバーフローしてしまうことです。実はGCCには__uint128_tという128ビット整数型があるのですが、私は寡聞にしてこれを知らなかったためオーバーフローの対処に大層苦労しました。

最初は多倍長でええやん、とか思って多倍長クラスをガリガリ書いていたのですが、いざ走らせてみると信じられないほど遅く（特に割り算）、使いものになりませんでした。挙句の果ては詳細に書きすぎたためクラス定義が肥大化していき、コード長が10kBを超えSource Limit Exceededを喰らってしまうという散々な目に遭いました。

なので多倍長クラスは捨て必要最小限のコードを書く方針に切り替え。自前の割り算も使わず、long doubleの乗除算で概算値を求め実際の値との差の余りを求めるという掛け算と引き算のみで可能な方法を採用しました。この時点で約7点。そこからはチューニングに次ぐチューニングです。vectorを普通の配列に変えて+5点、巨大数の配列表現に用いる基数を2のべき乗にすることで+3点など地道な改良を重ね、最終的には28点になりました。まだまだ少ないですが、最初に比べればだいぶマシです。

とは言え、そんな努力よりもまず__uint128_tを使え、という話ですよね……。この問題のソースコードを書く時間でざっと見積もって3時間はかかったので、その時間を使ってTLEの環境で使える128ビット整数の型を探す努力をすべきでした。1,2位のkikさん・kinabaさんはどちらも__uint128_tを使っています。それで約70点なので、2.5倍も得点差が出てしまいました。

感想

2年前のTLEも全力ぶっぱしましたが、今回も同様に全力ぶっぱしました。疲れました。コンテスト期間中、メシ・フロ・睡眠以外の時間はだいたい問題を解いていたと思います。それで3位かよとは言わないで。（1位と2位の人がやばすぎるだけです……多分）

感想としては、やはり2年前よりも簡単というか、取り組みやすい問題が多かったように思います。とりあえずAcceptされるコードを書くだけならどの問題もそこまで難しくはないように思いますし。ただ、やはりそこはTLE、点数を伸ばすのはどの問題も大変です。そういう意味では特に2年前より楽とかいったことは感じませんでした。

一つ残念だったのはQUEENのエスパーですね。二年前のBSTのtrailing spaceもそうでしたが、エスパーできない＝WAは悲しい。実際エスパーできなかったために通せなかったという方もいらっしゃいましたし。私はtrailing spaceに懲り懲りして、この問題でWAったときも真っ先に改行を試したため事なきを得ましたが。
あと、このQUEENの一件で私のジャッジに対するリスペクトが完全になくなり、他の問題でWrong Answerが出ても「本当にWrong Answerか？ ジャッジデータがおかしいんじゃないか？」とかいちいち考えてしまいました。まあこれは私の責任ですが。

来年以降も参加したいですが、今回や前回のように全力で行けるかはわかりません。来年は頑張ればできそうですが、再来年以降はどうかなあ。まあ、全力で参加できなくても一部で参加できればしたいと思います。

皆さんお疲れ様でした。