TLE 2015
http://felicity.iiit.ac.in/contest/tle/
成果物: https://gist.github.com/shinh/64fbd3d43147f6a7bbb4
毎年思ってることだけど、ここ数年は特に脳死しているなーという時に行なわれてる…ので腑甲斐ないのはしょうがないんだよ。
今回は結構神回だったんじゃないかなー実は。たぶん処理速度の問題で SNUSP 問題が消え失せたんじゃないかと思うんだけど、あれ別に面白くなかった気がするから消えて良かったんでないかと思うます。あとたぶんだけどあのへんの問題が決定的な要因になったんでないかな、残っていれば。偶然から生まれた神回感が強い。
あとちなみに初回の延期時から問題は変わってない…気がするので、やろうと思えば2週間以上使えたんじゃないかな実は…僕は延期した日にやったことは SNUSP の仕様読んでたくらいで、他の問題はだいたい忘れて脳死してたので、当日まで準備とかしてないよ…ホントだよ
Distinct Substrings
ゴミみたいな答えができたらゴミを後ろにつけると高得点というすごい問題。主催者が深く考えてない問題が出るのは毎度恒例ではある。トップを取るとかはどうでもいいスコアシステムだったので瞬時に捨てた。
Find the GCD
GCD(P,Q) を求めよただし P,Q には n,m,R を使って色んなことをして作られる。みたいな問題。 P,Q は巨大でかつ問題の制限として四則演算オペレータ使っちゃいけないということなんで、賢いやりかたがあるんだろうなーと思いつつ、はて…としばらく死んでいた。
まさに脳死という感じで。脳死しててもしゃーないんで、とりあえず正の点数取るか、そのうちなんか降ってくるだろ、となるのが私の唯一偉いところだと思ってるので、とりあえず解いた。つまり多倍長整数で mod が計算できる程度のコードを +-*/% 無しで書きました。感想はしんどかった。
手元で通るぽいコードを投げてみると Runtime Error 。これは TLE だろうかなあ…と思いつつデカいケースを喰わせてみると 0.15 秒くらいかかる。 1 秒が TLE の問題でこれだけ時間かかってると、まあだめだろうな…と思いつつ、 gprof とかで最適化するのにムダな時間を使う。本当にムダだ。
本当にムダなので賢いやり方を探そう、まー R てのが与えられてるからこれとなんかすればいいんでしょ？てことで適当に色んなことをやってると、 GCD(P,Q) が GCD(P,2^R) と一致するじゃありませんか…てことで解いた。
翌日 kinaba さんにアレでなんでいいのって聞いたらそんなの当たり前じゃないですか的なこと言われて、いや実際当たり前だった。はい。
Life, the Universe and Everything
数字がいくつか与えられるので、 echo しなさい、で、 42 で出力を止めなさい。ただし -nostdlib ついてるよ、とのこと。
えっとそれは得意分野やんけ…と瞬殺してほったらかしてたけど、普通にゴルフ足りてなかった。
ASCII Weaving
もうこの手の飽き飽きなんだよ…というような、画像圧縮問題。いつも通りとりあえず RLE してそれぽい解ができる。
いつも通りだとこれに huffman かけるんだけど、なんか huffman てやる前からどのくらいのサイズになるか見積れるわけで、はてこれはそういう感じでは mame さんに絶対追いつけないぞ、なんかすごいことが行なわれてる…
ということでやる気が失せて放置。
Halting
C プログラムの停止性を判断せよとの問題。
全部停止するって言えば 4 点入るので、あとは固定解答与えりゃいいやろ…とやってみるとうまくいかないので眺めてみると。出てくる順番が変わってるぽい。
出てくる順番変わってるだけな気がしたけど、まあ限定された C インタプリタとか割とすぐ書けるよね…と思って書きはじめたら全然間に合わなかった。いやまあインタプリタ書けても停止性は判定できないわけだけど、ある程度できたらヒューリスティクス適当に入れりゃ適当に得点高いだろ、って思ってたんだけど…
Reverse Quine
いつも通りの Quine 。 g++ の時は #include のかわりに #import 使うてのは基本中の基本だったはずなのに、脳死しててできなかった。ひどい。
工夫したところは ext/rope を #include すれば stdio.h と string が自動的に手に入る、てことくらいでしょうかね…
まとめ
問題はすごく良かったと思います。が、全体的に脳死してた。そもそも開始時間から大幅に遅れて起きてる時点でアレですね…なんか年々体力とやる気が失われている気がする。それくらいしか取り柄がないというのに…
あとまあ最終版にスコアボード全く見ずに Halting やってたのもひどいなあと思う。自分が1位から落ちてることにすら気付いてたんだっけ…という感じ。もうちょい戦略的にやるべき
