2015年07月

2015年07月16日

飽きずにまたコードゴルフです。

今回の問題はyukicoderの192です。

この問題は101から1000の整数Nを入力してN-100からN+100の範囲に含まれる合成数を求める問題です。

範囲内の数を適当に選んで素数判定とかすれば良さそうですがもっと単純に考えられますね。
素数判定をしなくても最後の桁が4の整数は全て合成数です。というわけで入力した文字の最後を4に書き換えて終了です。
という解法で最初は通しましたがもっと簡単な方法があります。
解説(ログインが必要です)の通り近い偶数を見つければいいだけです。
最初Nの範囲が1からだと勘違いしていたので最後の桁を4にするという方法を使いましたが入力される数は101以上なので入力された数が奇数なら1を引いて出力、偶数ならそのまま出力すればいいようです。
Rubyで書くと

p (a=gets.to_i)%2<1?a:a-1

(25Byte)
とかでしょうか。aに足す数は-99から99までの奇数なら問題無いと思います。ちなみに3以上なら入力が一桁とかでも大丈夫のようですね。

こんなことしなくても単純に解説通りに

p gets.to_i/2*2

(15Byte)
とすれば終了です。ここまでならまあ普通に計算式がわかれば書けますね。入力が3以下だと合成数以外が出力されますが入力は3桁以上あるので問題無いです。
これをビット演算で縮めます。

この計算がどのようなことをしているかというとNが奇数ならN-1,偶数ならそのままを出力というのは解説通りですが内部のビットの様子をちょっと見てみましょう。入力が181だった時2進数で表した時の様子を見てみましょう。書くのが面倒なので下位8ビットのみ書きます(その左側の24ビット(?)は全部0です)

10110101

これを/2すると

01011010

となり、そこに*2すると

10110100

となります。10進数で言うと180になりました。
一番右の1が消えましたね。
というわけで/2*2というのは一番右の1のみを消していることになります。これをビット演算で行う場合どうやら最初の数の最後の1ビットを0にする操作を行えばいいようです。
というわけでXORを表す記号の^を使ってN ^ 1とすれば良さそうです。と書きましたがこれはNが奇数の場合は有効ですが偶数だとダメです。1回これでWAを出してしまいました。奇数の場合はN-1になってくれますが偶数だとN+1となってN+1が素数の場合はアウトです。
というわけで違う方法を使いましょう。ビット演算に引き算があればN(引き算の記号)1と書けば終わるのですが引き算の記号は残念ながらありません(たぶん)。同じことをやる方法としてN&(~1)が使えます。Rubyのコードにする時はカッコはいらないのでN&~1と書けますビット反転した分1文字長くなってしまいましたがまあこれはしょうがないですね。~1は-2なのでどちらを書いても同じです。というわけで

p gets.to_i&-2

(14Byte)
と書けば終了です。

p gets.to_i/2*2

より1文字短くすることが出来ました。
とここまでやってもう1文字短縮する方法がありました。-2ではなく~1を使う方法です。同じ数を表すもので同じ文字数なのですがpとの間のスペースを消すことができます。ということで

p~1&gets.to_i

(13Byte)
で終了です。


1の代わりに3,7,15,31,63などを入れれば同様に下位の何ビットかを消すことができますね。どこかで使えそうです。逆に同じ桁を1で埋めたい場合はAND演算の&ではなくOR演算の|です。
ここでRubyの話は終了で次はC言語。C言語は古くからある言語でショートコーディングの世界でも結構人気があります。なんとなくやってみました。

main(n){scanf("%d",&n);printf("%d\n",n&-2);}

という感じでしょうか。C言語のショートコーディングテクニックを適当にググればこの程度は普通ですね。ちなみにreturn文を省略してますが一部のオンラインジャッジなどでは通るようですが残念ながらyukicoderではランタイムエラーになってしまいます。
上のコードは削れないように見えますが少しだけ短くできます。scanfは入力するための関数で返り値を利用することはほとんどありませんが関数なのでちゃんと返り値があります。成功すると代入した数(今回は代入する変数が1個なので1)が、失敗したら-1が返ってきます。この-1という値は比較的よく使われてfor(;~scanf(););とすることでscanfが成功するうちはループを回す使い方です。今回は失敗した時の-1ではなく代入した時に返ってくる1を利用します。
ここまで来るとわかると思いますがこの1と言うのは意味のある数ですね。というわけでこの1をビット反転して-2にして使います。

main(n){printf("%d\n",~scanf("%d",&n)&n);}

先ほどのコードに比べて一つの式になったことで;が一つ減ったのと-2がなくなったので3文字減、ビット反転の演算子で1文字使ったので合計で2文字減らすことが出来ました。
ちなみに自分ではよくわかってませんがn&~scanf("%d",&n)と書いても動きます。
まあどっちにしてもyukicoderで通すにはreturn 0;する必要があります。



(17:22)

2015年07月12日

なんとなくやってみました。
今回やってみたのはAtCoderBeginnerContest(以下ABC)の過去問のA問題です。
今回も例によってRubyです。基本的にランキングとか最高記録というのはRubyの中のランキングです。
基本的に過去問では全てのコードが公開されるので複数のコードからいいところをコピペすれば記録は抜けるので微妙なところもあります。
なので記録を縮めるために自分が気づかなかったところとか自分が縮めたところをまとめていきます。最短コードを解説するわけではありません。
一応かなりの問題で新記録を出せているのでそれなりに有効だとは思います。
まあAtCoderはゴルフ場ではないのでどの程度プロゴルファーが参加しているかという問題もありますが。


というわけで1問ずつ

ABC001-A

2つの整数が改行を挟んで入力されてその差を取るだけの問題。何も考えず

p gets.to_i-gets.to_i

とすれば終了です。特に短くするためのテクニック等は必要なく普通に計算すれば終わりです。あえて言うなら出力にpを使うくらいでしょうか。普通に書いても似たようなコードになることも多いようです。数を出力したい時は特に問題なくputsと同じ出力をしてくれます。コード長ランキングを見ると同じ文字数の人が何人かいますね(コードも全く同じです)。

(21Byte→21Byte)

ABC002-A

2つの整数がスペース区切りで与えられ、それの大きいほうを出力すればいいみたいです。
文字列でソートすると辞書順になるので2つの数の桁が違うとちゃんとソートできません。なので比べるときは数に変換する必要があります。
というわけで

p (gets.split.map &:to.i).max

とやれば終了です。と思って提出してランキングを見ると1文字負けてしまいました。原因はカッコの付け方で

gets.split.map(&:to_i).max

と書いていれば一つスペースを減らせます。この書き方は気づきませんでした。ゴルファーにとっては常識なんでしょう(僕はゴルフ初心者です)。
まあ1位の記録とはなりませんでしたが結構短くするための要素はある問題になってます。
まず2つの値を数に変換する為に2つに分割します。この時splitを使いますがこのsplitは引数無しで使うとデフォルトでは半角スペースを指定したものになります。なのでsplit(' ')などとやる必要はないです。
あとよく使われるのがmap &:to_iです。コードゴルフに限らず特にAtCoderではこういう形で値を読み込むことが多いです。普通に使えるので便利ですね。今回は変数に入れずに使ってますが

a=gets.split.map &:to_i

とやれば整数を要素に持つ配列aが宣言できます。また、配列の要素が決まっている時、例えば2個の時は

a,b=gets.split.map &:to_i

とすればa,bは整数として使えます。変数は増えますがa[0]とかやる必要が無いので短く書けることが多いです。問題によってはabcとかとかxyzとかそのまま使えるのでこれも便利ですね。足したり引いたりするには便利です(ソートとかする場合は配列のが便利ですね)。

ちなみに最後のmaxは配列の要素の中から一番大きいものを取り出します。[配列].sort[-1]と同じですね。ちなみに小さいものが欲しいならminです。

(28Byte→29Byte)

ABC003-A

n面のサイコロの期待値の問題です。
サイコロの期待値は(n+1)/2です。
問題はこのサイコロの期待値に10000を掛けた値を出力します。
というわけで普通に考えると

p (gets.to_i+1)*5000

です。簡単ですね。とここで終る問題ではないです。この数式は実は短くなります。まず5000というのは5e3と書くことができます。1文字短くなりましたね。
次に(gets.to_i+1)ですがこれも短くすることができます。ゴルフではとにかくカッコは消せ!という感じで扱われます。かけ算より優先順位の低い足し算を先にやりたいのだから消せないように思えますが次の形で書けます

p 5e3.*gets.to_i+1

こうすることで先に足し算を行うことができます。なんでそうなるかはここに書いてあります。
ここまでで終わりかと思いきやまだ縮められます。
結構有名な方法ですがビット演算を使うことでnが整数の時、n+1を-~nと書くことができます。
n+1と-~nでは長さは変わりませんが式の中ではうまく機能することがあります。
例えば-(n+1)は~nとなるのでこの場合は3文字の削減ですね。
というわけで今回の問題は最終的には次のようになります。

p -~gets.to_i*5e3

ここまでは普通に出るかと思ったら自分が初めてのようです。ビット演算で短くする方法を使ってる人はいませんでした。まあ僕はその前に5000を書いたのを出した後他の人のソースをみて5e3に気づきました。それまでの最高記録のコードは一個前のです。

(19Byte→18Byte)


ABC004-A

単純に入力を2倍するだけなので特に注意することも無いですね。1位タイもけっこういます。

(13Byte→13Byte)


ABC005-A

2つの数字を入力してわり算をするだけです。何故か最高記録を出すことができました。
こんな感じです

a,b=gets.split;p b.to_i/a.to_i

ちなみに他の人とどこが違うかというと他の人は

a,b=gets.split.map &:to_i;p b/a

としてます。後者はまとめてto_iできるので短くなりそうですが実は.map &:to_iより.to_i.to_iのが1文字短いです。2つまでなら分けて書いた方がお得なのです。繰り返しはとにかく避けたくなりますがこういう場合もたまにはあるのです。というわけで2つの変数で合計2回しか.to_iが必要ない時はmapしてやるよりも別々に書いた方が短く書けます。

(31Byte→30Byte)


ABC006-A

入力が3の倍数だったらYES、違ったらNOと出力する問題です。
普通に考えると
puts=gets.to_i%3==0?:YES:"NO"
でしょうか。出力するYES、NOは文字列にするよりシンボルにした方が1文字短くできます。三項演算子では片方は使えない(またはスペースが必要)ので片方は文字列です。
これはまだまだ縮まるんですが、普通に考えるとこうですね。僕も最初はこれを提出しました。
さらにここから%3==0と言うのは1文字短くすることができ、%3<1と書けます。取る値は0,1,2しかないので<1なら0ですね。上の式にこれを加えた文字で1位タイでした。ちなみにタイの1位のコードは判定方法が違います。
ここまでかと思ったらもう一つ短縮する方法がありました。この問題では入力される数が一桁(1≦N≦9)という条件があります。これが実はもう1文字縮められる要因になってました。
ここで使うのはto_iではなくordというメソッドです。
ordは文字の文字コード(数)を返してくれるメソッドです。
例えば"0".ordをすると48が返ってきます。ちなみにgetsの値は"5\n"とかになりますが、複数の文字による文字列にordを使うと最初の文字を数値変換したものが返ってきます。なので"0\n".ordも48です。
"0".ordは48ですが1,2,3...と行くとordも49,50,51...となるのでto_iをそのままordにすれば問題なく同じ式として機能します。最終的にはこうなりました。

puts gets.ord%3<1?:YES:"NO"

記録を1文字更新しました。やったね。

(28Byte→27Byte)


ABC007-A

特に何も書くことがないですね。

(13Byte→13Byte)


ABC008-A

この問題もABC004のと同じようにto_iを分けたら最高記録になりました。ちなみにAtCoderでは改行が2バイト扱いなので改行せず;で1行にした方が1バイト短くなります。

s,t=gets.split;p t.to_i-s.to_i+1

最後の+1はビット演算で消せそうですが先頭に-~と二文字つける必要があるのでビット演算を使っても短くできないですね。

(33Byte→32Byte)


ABC009-A

N/2でNが奇数ならもう1足せばいいようです。というわけで(N+1)/2を使います。
先程も使った~nを使えば良さそうです。

p -~gets.to_i/2

これで終了です。例によってビット演算でn+1を作っていた人はいなかったので最高記録です。

(16Byte→15Byte)


ABC010-A

特に問題はないですね。
getsから改行を取り除くにはgets.chompを使うことが多いですが最後の1文字を消すchopでも問題ないです。1文字短いのでこちらを使います。

(19Byte→19Byte)


ABC011-A

複数の同じ最短コードが提出される簡単な問題です。省略。

(16Byte→16Byte)

ABC012-A

2つの要素を入れ替える問題のようです。splitして配列にした後reverseで逆向きにしてjoin(" ")すればいいようです。ちなみに配列のjoin(" ")は*" "と書くことができます。これで最短コード。結構簡単な問題なようです。
しかし僕はたまたまですが違う方法でやりました。ソースは次のようになります。

a,b=gets.split;puts b+" "+a

この方法を使った人はいませんでしたが次のコードと文字数は一緒です。

puts gets.split.reverse*" "

(27Byte→27Byte)


ABC013-A

gets.ordを使えば簡単に解ける問題でした。"A".ordは65なので

p gets.ord-64

でいいですね。ちなみに最初はordを知らず

p " ABCDE".index(gets.chop)

と書いていました。27文字で2倍以上です。今気づきましたがgets.chopは今回は1文字だけ取得したいのでgets[0]で良かったみたいです。こっちのが少し短いですね。

(20Byte→13Byte)


ABC014-A

2つの数字を入力してなんか計算をするようです。
余りとかを使いそうな雰囲気ですね。
a%bは使いそうですがなんだかちょっと違うようです。
答えは(b-a%b)%bのようです。b-a%bかと思ったら違いました(ちょうど配りきれる時にアウトになるようです)。変数はできるだけ使いたくないですがbは3回出てくるのでbだけ変数を使います。

p (-gets.to_i%(b=gets.to_i)+b)%b

aを先にgets.to_iするために余計なマイナス符号が付いてしまったりカッコが多いですが仕方ないような気がします。ちなみに(変数の文字は違いますが)ここまでの答えはありました(と思ったら無駄なカッコが1組ありました、なぜ?)。
実はもう少し短くする方法があります。もっと簡単な数式で答えが求められます。
でその数式は(-a)%bです。
マイナスの値の割った余りとはなんぞやと思ってしまいますが僕もよくわかってないです。まあこういう式が使える(場合がある)ということは頭の片隅に置いておきましょう。僕は適当に遊んでいたら発見しました。というわけでちょっと長かった数式が一気に短くなりました。使用も1回だけなので変数も使わなくてすみます。というわけでこうなりました。

p (-gets.to_i)%gets.to_i

一気に短くなりました。大勝利です。と思ったらこのカッコもいらないようです。

p -gets.to_i%gets.to_i

ここまでですね。

(34Byte→22Byte)


飽きてきた長くなったので今日はこのくらい。残りの問題はまだ適当です。

(22:00)

2015年07月09日

競技プログラミングをやっているとコードゴルフが楽しそうな問題があるのでたまにやっています。
コードゴルフは課題に対してとにかく短いコードを書けって感じの遊びです。
今回ちょっと頑張った問題はAOJの0060番です。ちなみに今回使う言語はRubyです。
とりあえず続きの文章を読む前に問題を読んでください。

とりあえず自分のカードの数をa,b,相手の見えているカードをcとします。
この問題はちょっと考えればわかりますが20-(a+b)以下の数字を引く確率が50%を超えればYES、そうじゃなければNOとすればいいですね。
残りのカードは7枚なので(山には6枚ですが相手の1枚は見えないので7枚として考えればいいです)見えてないカードの中から20-(a+b)以下のカードを数えて4枚以上ならいいわけです。
他のソースコードを見てみると実際このようにカードを数え上げる方法がよく使われています。
何となくいろいろなソースコード(言語によらず)を調べてみると面白いコードがありました。
コードゴルフ的にはやや不利なC言語で書かれてるにもかかわらずなんと全言語で1番短いです。
中身を見てみるとなんと判定に使われている式が

(a+b)*6-c<92

です。初め見た時「こんなんで判定できるの?」と思いましたが実際結構うまくいくようです。この式をRubyで書けば1番短いコードになって終了ですがしかし調べてみるとテストケースに含まれない一部のパターン(a+b=16のあたり)では間違った答えを出してしまうことが分かったのでこの式を使うのはやめました。ちなみにテストケースは変更される場合があるので今でもこの数式が通用するかはわかりません。

しかし数式一つで判定するという考えは参考になります。というわけで間違った部分に対応できるように新しい数式を探す方針でなんとかすることにしました。


まずa、b、cがどのような場合にYES、NOとなるかを調べてみることにします。

a+bが17以上の場合はどうやってもパターンがありません。つねにNOになります。Cに関係なく引いてもよいカードは山に3枚以下です。
a+bが16の場合はCが5以上ならYES、それ以外はNOです。
a+bが15の場合はやや複雑になります。AとBの大きいほうが10(つまり10と5の組)だった場合Cが5以上ならYES、それ以外ならNO。AとBの組が(6,9),(7,8)だったらYESです。
a+bが14以下の時はYESになります。

答えを出すためにCが関係あるのはA+Bが16または15の時(の一部)のみになります。
この時はCの範囲が同じなのでまとめてどうにかしたいですね。
式にすると
a+b==15||a+b==16
になりますがさすがに長いし返って来るのは真偽なので扱いにくいです。
なので
(a+b+1)/2
を使います。これならA+Bが15でも16でも同じ値になるので式の中でも扱いやすいです。ちなみにビット演算を使うことでコードゴルフ的にはこれはもう少し短くできます。
(a-~b)/2
と書くことで同じ値になります。~x=-(x+1)です。
これを使って計算式を立ててみます。
色々試行錯誤して出来上がった数式が次のです。(式の正しさを見るためなのでビット演算による文字列短縮はしていません)

(a+b+1)/2*6-c<45

最初のあの数式よりは長いですがそれなりに短いですね。これで終わりかと思ったらa+b==15の時の場合分けを忘れていました。これじゃ駄目です(6 9 4とかの場合に間違った答えが出ます)。

というわけでa,bの大きいほうの数を使って新しい計算式を作ることにしました。
ちなみにa,bの大きいほうを取得したい場合は[a,b].maxと書けばいいです。
というわけで次は(a+b+[a,b].max)の値を使うようにしてみます。
そうするとcによって場合分けする(a+b+[a,b].max)の値が25,26になります。これでなんとかなりそうかと思ったら実は(a,b)が(8,9)の時にも(a+b+[a,b].max)は26になってしまいます。ダメみたいですね。


というわけで1つの式でなんとかするのは無理そうだったので違うアプローチを使います。cの範囲を調べなきゃいけない範囲というのは(a+b+1)/2==8の時です。その時だけさらに判定をしてそうじゃなければ大きければNO、小さければYESを出力すればいいわけです。

Rubyの面白いメソッドとしてx<=>yと言うものがあります。これはxのが小さい場合は-1,同じだったら0,大きければ1が返ってきます。というわけでこれで3つの場合分けをすることができます。

(a+b+1)/2<=>8

とすればいいですね。これをさらにどうやって使うかというと配列のインデックスとして使います。配列の変数を宣言するのは(複数回使わなければ)文字数の無駄なので
[nantoka,:NO,:YES][(a+b+1)/2<=>8]
と書きます。配列[-1]は配列の最後の要素が取り出せるのでこれで8以外の場合は正しい結果、8の時はnantokaが評価された値が取得できます。ちなみにシンボルを使っても勝手に文字列に変換して出力してくれるので"NO",”YES”と書くより短くできます。これで8の場合のnantokaを書けば終了です。このnantokaを考えることにしましょう。

というわけでa+bが15または16の場合を考えます。
このとき(a,b)が(6,9),(7,8)(順番関係無し)ならYES、そうじゃなければcの値によって結果は変わります。
[a,b].max,[a,b].minを使っても場合分けできないので他の方法を考えます。
なんとかして考えた方法は次の式です

a*a+b*b>117&&c<5?:NO:"YES"

三項演算子を使う時は後の要素(falseの時の値)はシンボルが使えないのでここは文字列です。Rubyではx^nをx**nと書くことができますが2乗なら普通にかけ算のが短いですね。
これなら(6,9),(7,8)の時はa*a+b*bが117,113になり、他の場合(Cによって変える場合)は125以上になるので場合分けすることができました。以上をまとめると正しい結果を得るためには次のような式を書けばいいことになります。

[a*a+b*b>117&&c<5?:NO:"YES",:NO,:YES][(a-~b)/2<=>8]

これで正しい結果を得ることができました。入出力などの部分を含めて全部書くと

#!ruby -apl
a,b,c=$F.map &:to_i
$_=[a*a+b*b>117&&c<5?:NO:"YES",:NO,:YES][(a-~b)/2<=>8]

となりました。これで終わればよかったのですが実はこれRubyで一番短いコードに(10文字も!)負けています。苦労して違う方法を採ったのになんということでしょう。これを何とか短くします。できるのでしょうか。


これを見てなんか短くできそうなのは:NO:"YES",:NO,:YESと繰り返されている所です。同じ文(まあ文ではないですが)を繰り返すのはコードゴルフに限らず良くないことです。
というわけで繰り返されてるので変数を使いましょう。
y,n=:YES,:NO
とすれば
:NO:"YES",:NO,:YES を
n:y,n,y と書くことができそうです。短くなったような気がしますが実は長くなってます。駄目でした。あとこう書くと三項演算子の部分で構文エラーになってしまいます。これを回避しようとして次のような文にしました。

$_=[a*a+b*b>117&&c<5?n=:NO:y=:YES,n,y][(a-~b)/2<=>8]

これで2文字短くすることができました。ですがこれは実際には動きません。三項演算子の結果は片方しか評価されないのでyかnの片方の変数は宣言されません。動いたとしてもまだ文字数で負けています。


というわけで他の方法です。

そもそもなぜこんなこと(YESとNOが繰り返される)になっているかというとx<=>yを使って3つに場合分けをしたうちの一つをさらに条件分けしているためです。結構単純な3択なら配列で3つの要素にアクセスするのは悪くないかもしれません。
あとNOとYESの繰り返しもそうですが<=>という3文字も使う記号やアクセスするために[]を使っていたりとスマートな解法のように見えて意外と長いことにも気づきます。
結構有効に見えた[][x<=>y]作戦はコードゴルフ的には意外とダメなようです。

答えは2つなのだから3つから選ぶ方法は良くないような気がしてきました。なんとかならないかと考えていた時にあることに気づきました。
(a-~b)/2==8の場合に判定していた数式は他の範囲でも使える場合があるということです。
具体的に言うと(a*a+b*b>117&&c<5)という式はa+bが(15,16のときだけではなく)14以下の時にも使えます。というか常に条件を満たしません(条件を満たさないので正しい結果になる)。a+b>16の時は使えませんが3択が2択に減りました。というわけで3つの場合分けではなく2つの場合分けをすればいいという事に気づきます。これで[,:NO,:YES][(a-~b)/2<=>8]とかいう長い文字列を削除することができました(a+b>16を判定するための式は追加する必要がありますが)。


というわけで最終的にはa+b>16かどうか、a*a+b*b>117&&c<5かどうかということを判定すればOKということです。プログラムは最終的にはこうなりました。

#!ruby -apl
a,b,c=$F.map &:to_i
$_=a*a+b*b>117&&c<5||a+b>16?:NO:"YES"

これで69文字。他の言語も含めて1番短いコードを書くことができました。

(19:56)