yukicoder No.81 すべて足すだけの簡単なお仕事です。
この記事は、yukicoder No.81 すべて足すだけの簡単なお仕事です。 の解説かもしれない(し、解説でないかもしれない)。この問題のコードゴルフがとても楽しかったので、何があったのかを時系列順に書いてみた次第。
2016-05-25 14:59:37 84B
#93995 Matchald さんによる Python3 のコード
from decimal import *
i=input
print(round(sum(Decimal(i())for _ in[0]*int(i())),10))
元々はこれが最短コードだった。
2016-12-26 05:17:44 53B(-31)
sed '1d;y/-/_/;s/$/+/'|tr -d \\n|dc -e?1.0000000000*p
とりあえず解いてみた。当初、Perl で解こうとしたが、単に bignum を使うだけでは充分な精度で計算できなかったので、dc に丸投げした。
- いきなり dc を使うことはできないのでまずは sed で入力を加工
- 1行目の入力が邪魔なので
1d
- dc では単項のマイナスは
-
ではなく_
なのでy/-/_/
- 各行末に
+
を付けるためにs/$/+/
- 上記までで加工された入力の改行が邪魔なので
tr -d \\n
dc -e
でそれ以降を dc のコードとして実行?
で加工された入力を1行読み込むと同時に dc のコードとして実行1.0000000000*
で小数点以下10桁の精度を持たせてp
で表示して終わり
dc は逆ポーランド記法で任意精度の計算ができる。1+2+
というコードがあったとすると、まず 1
がスタックに積まれ、+
で足し算をしたいけどスタックの要素数が2未満だから何もしない、次に 2
が積まれ、今度は足し算ができるから足して 3
、という具合に計算されるので、 +
が1個余計にあっても計算結果は正しくなる。今回の問題ではこの +
が1個余計にあっても良いことを利用している。
2016-12-26 05:22:03 36B(-17)
read;tr \\n- +_|dc -e?1.0000000000*p
いかにも無駄がありそうだったので dc を呼ぶより前の部分をいじった。書き方が変わっただけで、やっていることは全く同じである。
2016-12-26 05:25:45 35B(-1)
read;tr \\n- +_|dc -e?.0000000000+p
1を掛けるのと0を足すのは同じことで、0.0000000000
は先頭の 0
を省略できるということを思い出してこうなった。
2016-12-26 11:07:10 27B(-8)
read;tr \\n- +_|dc -e?Ak1/p
A
は 10
の短い書き方。k
は精度(小数点以下何桁まで精度を持たせるか)を設定する。1/
によって設定した精度が有効になる。k
を利用しようとは思っていたのだが、1で割れば良いということを忘れていて、tails さんに先に提出されてしまって最短を取り逃してしまった。
とまぁ、ここまではよくある話である。
yukicoder の最短コード、今日だけで9問とって、そのうちの6問を tails さんにとられてる。
— %20(締切を甘く見すぎ) (@henkoudekimasu) 2016年12月26日
この6問のうちの1問がこれ。
2016-12-26 19:30 ~ 21:00 頃
- dc では、小数点以下10桁までを表示するつもりでコードを書いても、
0
は0
と表示される - dc では、
0.なんたら
は.なんたら
と表示される
という、dc に特有の変な性質のせいで、出力すべき答えが 0.0000000000
や 0.1000000000
になるような入力が与えられた場合、dc を使った解答では想定される出力が得られない、ということが分かった。というわけでチャレンジ。
yukicoder の嘘解法を落とすためのテストケース追加ってどういう手順でやるん?
— %20(締切を甘く見すぎ) (@henkoudekimasu) 2016年12月26日
@yukicoder ありがとうございます。「No.81 すべて足すだけの簡単なお仕事です。」に以下のテストケースの追加をお願いします。
— %20(締切を甘く見すぎ) (@henkoudekimasu) 2016年12月26日
入力1
1
0
出力1
0.0000000000
入力2
1
0.1
出力2
0.1000000000
影響範囲は dc を使った解答をしている %20 と tails さんの2人だけだろうと思っていたのだが、
テストケース追加したら予想外に多くの人に影響があってびっくり。
— %20(締切を甘く見すぎ) (@henkoudekimasu) 2016年12月26日
@henkoudekimasu どんな自爆テロですかw
— 齊藤 (tails) (@saito_ta) 2016年12月26日
2016-05-25 14:50:56 96B(+69)
#93983 Matchald さんによる Python3 のコード
import decimal as d
j=input
print("{:.10f}".format(sum(d.Decimal(j())for i in range(int(j())))))
リジャッジの結果、最短コードになったのはこのコードだった。
2016-12-26 21:51:34 73B(-23)
<>;print`tr \\\\n- +_|dc -e?Ak1/p`=~s/^0/'.'.0 x10/er=~s/^(-?)\./${1}0./r
実は、もう1つコーナーケースがあることに気づき、場当たり的に提出したコード。
2016-12-26 21:56:43 51B(-22)
read;tr \\n- +_|dc -e?d1~rn46P[A*1~rd*vndzC\>f]dsfx
これは、もう1つのコーナーに対応していない。
@yukicoder No.81 に、もう1ケース追加をお願いします。
— %20(締切を甘く見すぎ) (@henkoudekimasu) 2016年12月26日
入力3
1
-0.1
出力3
-0.1000000000
答えが -0.9999999999
以上 -0.0000000001
以下の場合、「符号つきで整数部を表示、.
を表示、小数部の絶対値を表示」というようなコードは落ちる。
2016-12-26 22:04:55 49B(-2)
read;tr \\n- +_|dc -e?d1~rn46P -eA*1~rd*vn{0..9}r
これも、もう1つのコーナーに対応していない。2度目のリジャッジの直前に提出された。
2度目のリジャッジの結果、さらに多くの嘘解法が落ちた。
作問者による想定解さえも落としたぞい。
— %20(締切を甘く見すぎ) (@henkoudekimasu) 2016年12月26日
#1833 No.81 すべて足すだけの簡単なお仕事です。 - yukicoder https://t.co/60DBWNgOP5 @yukicoderさんから
2016-12-26 23:16:48 57B(-16)
use bignum p,-10;$x=0/<>;$x+=$_ for<>;print$x||'0.'.0 x10
use bignum
にオプションをつけることで、充分な精度で計算できるようである。ただし、0
の場合は 0.0000000000
を表示させるために埋め込んでいる。
2016-12-26 23:55:50 55B(-2)
use bignum p,-10;$x=0/<>;$x+=$_ for<>;printf$x||'%.10f'
print
の代わりに printf
を使って 0.0000000000
を表示するための部分を短くしている。
これにはもう隙が見当たらなさすぎる。これ以上縮むことはないね。終わり。
2016-12-28 04:19:56 52B(-3)
#141845 hogeover30 さんによる Ruby のコード
gets;puts"%.10f"%$<.map(&:to_r).inject(:+).round(11)
まだ終わってなかった。Ruby には「有理数型」があるので入力の文字列を to_r
で有理数型に変換すれば簡単に計算できる。なるほど。
— hogeover30 (@hogeover30) 2016年12月27日
2016-12-28 04:34:42
puts"%.10f"%eval((`read;dd`.tr$/,?+)+?0).round(11)
何とか縮める方法はないかと探って、こんなコードを書いてみたが WA。重要なのは to_r
によって有理数型に変換することなのでそれをしなければ WA になるのは当然。
2016-12-28 05:13:22 50B(-2)
#141854 hogeover30 さんによる Ruby のコード
puts"%.10f"%(eval"+gets.to_r"*gets.to_i).round(11)
%20さんがevalを使ってたのがヒントになった
— hogeover30 (@hogeover30) 2016年12月27日
WA も無駄ではなかった。eval
によって(2行目以降の)行数分の繰り返しをしている。
2016-12-28 05:21:54 49B(-1)
#141856 hogeover30 さんによる Ruby のコード
gets;puts"%.10f"%(eval"+gets.to_r"*100).round(11)
実は、繰り返し回数は行数分以上であれば良いらしい。この問題の制約から、1行目は無視して、100回の繰り返しをすれば良いということになる。
2016-12-28 05:45:32 39B(-10)
gets;puts"%.10f"%(eval"+gets.to_r"*100)
ところでその .round(11)
とやらは要るの? という感じで削ってみた。
2016-12-28 05:48:11 38B(-1)
gets;puts"%.10f".%eval"+gets.to_r"*100
そういえば、Ruby では演算子はメソッドのシンタックスシュガーだから括弧外せるなぁ。
100
は100以上の整数であれば何でも構わないので、$$
(PID を表す特殊変数)が使えるかと思ったら yukicoder では $$
は小さいらしく WA。1行目の入力が邪魔なのも何とかならないかなぁと思考錯誤しても何ともならない。
2016-12-28 13:58:20 37B(-1)
puts'%.10f'.%eval`sed '1!s/$/r+/'`+?0
なるほど、sed を使えば色々同時に解決できる。1!s/$/r+/
というのは1行目以外の行の末尾に r+
をつけるということ。1.5r
のように書くと有理数型にできるらしい。
2016-12-28 14:14:54 36B(-1)
puts'%.10f'.%eval`sed 1\!s/$/r+/`+?0
sed は ''
を省略できる場合がある。ただし、エスケープが必要になる文字がある。
2016-12-28 14:25:23 35B(-1)
puts'%.10f'.%eval`sed 1!s/$/r+/`+?0
エスケープ要らなかったらしい。
終わり。