CODE FESTIVAL 2015 短縮王 感想と解説

,

CODE FESTIVAL 2015のコンテンツとして行われたgolf、ショートコーディングコンテスト「短縮王」に関して。 全言語部門の全問題で1位or1位タイを取って総合1位を取りました。 感想と私の提出コードの解説の記事です。

全体の感想とか

全言語部門で1位を取りました。 賞品はラクリートというロボット掃除機を1つと、ロボット掃除機を模した机の上を落ちないように走り回るおもちゃが3つでした。 golfという正直あまり役に立たない遊びのわりに賞品が豪華で驚きです。中の人的に幾何ゲーが元の選択なのだろうが、しかし掃除という選択はなにかの皮肉にしか見えない。普段のコードは綺麗ですよ。

c言語部門に関してはさっぱり。c言語のgolfに関するがあって、皆これを読んでいたらしい。私は同じ土俵に上がることすらできていなかったようです。 上手くeaxを0にする技や、領域の確保を嫌がって入力をstack上にぶち込む技が必要な争いだったらしい。

一方、全言語部門に関しては、perlとrubyを両方ある程度使えてgolfをやる気がある人が私だけ、という状況。例えばD問題をperlで出しているのは私だけ。 優勝争いには実質ひとりしか参加してなかったように感じました。 c言語部門は白熱してたように見えて羨しかったです。 でも唯一C問題は、あるrubyistと抜いたり抜かれたりを楽しみました。

そういう私も、perl/rubyによるgolfをまともにやったのは今回が初めてです。 perl golf tipsとかでぐぐった結果を見ながらgolfしていました。 なのでshinhさんの解説でも、知らない知識がかなりたくさん出てきていました。 「golfの入門に良いサイトや本はありますか?」とshinhさんに質問したところ、anarchy golfの過去問の解答を読むこと、c言語に関してはがあるということ、を教えていただきました。 とりあえず今は今回の問題のanarchy golf上での出題が期限切れして解答が公開されるのを楽しみにしています。

とにかくgolfはとても楽しかったです。 そして後から自分のtwitterを見かえしたら、ほとんどgolfの話題しか呟いてなくてちょっと気持ち悪かったです。 参加者少ないのでgolfが初めての人間でも優勝が狙えます。 楽しい上に優勝が狙えるなら参加するしかないですよね。 なので皆さん来年は是非とも全言語部門にも参加してほしいと思います。

ルール

  • atcoder上で実行される
    • return codeが非零ならruntime errorに
    • 改行は2byte
    • 使える言語は実用言語ばかり
  • 全言語部門と、c/c++部門のふたつが存在
    • clangは禁止
  • 嘘解法も許される (通るなら)
  • 問題は事前公開されている
    • ただし入力形式の大幅な変更がある。当日の調整は必須
  • 順位表

A - もし解けなかったら木の下に埋めて貰っても構わないよ (anarchy golf: Code Festival A If you cannot solve this)

50byte perl

$a=(2*<>-1)*<>;$a-=$_ for<>;print$a>0?Pass:Fail,$/

激戦区。同じ50byteを提出していた人が他に3人いる。提出時間の差で2位。

解説

式変形

  • $s1 \le \frac{\Sigma{i=1}^N s_i}{2N}$
  • $2Ns1 \le \Sigma{i=1}^N s_i$
  • $(2N-1)s1 \le \Sigma{i=2}^N s_i$
  • $(2N-1)s1 - \Sigma{i=2}^N s_i \le 0$
$a=(2*<>-1)*<>;  # a = (2N-1)s_1
$a-=$_ for<>;  # a -= s_i (2 <= i <= N)
print$a>0?Pass:Fail,$/  # 出力
  • <>はつまりgetline
  • perlでは文字列から数値への暗黙変換がある
  • for(<>){...}STDIN.each{...}
    • $_に行の文字列が改行付きで入る
  • 後置forは得
    • for(...){...}...for...;になって4byte前後減る
  • 関数呼び出しの()は基本的に省略可能
  • perlの識別子は適当に文字列として解釈される (bareword)
    • "Pass"Passになって2byte減る
    • use strict; pragmaでこの機能を殺せる
  • $/には改行文字"\n"が入ってるので2byte有利

改善

shinhさんの解説を聞いて

  • join('+', <>)してevalすれば$a = 0; $a += $_ for <>;相当のことができる

とのことなので縮めたのが以下。スライドに載ってたのはもうちょっと短かったような気がする。

46byte

print~-(<>*2)*<>>eval(join'+',<>)?Pass:Fail,$/

golf場では入力が1行に与えられるのでeval s/ /+/gってしてたけど、複数行でもできるのは知らなかった。 ~-xx-1-~xx+1は知ってた。

B - Union Find (anarchy golf: Code Festival B Union Find)

114byte perl

<>;sub r{$j=$t[my$i=pop];$j?$t[$i]=r($j):$i}s/ \d+//,$p=(r$&)-(r$'),$`&&print($p?NO:YES,$/)||$p&&($t[r$&]=$')for<>

golf場と入出力形式が同じ。 shinhさんがの管理者権限を使ってgolf場でのやばいperlのコードを紹介してた。まったく読めなかった。

解説

# union find treeを表す変数は @t
<>;  # 1行目は読み飛ばし
sub r {
    $j = $t[my $i=pop];  # 引数のひとつめをlocal変数$iに積み、その親も取得しglobal変数$jに格納
    $j ? $t[$i] = r($j)  # 親が居るなら再帰して更新
       : $i  # 居ないなら自身が代表元
}
s/ \d+//,  # 入力 "A B C\n" の "B" にだけmatchさせることで、 $` = A; $& = B; $' = C を実現
    $p = (r$&) - (r$'),  # BとCの親が異なるかどうか
    $` && print($p ? NO : YES, $/)  # Aが1なら出力
       || $p && ($t[r$&] = $')  # Aが0なら更新 ただし同じ集合に属するなら無視
    for<>

C - 割り算と足し算 (anarchy golf: Code Festival C Div and Add)

79byte ruby

def f(i)i-i/10*9+(i>99?9:(1..i-1).map{|j|i%j<1?f(j):0}.max||0)end;p f gets.to_i

(a..b), .upto, .times, .stepの辺りでずっと試行錯誤していた。(...)は知らなかった。

解説

$$ f(i) = ({\rm sum~of~digits~of~i}) + \max { f(j) \mid 1 \le j \lt i, j \shortmid i } $$ という再帰関数。dpしてもよいが、再帰の方が短くなった。

def f(i)
    i-i/10*9  # i/10+i%10 に等しい 2桁目以上と1桁目の和
        + ( i>99
                 ? 9  # 100の場合は別処理 差分を足す
                 : (1..i-1).map{ |j|
                       i%j < 1
                               ? f(j)
                               : 0
                   }.max || 0  # maxを取る 空列のときnilになるので対処
          )
end;
p f gets.to_i

改善

shinhさんの解説で、覚えている範囲で改善

75byte ruby

f=->i{i-i/10*9+(i>99?9:(1..i-1).map{|j|i%j<1?f[j]:0}.max||0)};p f[eval *$<]

shinhさん曰く、

  • rubyにはarrow記法による$\lambda$式も存在する
    • 昔はなかった気がする
    • -> (args) { body }
    • .call[]で呼びだす
  • gets.to_iよりeval *$<の方が1byte短い
irb(main):001:0> ->x{x*x}[3]
=> 9

教えてもらいました。1.9ということは?dで整数100を表現して1byte得するテクと共存できない。

指摘

74byte ruby

f=->i{i-i/10*9+(i>99?9:(1...i).map{|j|i%j<1?f[j]:0}.max||0)};p f[eval *$<]

こういう指摘はとてもありがたいです。

(...)はまったく知りませんでした。自明どころか驚きの事実です。精進します。

71byte ruby

D - 数列圧縮 (anarchy golf: Code Festival D Compress numbers)

78byte perl

$a=<>;@b=split//,<>;[email protected];$a=~s/./($b[0]-=$&)%10||[email protected]/eg;[email protected]?NO:YES,$/

perlでの提出者が私だけなので当然1位。なんだか悲しい。

解説

Aの数字を先頭から貪欲に足し合わせていって、Bの数字の文字と一致すればふたつを除去する。これを繰り返して、Bが空になり、かつその時Aの数字の総和が0になればよい。

$a = <>;  # 1行目は文字列
@b = split//,<>;  # 2行目は文字の配列
pop @b;  # 改行文字をpop
$a =~ s/./
        ($b[0] -= $&) % 10 || shift @b  # $a内の各文字を$&に入れて、$bの先頭から引く。 それが零なら$bの先頭を削除
    /eg;
[email protected]?NO:YES,$/
  • 正規表現のemodifierは右辺を式としてevalする。
    • 二重にやるeemodifierもある。いくらでもnestさせられるぽい。

shinhさんの解説では$aの側でもs///egを使っていたはず。そう長くは映されていなかったので読めず。

指摘

74byte perl

$_=<>;@b=split//,<>;[email protected];s/./($b[0]-=$&)%10||[email protected]/eg;[email protected]?NO:YES,$/

これは気付くべきだった。


  • Tue Nov 17 20:18:29 JST 2015
    • rubyのarrow記法に関して教えてもらったので追記
    • Dの最後で引用してるコードが間違ってたので修正