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;する必要があります。
今回の問題は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)
