Distinct Substrings

ゴミみたいな答えができたらゴミを後ろにつけると高得点というすごい問題。主催者が深く考えてない問題が出るのは毎度恒例ではある。トップを取るとかはどうでもいいスコアシステムだったので瞬時に捨てた。

Find the GCD

GCD(P,Q) を求めよただし P,Q には n,m,R を使って色んなことをして作られる。みたいな問題。 P,Q は巨大でかつ問題の制限として四則演算オペレータ使っちゃいけないということなんで、賢いやりかたがあるんだろうなーと思いつつ、はて…としばらく死んでいた。

まさに脳死という感じで。脳死しててもしゃーないんで、とりあえず正の点数取るか、そのうちなんか降ってくるだろ、となるのが私の唯一偉いところだと思ってるので、とりあえず解いた。つまり多倍長整数で mod が計算できる程度のコードを +-*/% 無しで書きました。感想はしんどかった。

手元で通るぽいコードを投げてみると RuntimeError 。これは 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位から落ちてることにすら気付いてたんだっけ…という感じ。もうちょい戦略的にやるべき