Hatena::ブログ(Diary)

菊やんの雑記帳

2015-03-02 TLE 2015

[] 01:40 TLE 2015 - 菊やんの雑記帳 を含むブックマーク

TLE 2015 だった。

最初は 2/7 にやるよ!って書いてあったような気がするんだけど、いつのまにか 2/11 → 2/12 → 2/27 → 2/28 にどんどん延期されていってやばかった。そのせいか参加者少なすぎ。

問題一覧はここを見るとよい

http://d.hatena.ne.jp/ku-ma-me/20150302

提出したコードはここ

https://gist.github.com/kik/ba7f3ba6699932539913

Distinct Substrings

やるだけ。どうやったら点数が変わるのか分からなかったので通しただけだったけど、98点あったので放置。どうやったら点数が減るのかが逆にわからない。たぶん、点数を最大化する方法をkinabaさんが解説してくれるんじゃないかな。

Find the GCD

5人しか通せてない。見たところみんなやり方が違って面白い。

  • 多倍長を使う派
    • 互除法使う派
    • x & -x派
    • 1bitずつシフトする派
  • 多倍長しなくていいじゃんに気づいた派

最初は多倍長+互除法で実装して通した。最初のはldiv()で割り算してた。一度通ってしまうと改造するのも楽ちん。

ldiv()で互除法はめんどくさいし、足し算を書いてたので x & -x のほうがいいかなと思って通らない。

gcd(x, 1<<R)

x = x & -x
min(x, 1<<R)

って同じに見えるじゃないですか!でもサブミットしたら通らないし、実行に差がでる場合を全探索した結果、x = 0 のときだけ結果が違いました!なので、

x = x & -x
x ? min(x, 1 << R) : 1<<R

みたいなくそコードになったんですが、よく考えたら

x |= 1 << R
x & -x

でできました。orとってビット演算する方式は__builtin_ctzするチノちゃんのコードと同じですね。ffsじゃだめだったのかよく知りませんが。

Life, the Universe and Everything

これはさらに通してる人が少ないわけですが、みんなだいたい同じです。みんな当然のように'\n42\n'と比較してたんです。これだと、最初に"42\n"が来たときに困るなあと思って、わざわざバッファの先頭に'\n'を置いたり、終端を検査したり、まじめコードを作ってたんです。サブミットしたらそんな真面目に書かなくても通ることが分かったので、これは答も定数になってるんじゃねと思ってやってみたら、やっぱりマジックナンバー917を当てる問題でした。

なので、stdinから917バイト読んでstdoutに917バイト書いてexit(0)

ASCII Weaving

去年のしょぼい圧縮コードを持ってきて、そのままコピペしました。shinhさんと同じくらいの点数になったしそれでいいや。

Halting

最初は適当に全部yesにして4点。

先頭だけnoにするところころ点数が変わる。あと、問題は30問あるっぽい。

ってのがわかったので、yesを17個、noを13個をランダムにシャッフルしてみたんだけど全然点数にならない。

ということで、問題がシャッフルされてるぽいってことはわかった。というわけで、問題をテキスト順でソートして、その順番にyesとnoを固定で割り当てて、元の順に戻して出力するってのを書いたつもりだったんだけど、どっかバグってたのかうまくいかなかった。チノちゃんはこれで満点だったっぽいので、何かをどっかで間違えたっぽい。

しかたないので、諦めてテキストの適当な性質で分岐していくことにした。whileの数とかifの数とかで分岐して、各分岐を何回通ったかを数えて、1回しか実行されないコードにがんがん分割していって、yesとnoを割り当てていく作戦にした。これをやっていっても最終的には満点になるはずだったんだけど時間が足りない。

Reverse Quine

まず、コードが通らない。通らないのはなぜかというと、問題文にとちゅうにある改行は消すよって書いてあったから。よくみたら最後の改行しか消してない。なので、本当に基本的な、printf(p, 34, p, 34) 型でなんとか通す。本当は一昨年からずっと使われてるマクロを使うべきだったのに時間が足りない。

まぼろしの残り3問

SNUSP http://esolangs.org/wiki/SNUSP というesolangで書けというのが3問あった。起きたら無くなってた。

2009-02-13 TLE

[] 23:14 TLE - 菊やんの雑記帳 を含むブックマーク

適当に参加した

KEY: 154点。点数の集計の問題で、同点になるSの値がたくさんあってしょぼんぬ。154点の中では一番なのに……

SHORTREN: なんか途中でやる気がなくなった。

INPOUT: 採点の変更は空白を使ったコードを排除するためだったのね。なんか手元の点数の計算がずれてたので、600を超えるには空白をうまく使わないとできないものだと勘違いしてた。

CODEHASH: あとは自動探索を走らせるぐらいしかないなー。でも他にやる気ある参加者いないみたいだし放置でいいや。とか思ってたら抜かれた。普通に探索すればすぐみつかるコードじゃん。

CLASS: typeofとかいらないから。Cのパーザを書きまくってるからこれは自明

PRINT: もうやるきないなーとか思ってたら、nihaさんがPRINTを解き始めたのを見て、せっかくだからやるか→空白カウントしない問題じゃん→SHORTRENでやろうと思ってたコード埋め込みだろこれ。

char*s,*t,p[]="ここにコード";main(n){for(*(&n-1)=s=t=p;*s;s+=1+n)*t++=n=index(s,9)-s;}

きめえ

ARBIT: 解読だけしておなかいっぱい。