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番短いコードを書くことができました。
コードゴルフは課題に対してとにかく短いコードを書けって感じの遊びです。
今回ちょっと頑張った問題は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)
