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
エスケープ要らなかったらしい。
終わり。
コードゴルフをする場について
誰向けの記事なのかよくわからない。
- ゴルフ場
- 111言語
- esolang 多め
- テストケースは最大3件で全て可視
- 出題期間は2週間が基本だが、1時間から4週間、無期限もある
- 出題頻度は時によりばらばら
- 誰でも作問・出題できる
- 単に解くだけなら簡単な問題が多い
- 競プロ場
- 22~52言語
- 古い問題は使用可能言語が少ない
- 一部の esolang も使える
- テストケースは可視と、不可視(コンテスト終了後に可視になるものもある)が両方ある
- 出題期間は競プロのコンテストとしては約2時間
- 基本的に、毎週土曜(か日曜)にコンテストとして6問出題される
- レート2400以上の人を対象に作問者を募集している
- ゆるふわ競プロ場
- 34言語
- 一部の esolang も使える
- テストケースは可視と、不可視(コンテスト終了またはACで可視になる)が両方ある
- 嘘解法を落とすためにテストケースが追加されることがある
- 出題期間は競プロのコンテストとしては約2時間
- 基本的に、毎週金曜にコンテストとして4問出題される
- 誰でも作問できるが出題には審査がある
- ゴルフ場でもある
- 17言語
- コード全体ではなく関数だけを書く
- 空白文字はコード長にカウントされない
- テストケースは可視と不可視が両方ある
- 出題期間は1日か2日が多いが、1週間や100年もある
- 出題頻度は1日1問ぐらい
- 誰でも作問できるが出題には審査がある
1種類の括弧対で非負整数を表現する記法を思いついた
1種類の括弧の対だけで非負整数を一意に表現するよくわからない記法を思いついた。
この記法で 0 から 32 までを列挙すると以下の通り。
0 ()
1 (())
2 ((()))
3 ((())())
4 (((())))
5 (((()))())
6 (((())()))
7 (((())())())
8 ((((()))))
9 ((((())))())
10 ((((()))()))
11 ((((()))())())
12 ((((())())))
13 ((((())()))())
14 ((((())())()))
15 ((((())())())())
16 (((((())))))
17 (((((()))))())
18 (((((())))()))
19 (((((())))())())
20 (((((()))())))
21 (((((()))()))())
22 (((((()))())()))
23 (((((()))())())())
24 (((((())()))))
25 (((((())())))())
26 (((((())()))()))
27 (((((())()))())())
28 (((((())())())))
29 (((((())())()))())
30 (((((())())())()))
31 (((((())())())())())
32 ((((((()))))))
「0 は()
、1 は(())
、2 以上のとき、偶数ならばその半分の数を()
で囲む、奇数ならばそれより 1 小さい数の最後の)
の直前に()
をつけ足す」という方法で生成できる。
ferNANDo という言語で足し算をした。
ferNANDo という esolang(難解プログラミング言語)で A plus B problem という問題を解いた。
endless 問題のネタバレなので、自力で解きたい人は引き返して下さい(いないと思うけど)。
ferNANDo の命令は「入力を1文字読む」「1文字出力する」「2変数を NAND して変数に代入する」「変数が真のとき戻る」の4種類しかない。変数は0
か1
の値しか持たない。
この問題では、1~4桁の、桁数が固定されていない整数を読み取る必要があるので、スタックのようなものが必要だが、この言語には配列もスタックも無いので、自分でスタックのようなものを作る必要がある。スタックのようなものは、疑似コードで言うと、do{e=!d,d=!c,c=!b,b=!a;}while(a=input());
という具合になる。「ループする毎に『値がどの変数に入っているか』がずれていく構造」と言ったほうが適切か。なお、b=a
ではなくb=!a
となっているのは、その方がコードが簡潔になるからである。
提出したコードでやっていることは、おおよそ以下の通り。
左側の整数を読み込む
スペースが来るまで入力を読んでスタックAに積む。文字コードが、数字は0011????
、スペースは00100000
なので、下から5ビット目を見れば数字かどうかが分かる。
右側の整数を読み込む
改行が来るまで入力を読んでスタックBに積む。改行の文字コードは00001010
なので、下から5ビット目を見れば数字かどうかが分かる。
足し算する
スタックA,Bから1桁ずつ取り出して、足し算して、その結果をスタックC(実際にはスタックAを反対向きに見たもの)に積む。
入力が何桁だろうと、スタックA,Bに最後に積んだものは(十進の)一の位なので、そこから順に計算していく。(二進の)1の位で足し算、2の位で足し算、4の位で足し算、8の位で足し算、足した結果が10以上なら「繰り上がりがある」という情報を持った上で10を引く(6を足す)。それをスタックAの反対側に積む。入力の最大桁数は4桁なので、(4桁未満の場合は0を補完して4桁とみなして、)これを4回繰り返すと上手くいく。
先頭の0を捨てる
出力する時は、先頭にある0は要らないので、スタックCの先頭から連続する0を取り出して捨てる。(この時、スタックCの底に目印(0000
~1001
でない値)をつける。)
出力する
スタックCの底の目印が来るまで、スタックCから1桁ずつ取り出して出力する。
EOF かどうかを判定する
EOF が来たら終了、そうでなければ最初に戻る。EOF が来たら終わるのは、Brainfuck の,+[-ほげほげ,+]
に似ていると思う。
最初に提出したコードは 1219 B、227 行であり、2番目に長い COBOL でさえ 222 B である。とにかく長い。
9
D 0
C 0
B 0
A 0
d 0
c 0
b 0
a 0
5
P L L
O K K
N J J
M I I
L H H
K G G
J F F
I E E
H D D
G C C
F B B
E A A
D 4 4
C 3 3
B 2 2
A 1 1
9 0 0 9 5 4 3 2 1
5
p l l
o k k
n j j
m i i
l h h
k g g
j f f
i e e
h d d
g c c
f b b
e a a
d 4 4
c 3 3
b 2 2
a 1 1
9 0 0 5 5 4 3 2 1
5
6
A A
a a
r A a
A r
a r
A a
s A q
A s
q s
A q
r s
B B
b b
q B b
B q
b q
B b
s B r
B s
r s
B r
q s
C C
c c
r C c
C r
c r
C c
s C q
C s
q s
C q
r s
D D
d d
q D d
D q
d q
D d
s D r
D s
r s
D r
q s
r B B
s C C
r s
r D
q q
q r
Q q q
r B q
B r
r q
B r
r B q
r r
s C r
C s
s r
C s
r C B
r q
r r
s D r
D s
s r
D s
1 A A
2 B B
3 C C
4 D D
A E E
B F F
C G G
D H H
E I I
F J J
G K K
H L L
I M M
J N N
K O O
L P P
M 1 1
N 2 2
O 3 3
P 4 4
a e e
b f f
c g g
d h h
e i i
f j j
g k k
h l l
i m m
j n n
k o o
l p p
6 6
6
5 5
5
R 0
S 0
T 0
5
4 T T
3 S S
2 R R
1 Q Q
T P P
S O O
R N N
Q M M
P L L
O K K
N J J
M I I
L H H
K G G
J F F
I E E
H D D
G C C
F B B
E A A
D 9 9
C 9 9
5 1 1
a 2 2
5 a
5 5
a 3 3
5 a
5 5
a 4 4
5 a
5 5
5
0 0 9 9 4 3 2 1
4 T T
3 S S
2 R R
1 Q Q
T P P
S O O
R N N
Q M M
P L L
O K K
N J J
M I I
L H H
K G G
J F F
I E E
H D D
G C C
F B B
E A A
5 4 3
5
0 0 0 0 9 0 9 0
9 H h L l 4 3 2 1
K 0
J 0
I 0
G 9 9
F 9 9
E 9 9
k 0
j 0
i 0
g 9 9
f 9 9
e 9 9
q 9 9
9
この記事を読んで、もっと短く書けるぞと思った人がもしいれば、是非提出してほしい(そもそも、この記事自体、誰向けなのか分からないが)。
Perl では「偽⇒0」は真だが「0⇒偽」は必ずしも真でない
Perl では、真偽値として解釈した値が偽であるならば、数値として解釈した値は 0 である。しかし、数値として解釈した値が 0 であっても、真偽値として解釈した値が偽になるとは限らない。
項 | 真偽 | +0 | .'' | 備考 |
---|---|---|---|---|
0 | 偽 | 0 | '0' | |
0b0 | 偽 | 0 | '0' | |
0x0 | 偽 | 0 | '0' | |
0e5 | 偽 | 0 | '0' | |
0.0 | 偽 | 0 | '0' | |
.0 | 偽 | 0 | '0' | |
'0' | 偽 | 0 | '0' | 空でない文字列で偽になるのはこれだけ |
'' | 偽 | 0 | '' | |
() | 偽 | 0 | '' | |
(123,456,0) | 偽 | 0 | '0' | コンマ演算子 |
(@a=()) | 偽 | 0 | '0' | |
undef | 偽 | 0 | '' | |
11 | 真 | 11 | '11' | |
011 | 真 | 9 | '9' | 8進数 |
0b11 | 真 | 3 | '3' | 2進数 |
0x11 | 真 | 17 | '17' | 16進数 |
1e5 | 真 | 100000 | '100000' | 指数表記 |
123.456 | 真 | 123.456 | '123.456' | |
0.123 | 真 | 0.123 | '0.123' | |
.123 | 真 | 0.123 | '0.123' | |
'11' | 真 | 11 | '11' | |
'011' | 真 | 11 | '011' | 8進数として解釈されない |
'0b11' | 真 | 0 | '0b11' | 2進数として解釈されない |
'0x11' | 真 | 0 | '0x11' | 16進数として解釈されない |
'0e5' | 真 | 0 | '0e5' | |
'1e5' | 真 | 100000 | '1e5' | 指数表記として解釈される |
'0.0' | 真 | 0 | '0.0' | |
'123.456' | 真 | 123.456 | '123.456' | |
'0.123' | 真 | 0.123 | '0.123' | |
'.123' | 真 | 0.123 | '.123' | |
'0abc' | 真 | 0 | '0abc' | |
'123abc' | 真 | 123 | '123abc' | |
'abc' | 真 | 0 | 'abc' | |
(0,123,456) | 真 | 456 | '456' | コンマ演算子 |
(@a=(0)) | 真 | 1 | '1' | |
(@a=(123,456,0)) | 真 | 3 | '3' |
AtCoder での Perl golf に関するメモ
最近、AtCoder の問題を(ゴルフで)解き始めた。それに関するメモ。気が向いたら追記する。
N
$_**=3,print$_,$/for<>
$_=<>;print$_**3,$/
print+($_=<>)**3,$/
$_=<>**3;print$_,$/
print$_**3,$/for<>
print<>**3,$/
S
$_=<>;print s/abc/xyz/r
$_=<>;s/abc/xyz/;print
print s/abc/xyz/rfor<>
s/abc/xyz/,print for<>
print<>=~s/abc/xyz/r
X Y
print eval<>=~y/ /+/r,$/
<>=~$";print$`+$',$/
print<>!~$"+$`+$',$/
n a1 a2 ... an
<>;$x+=$_ for split$",<>;print$x,$/
<>;$x+=$_ for<>=~/\d+/g;print$x,$/
<>;s/\d+/$x+=$&/gefor<>;print$x,$/
<>;<>=~s/\d+/$_+=$&/ger;print$_,$/
<>;$/=$";$x+=$_ for<>;print"$x
"
<>;print eval<>=~y/ /+/r,$/
ブログを始めるよりも前にあなごるで出題した問題
Anarchy Golf で自分が出題した問題について、ブログを始めたら何かしら書こうと以前から思っていたので書く。
850. A045718
素数±1 の数を 1 から 252 まで出力する問題。初めての出題だったので、簡単だし出題期間は1週間でいいよね・・・とか思って1週間にしてしまった。
861. tetration
テトレーションの問題。これを Whitespace で解こうとしたところ、普通に書くと TLE したので、2↑↑5 の代わりに 4**32768 の結果を出力して TLE を回避した。
889. 42
ultimate problem の入力と出力を逆にしたネタ問題。同じ入力に対して、異なる3つの出力が求められるので、何らかの乱数を使わないと解けない。しかも分岐が地味に面倒臭い。乱数を使わないと解けない問題として、123 という問題が既にあることは知っていたので、それとの違いをはっきり出すためにも、2回分岐するのはちょうど良かったと思う。Brainfuck では解けないと思っていたが、上手いこと cheat すると解けるらしい。
893. 32 div 0
Befunge のインタプリタの仕様を利用したネタ問題。Befunge の最短解が全体の最短解になる想定で出題した。exec を allow しているので、他の言語から Befunge を呼び出すこともできるようになっている。Befunge で最短解にたどりつくには、1Byte で 32 を作る方法を知らないといけない。
895. sandglass
入力を砂時計の形に変形する問題。あまり解答者が増えず、難易度調整の難しさを思い知った問題でもある。出題時に問題ページに署名をするようになったのはこの問題から。
902. 1 2 32 4 512
先頭が 1, 2, 3, 4, 5, ... , 100 になるような 2のn乗 の数を出力する問題。OEIS にもさすがにこれは載ってないだろと思ったら載ってて OEIS すげーってなった。
903. from 1 to 100
1 から 100 までの整数を改行区切りで出力する、とてもシンプルな問題。出題期間を初めてエンドレスにした。慣れていない言語に手を出すときに、まずは ASCII from 0x01 to 0x7f とセットでこれをやってみるといいんじゃないかな的な問題。一応、似たような問題として、Print out a lot _56K BEWARE_ という問題がある、ということを知ったのは出題したよりも後のことだった。
909. Convert hex to ASCII
16進数の入力に対して、最初の入出力例に示した変換を施す問題。FerNANDo で解くのがとても楽しかった。
913. differentiation
微分する問題。例外はあまり多くない方が良いと思い、なるべくシンプルに解けるような入出力にした。sed でも一応解いた。
914. antidifferentiation
不定積分する問題。こちらは敢えて例外を多くしてエンドレスで出題。面倒なのはよく分かっているので、解答者はあまりいないが気にしない。
916. FizzFizz
あの FizzBuzz をちょっと改変した問題。3のn乗の倍数なら Fizz をn回、5のm乗の倍数なら Buzz をm回出力する。この問題を出題した結果、FizzBuzz の解答も増え、何故か FizzBuzz の Bash の最短解が更新されるなどした。あと「アレンジ」が変な日本語だってことも分かった。
問題を解くのは楽しいので、出題者が増えれば嬉しいし、出題するのもそれはそれで楽しいので、今後も出題していきたいと思う。