naiの日記

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

875. Kimariji

最近はあまりCode Golfをやっていなかったのですが,ふとanarchy golfを見るとKimarijiをやってました.
これはかるたラーとしては参加せざるを得ないということで,頑張ってCで縮めてトップを取ることができました.とても面白い問題でした.
せっかくなので私のコードについて軽く解説をします.

用いたアルゴリズム

read()で入力を全部読み込み,入力の末尾に答えとなる文字列を付け加えていきます.
全ての行に対し決まり字を求めたら,謎の終了条件で無理矢理ループを抜けてputs()で答えを出力して終了.

なんでわざわざこんなことをするかというと,所謂「決まり字変化」を無視するためです.
単に決まり字を出力していくだけのコードだと,例えば「はるのよの」の決まり字を探す際に,既に"\nharus"は通りすぎているため"\nhar"までで決まってしまいます.出力を末尾に加えてゆくことでこれを回避できるというわけ.

sbrk()

最初は以下のように,intで巨大な配列を確保して用いていました.

s[999];main(b){char*p=s;...}

sの要素数を減らしたり,mainの第二引数を使ったりしましたがうまくいきませんでした.そこで発見したのがsbrk()です.
簡単に言うと,sbrk(n)でnバイトのヒープ領域を確保できるということらしいです.ヒープ領域はおおむねゼロクリアされていますし,嬉しい誤算として毎回値が変わるため,b%65を用いたrandコードが通るようになりました.
なお,終了したい時点での余りが他と被らない中で2番目に小さい割る数として65を採用しました.最小は40ですが,さすがに8の倍数だとまずいみたいです.
ちなみに,randを用いない100Bコードは以下の通り.

s[999];main(b){char*p=s,*t=p+read(0,p+1);for(;b%511;p++)strstr(p,*p<11?b=t:b)-b?*t+++=*p:1;puts(p);}


sbrk()は個人的には大発見だったのですが,ググってみると

sbrk is also useful in code golf because it's 2 characters shorter than malloc.

c - What does the brk() system call do? - Stack Overflow

なんてのも出てきて,やはり先人は凄い……