37.50.48

%20 の ブログ

yukicoder No.502 階乗を計算するだけ

この記事は、yukicoder No.502 階乗を計算するだけ の解説というより、自分が書いたコードの解説です。

 

作問者による解説にもある通り、この問題は、予め一部の値を計算しておいて、それを埋め込むことで解ける。作問者は「例えば1000個を埋め込む」と解説しているが、速い言語であればそこまでたくさんの値を埋め込む必要はない。

n が 10^9+7 未満の場合について、10^8 毎に区切って 11 個の値(0!, 10^8!, 2*10^8!, ..., 10^9!)を埋め込むと 500ms ほどで AC ということが tails さんの提出したコードから分かっていたので、ほぼ同じようなコードを提出したところ、なぜか TLE だった。

原因を探ったところ、m=1e9+7;s=1e8; という部分に問題があった。

これは何なのかというと、普通にコードを書くと 1000000007, 100000000 という値が 2 回ずつコード中に出現し、それだとコードが長くなるので、グローバル変数(型名を省略すると int 型になる)を初期化して(このとき暗黙の型変換が行われる)、それらの変数を 2 回ずつ使うことでコードを短くしようとした結果生まれたものである。

これを使うと何が悪いのかというと、(実際には初期化した以降で変数の値が書き変わらないものの、)変数で剰余をとると定数で剰余をとるよりも遅いという問題がある。

const を使うとこの問題は解決できる

 

というわけで、ここからコードを縮めるにはどうすれば良いかというと、まず埋め込みを減らしたい。最大で 10^8 回のループを回して 500ms より少し遅いということから、2*10^8 回のループを回すと TLE することが予想される(実際に TLE だった)。

なので、166666668 毎に区切って 6 個の値(0!, 166666668!, 333333336!, ..., 833333340!)を埋め込むことにした(ここでもし 166666667 毎に区切ってしまうと埋め込む値が 7 個(0!, 166666667!, 333333334!, ..., 1000000002!)になってしまい、最後の 1 個が邪魔になる)。

埋め込む値の中に 500000003 という値があったのでそれを 5e8+3 と書くなどして 167B まで縮んだもののまだ長い。

 

そこで、文字定数を使って 156B まで縮めた。文字定数というのは、通常は 'a' のように 1 文字をシングルクォートで囲って使うものだが、複数文字を囲って使うこともできる(コードゴルフでは、1 文字を囲う使い方は基本的にしない。例えば 'a' より 97 の方が短いので 'a' を使う理由が無く、'z'122 では長さが同じなので 'z' を選ぶ必要が無い)。

複数文字を囲った場合、ビッグエンディアンで 4 バイトの値が得られる。例えば、'(.&F' は (((40*256)+46)*256+38)*256+70 = 674113094 となる。

 

文字定数はコードを縮めるには確かに強力だが、'', が何回も出てきて長い。そこで役立つのが、文字列リテラルである。文字列リテラルが持つ値は文字列の先頭のアドレスなので、これを int* 型のポインタ変数に代入すれば、int[] 型の配列と同様の使い方ができる。

int 型の値は、リトルエンディアンで 4 バイトで表されるので、例えば、((int*)"****F&.(****")[1] は 70+256*(38+256*(46+256*40)) = 674113094 となる。

これで 144B まで縮んだが、文字列リテラルの中の \r がウザい(例えばタブは \t という表現を使わずに直に書けるのに対して、\r\n はそういうことができない)ので、166666668 毎に区切っていたものを 166666669 毎に区切るようにして、\r が不要な値を使うようにして 143B

 

繰り返す回数を表すのに使っていた変数 i が必要なかったのでそれを削って 136B

s の初期化は文字定数を使った方が短くて 135B

文字定数を直に使えばそもそも const m,s は必要なかったので 132B

n<mm は文字定数を使うよりも 1e9+7 の方が短くて 131B

xlong 型である必要が無かったので、long ni を削った時に空いた main 第 1 引数に入れて 130B

*a="\x01\x00\x00\x00M\xfb#\x07O\x0f\xed9`\x1d\xe17\xa6\xcbp%?y\x8d\x0e";
x;main(long n){
    scanf("%ld",&n);
    for(n<1e9+7?x=a[n/'\x09\xef!\xad']:0;n%'\x09\xef!\xad';)
        x=x*n--%';\x9a\xca\x07';
    printf("%d",x);
}

赤で示したものは実際には十六進数で表された文字コードの文字そのものであり、コピペでは正しく動かない。例えば \xed99 がエスケープシーケンスの一部と誤解され、\xd9 のような扱いになるからである。

 

この記事の公開後、lpha_z さんが 129B で AC した。

yukicoder No.491 10^9+1と回文

この記事は、yukicoder No.491 10^9+1と回文 の解説です。

N の桁数を L とする。
10^9+1 の倍数かつ回文数であるような 1 以上 N 以下の整数のうち最大のものを M とする。
M が求まれば、最終的な答えは簡単に求まる。

例えば、M=543212345543212345 (これを 54321... と表記する) の場合について考える。

10^9+1 の倍数かつ回文数であるような L 桁の整数のうち、

  • 5432x... のものは 54320... から 54321... までで 2 個
  • 上記以外で、543xx... のものは 54300... から 54319... までで 20 個
  • 上記以外で、54xxx... のものは 54000... から 54299... までで 300 個
  • 上記以外で、5xxxx... のものは 50000... から 53999... までで 4000 個
  • 上記以外で、xxxxx... のものは 10000... から 49999... までで 40000 個

であり、これらを合計すると 44322 個である。

10^9+1 の倍数かつ回文数であるような L 桁未満の整数のうち、

  • 10 桁未満のものは 0 個
  • 10 桁または 11 桁のものは 1... から 9... までで 9 個
  • 12 桁または 13 桁のものは 10... から 99... までで 90 個
  • 14 桁または 15 桁のものは 100... から 999... までで 900 個
  • 16 桁または 17 桁のものは 1000... から 9999... までで 9000 個

であり、これらを合計すると 19998 個である。

以上より、求める個数は 44322+19998=64320 である。

M を求めるには、M 候補を最初は (L 桁の) 0 にしておいて、上位の桁から順に floor((L-8)/2) 桁について、回文数になるように M を変更しつつ、M≦N を満たすように決めていけばよい。

10^9+1 の倍数かつ回文数であるような L 桁の整数の個数は、M の最上位の桁の値から 1 を引いたうえで、M の上位 floor((L-8)/2) 桁の値に 1 を足したものである。

10^9+1 の倍数かつ回文数であるような L 桁未満の整数の個数は、9*10^floor((i-10)/2) (i=10, 11, ..., L-1) の総和である。

これらの和が求める個数である。M が L 桁にならない場合、L 桁未満の数についてだけ考えればよい。

コード

$"='';
@M=(0)x(@N=<>=~/./g);
for($k=0;2*$k<=@N-10;++$k){
	@M[$k,$k+9,$#N-$k,@N-10-$k]=($|?9:$N[$k])x4;
	@M[$k,$k+9,$#N-$k,@N-10-$k]=($N[$k]-1)x4,$|=1if"@M">"@N"
}
$%="@M[0..(@N-10)/2]"+1if$M[0]--;
$%+=9*10**($_>>1)for 0..@N-11;
print$%,$/

正規表現の積

誰か解いて

追記ここから

時間制限: 2秒 / メモリ制限: 512MB

追記ここまで

問題文

[a-z.] のみから成る2つの正規表現 A, B が与えられる。
A, B に共にマッチするような文字列の集合全体を、[a-z.*|] のみから成る正規表現 C で表したい。
このとき、C に含まれる | の個数の最小値を答えよ。

入力
A
B

入力は以下の制約を満たす。

  • 1 ≦ |A|, |B| ≦ 10
  • A, B には、[a-z.] 以外の文字は含まれない。
サンプル

入力1

a
b

出力1

1

C を例えば a.*b|b.*a と表した場合、| の個数は1で、これが最小値である。

入力2

a.a
.b.

出力2

2

例えば aba|a.a.*b.|.b.*a.a と表せる。

入力3

.a.b
a.b.

出力3

2

例えば aabb|.a.b.|a.b.*a.b と表せる。

入力4

b.a.
.a.b

出力4

5

例えば baab|.abba.|b.a.b|.a.b.a.|b.a.*a.b|.a.b.*b.a. と表せる。
追記:赤で示した部分が抜けていたので追加した。それに伴い出力4を修正した。

入力5

confused
sed

出力5

0

例えば confused と表せる。

Perl でコードゴルフをする時に空白が必要なのはどういう場合か

普通にプログラミングをする上では、空白文字(スペース・タブ・改行)というものは多用されるが、文法上必須であるものは少ない。コードゴルフにおいては、最終的に出来上がるコードには、文法上必須であるような空白以外は不要である。Perl で空白が必要になるのは、空白が無いと1つのトークンとして解釈されてしまうような2つのトークンの区切りを示す場合である。

/[A-Z_a-z] [0-9A-Z_a-z]/

空白が必要なのは基本的には上記の正規表現にマッチするような場合である。
print 1, while s/hoge/fuga/, for 1..100 などがこれに当てはまる。

print $a, 0 for, 0 while, $% for, for <> などはこれには該当しないので空白は不要である。

0 x$a

これは丁寧に書くと '0'x$a であり、文字列としての 0$a 回繰り返すことを意味する。
0x$a は、十六進数としての 0 の直後に $a があると解釈されてしまう(エラーになる)ので、それを回避するために空白が必要。

123 .$a

これは丁寧に書くと '123'.$a であり、文字列としての 123$a を結合することを意味する。
123.$a は、実数としての 123 の直後に $a があると解釈されてしまう(エラーになる)ので、それを回避するために空白が必要。

/hoge/ x

Perl では、/./g, /a/i のように、正規表現にオプションを付けることができる。正規表現の直後に or, x といった演算子を書きたい場合、ox はオプションとして存在するので、空白が必要。

/hoge/for/hoge/while は、fw がオプションとして存在しないので、v5.16 までは空白が不要だったが、v5.18 からは空白が必要になった。
/hoge/and は、a がオプションとして存在するのに何故か v5.16 までは使えていたが、v5.18 からは空白が必要になった。

perl v5.18.0 での変更点 > 英数字演算子は正規表現の閉じ区切り文字から分離されなければならなくなりました

$' for

$' 自体は特殊変数なのだが、直後に /[A-Z_a-z]/ があると、' は無視される、つまり、$'hoge$hoge と同じ意味になる、という謎の機能があるので、それを回避するために空白が必要。

この記事に対してコメントを貰ったので追記。

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)

#141471 %20 による Bash のコード

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)

#141472 %20 による Bash のコード

read;tr \\n- +_|dc -e?1.0000000000*p

いかにも無駄がありそうだったので dc を呼ぶより前の部分をいじった。書き方が変わっただけで、やっていることは全く同じである。

 

2016-12-26 05:25:45 35B(-1)

#141473 %20 による Bash のコード

read;tr \\n- +_|dc -e?.0000000000+p

1を掛けるのと0を足すのは同じことで、0.0000000000 は先頭の 0 を省略できるということを思い出してこうなった。

 

2016-12-26 11:07:10 27B(-8)

#141500 tails さんによる Bash のコード

read;tr \\n- +_|dc -e?Ak1/p

A10 の短い書き方。k は精度(小数点以下何桁まで精度を持たせるか)を設定する。1/ によって設定した精度が有効になる。k を利用しようとは思っていたのだが、1で割れば良いということを忘れていて、tails さんに先に提出されてしまって最短を取り逃してしまった。

 

 

とまぁ、ここまではよくある話である。

 

 

この6問のうちの1問がこれ。

 

2016-12-26 19:30 ~ 21:00 頃

  • dc では、小数点以下10桁までを表示するつもりでコードを書いても、00 と表示される
  • dc では、0.なんたら.なんたら と表示される

という、dc に特有の変な性質のせいで、出力すべき答えが 0.00000000000.1000000000 になるような入力が与えられた場合、dc を使った解答では想定される出力が得られない、ということが分かった。というわけでチャレンジ。

影響範囲は dc を使った解答をしている %20 と tails さんの2人だけだろうと思っていたのだが、

 

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)

#141621 %20 による Perl のコード

<>;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)

#141622 tails さんによる Bash のコード

read;tr \\n- +_|dc -e?d1~rn46P[A*1~rd*vndzC\>f]dsfx

これは、もう1つのコーナーに対応していない。

 

答えが -0.9999999999 以上 -0.0000000001 以下の場合、「符号つきで整数部を表示、. を表示、小数部の絶対値を表示」というようなコードは落ちる。

 

2016-12-26 22:04:55 49B(-2)

#141624 tails さんによる Bash のコード

read;tr \\n- +_|dc -e?d1~rn46P -eA*1~rd*vn{0..9}r

これも、もう1つのコーナーに対応していない。2度目のリジャッジの直前に提出された。

 

2度目のリジャッジの結果、さらに多くの嘘解法が落ちた。

 

2016-12-26 23:16:48 57B(-16)

#141631 tails さんによる Perl のコード

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)

#141635 tails さんによる Perl のコード

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有理数型に変換すれば簡単に計算できる。なるほど。

 

2016-12-28 04:34:42

#141847 %20 による Ruby のコード(WA)

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)

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)

#141858 %20 による Ruby のコード

gets;puts"%.10f"%(eval"+gets.to_r"*100)

ところでその .round(11) とやらは要るの? という感じで削ってみた。

 

2016-12-28 05:48:11 38B(-1)

#141859 %20 による Ruby のコード

gets;puts"%.10f".%eval"+gets.to_r"*100

そういえば、Ruby では演算子はメソッドのシンタックスシュガーだから括弧外せるなぁ。

 

100 は100以上の整数であれば何でも構わないので、$$(PID を表す特殊変数)が使えるかと思ったら yukicoder では $$ は小さいらしく WA。1行目の入力が邪魔なのも何とかならないかなぁと思考錯誤しても何ともならない。

 

2016-12-28 13:58:20 37B(-1)

#141905 tails さんによる Ruby のコード

puts'%.10f'.%eval`sed '1!s/$/r+/'`+?0

なるほど、sed を使えば色々同時に解決できる。1!s/$/r+/ というのは1行目以外の行の末尾に r+ をつけるということ。1.5r のように書くと有理数型にできるらしい。

 

2016-12-28 14:14:54 36B(-1)

#141910 %20 による Ruby のコード

puts'%.10f'.%eval`sed 1\!s/$/r+/`+?0

sed'' を省略できる場合がある。ただし、エスケープが必要になる文字がある。

 

2016-12-28 14:25:23 35B(-1)

#141915 tails さんによる Ruby のコード

puts'%.10f'.%eval`sed 1!s/$/r+/`+?0

エスケープ要らなかったらしい。

 

 

終わり。

コードゴルフをする場について

誰向けの記事なのかよくわからない。

Anarchy Golf

  • ゴルフ場
  • 111言語
  • esolang 多め
  • テストケースは最大3件で全て可視
  • 出題期間は2週間が基本だが、1時間から4週間、無期限もある
  • 出題頻度は時によりばらばら
  • 誰でも作問・出題できる
  • 単に解くだけなら簡単な問題が多い

AtCoder

  • 競プロ場
  • 22~52言語
  • 古い問題は使用可能言語が少ない
  • 一部の esolang も使える
  • テストケースは可視と、不可視(コンテスト終了後に可視になるものもある)が両方ある
  • 出題期間は競プロのコンテストとしては約2時間
  • 基本的に、毎週土曜(か日曜)にコンテストとして6問出題される
  • レート2400以上の人を対象に作問者を募集している

yukicoder

  • ゆるふわ競プロ場
  • 34言語
  • 一部の esolang も使える
  • テストケースは可視と、不可視(コンテスト終了またはACで可視になる)が両方ある
  • 嘘解法を落とすためにテストケースが追加されることがある
  • 出題期間は競プロのコンテストとしては約2時間
  • 基本的に、毎週金曜にコンテストとして4問出題される
  • 誰でも作問できるが出題には審査がある

CodeFights

  • ゴルフ場でもある
  • 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 小さい数の最後の)の直前に()をつけ足す」という方法で生成できる。