短縮王 in CODE FESTIVAL 2015 A - もし解けなかったら木の下に埋めて貰っても構わないよ

問題

問題文

提出したコード

Submission Ruby (2.1.5p273) 58 Byte

s=0;n,a=$<.map{|i|s+=i.to_i};puts s/n>a-n<<1 ?:Fail: :Pass

本番中出したコードはこれよりも 3 バイト長いものです．あとで幾分 ciel さんのも参考にして縮めました．

方針

ショートコーディングはほぼ初めてだったので嘘があったら教えてください．

1, 2 番めの文

文はセミコロンで区切られます．1,2 番めの文を引き伸ばすと以下のようになります．

s = 0
n, a = $stdin.map { |i|
    s += i.to_i
}

$< は $stdin ARGF のことです．標準入力が ARGF から取り出せ，それに対して map を呼び出すと，各行に対してブロックで渡した処理を実行し， Array に入れて返します． ブロックは明示的に値を返さない場合，最後に評価された値を返します． to_i で文字列の整数への変換を行い s への加算し，累積した結果を返すということをしています． さらに配列を s, a に代入すると，配列の前から 2 つの値を s と a に書き込めます．

3 番めの文

3 番めの文を引き伸ばすと以下のようになります．

puts (s/n > (a-n) << 1) ? :Fail : :Pass

(s/n > (a-n) << 1) は下で説明する条件式で bool 値です． :Fail のように : で始まる ものは Symbol というオブジェクトで，それを文字列に変換することでダブルクオーテーションを省略できます． ?, : は 3 項演算子で puts は文字列に変換して改行と共に出力するメソッドです．

アルゴリズム

問題で与えられる変数の名前と混乱しやすいですが，コード中の s は入力を全て足した数です．なので s は 点数の総和 + n となっています． また a には (問題文での n + 問題文での s[1]) が入っています。

判定すべき不等式は s[0] <= (sの合計) / (2*n) です．上でおいた s, a を使って素直に書くと a-n <= (s-n)/(2*n) となります．両辺に 2 をかけると， 2(a-n) <= (s-n)/n となります． (よく考えたらここ怪しい(s-nが2nで割り切れないとき)) 左辺は整数で，右辺について s-n と s は n で割ったあまりが等しいので，(s-n)/n = s/n-1 と書き直せます． -1 を移項すると 2(a-n)-1 <= s/n となり，両辺とも整数なので 2(a-n) < s/n と書き直せます．さらに右辺をシフト演算で書き直して左右入れ替えると s/n>a-n<<1 となります．