2015年03月20日

【Java】フィーバー・ナンバー問題とか

CodeIQさんでフィーバー・ナンバー問題というのが出ました。

どういう問題かというと、平方根取って小数点がゾロ目の数字を求めてね(はぁと
という問題で、出題されたのは下6桁がゾロ目となる最小の数字でした。

平方根をx.aaaaaa...と表すと、元の数字は
x.aaaaaa*x.aaaaaa+α
なので、これを展開して
=xx+0.222222xa+0.012345654321aa+α
となります。
αは無視できるほど小さく、aも0〜9の数字のため、0.012345654321aaも無視できるほど小さい数字になります。
また、0.222222xaは最大でも1.999998xです。

そのため、求める数はxx〜x(x+2)=xx+2xの範囲にあることが明白です。

ちなみにaの数がnであっても、大筋は変わらず、xx+0.(2がn個)xa+αとなりますので、検索範囲はxx+2xです。

問題のほうに4つ並ぶのは5168だよーという記述があるので、√5168=71.8888...よりも大きい数字から探して

を実行すると√48273160=6947.888888...ということがわかりますb
ところで、ちゃんと検証してませんけど、nが3以上のとき、aは常に8なんじゃないかと思います。
posted by バー at 10:13| Comment(0) | TrackBack(0) | CodeIQ | このブログの読者になる | 更新情報をチェックする

2015年03月06日

【ですころ10】Javaゴルフ講座とか

9回は特に書くことなかったので飛ばしましたけど、10回目のデスコロ

またもやJavaで最短ですよ!
今回は
treetreetreefiregoldtreetreetreetreegoldtreegoldtreegoldtreegoldtreegoldtreetreegoldtreegoldtreetreetr
eegoldtreetreetreewaterwatertreetreewatergoldgoldtreegoldtreegoldtreegoldtreegoldtreetreegoldtreeg
oldtreetreetreegoldtreetreefiregoldgoldwatermoontreemoontreegoldgoldtreewatergoldgoldtreetreegold
goldtreetreemoonwatergoldgoldwatergoldtreetreemoongoldgoldmoon

という文字列を出力しろ、というのが課題です。
さて、この文字列はtree,fire,gold,moon,waterという5つの文字で出来ています。
月に代わっておしおきですね!
これを数字に当てみると0001200002020202020020200020004400422020202020020200020012243030220422002200342242003223みたいな数列になります。
この数列は5進数なので、これをn進数に圧縮して/=5しつつ%5で値を取れば答えが求まります。
ところで、Javaで扱えるn進数は最大幾つかご存知でしょうか。
16までと思う人は甘いです。なんと無駄に36進数なのです!
上の数字を逆順に(reverse)して36進変換すると4k8orvt45xfetts7f5f7w9flurp2bmks14vsoi6rと、強烈に圧縮されます。
では36進数変換した文字列を使って回答してみましょう。

この[]xはArrays.toListに変えて

とすると、若干短くなりますが、永杉さんです。ていうか、BigIntegerが長すぎるのですよ!
もう余計な処理は辞めてシンプルに書きましょう!

あら短い。

これを基準に、この長い数字列を圧縮することを考えます。
この数字を全角文字コードに直し、ビット演算で0〜4の数字化すれば圧縮できるはずです。
Javaで使用される文字コードはUTF-8。UTF-8の全角文字は通常3バイトです。
UTF-8で3バイト全角文字はE2****〜E6****にありますので、ちょうど5種類ですが、問題はE2系。これってрニか→とかLあたりが扱われているのですが、ほぼ全部CodeIQですと「機種依存文字」として弾かれます。
そのため、E2系は実質使えません。
また実際にはサロゲートペアという拡張文字があって、これを使うと4バイトになりますが、扱える文字数が少なくて使いづらい上に、機種依存文字の可能性が高く、怖くて使えません。

そこで、文字として出現率の低いfireを1バイト文字(つまり半角ASCII文字)で表すことにして、E3〜E6系だけを使いました。
もともとの数字を3バイトあるいは1バイトに切ったとき、最短となるのは(0〜4をa〜eと置き換えて)
aaa,b,caa,aac,aca,cac,aca,aca,caa,aca,aae,eaa,ecc,aca,cac,aca
,aca,caa,aca,abc,ced,ada,cca,ecc,aac,caa,dec,cec,aad,ccd
と分割した時です。
そして、これ上手い具合にdで始まるのがdecしかないので、あえて
aaa,b,caa,aac,aca,cac,aca,aca,caa,aca,aae,eaa,ecc,aca,cac,aca
,aca,caa,aca,abc,ced,ada,cca,ecc,aac,caa,d,ecc,eca,adc,cd
と分割し、dも先頭から外してしまいます。これでも後述の理由により文字数は変わりません。
あとはUTF-8文字コード表とにらめっこしながら、&7で2〜6になるような文字列を作り上げ、-2を引いてあげれば0〜4の数字に戻せます。
実際の文字列は
伜C億伽佼包佼佼億佼伶挌捕佼包佼佼億佼仕冊交兄捕伽億B捕杜井備
となります。
この中で重要なのは最後の「備」。こいつは0xE58299なので、バイトごとに&7かけると5,2,1となります。最後の1文字が2〜6ではありませんので、-2すると-1となってしまいます。
これぞデスマ名物Exception抜けです。デスマコロシアムではExceptionが出ても無視されることになっているため、ArrayOutOfBoundsExceptionを起こして終了させて構わないのです。このテクニックを使って、元の数字の3を使わないようにしたほうが、全角文字を当てるときに便利というわけ。
こうして出来たのが

この-2を先頭に持っていくと

で、1文字だけ減ります。
しかし、これ以上縮まりません。
たとえば順序を工夫して~i&7で処理することで文字列を縮めようとしても、2〜6→5〜1となってしまい、ノイズ除去の""を入れて

とすると、かえって長くなってしまいます。

Javaで最短に挑戦した人はたぶんこのあたりで投了しているはずです。
バーも投了しかけました。

たとえばListではなく配列にすれば.get()ではなく[]が使えて文字が削れますが、Javaで変数代入なしで配列作るにはnew String[]{,,,}という書式になります。

長い、長いよママン。
もはや諦めるしかと思ったとき、突然閃きました。
CSVファイルを処理する場合、Javaで使うメソッドがあるじゃないの!
String.split()!
new String[]{"","water","gold","tree","fire","moon"}

",water,gold,tree,fire,moon".split(",")
と等価!
これで一気に縮まり

という最短解が求まりました。

やったー!


続きを読む
posted by バー at 09:22| Comment(0) | TrackBack(0) | CodeIQ | このブログの読者になる | 更新情報をチェックする
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。