最近のあなごる問題

ビンラディンの件はびっくり。アメリカはしばらく厳戒態勢なんだろうな。９・１１みたいな報復がないことを祈っているが、株はちょっと売り払った。
さて、あなごるは、ここのところ問題が多い。まぁ、質の悪い問題も多いようだ。間違っているものは修正してほしいな。対応しないから、そんな問題にも解答がたまっていっている。

Outline

今までにないパターンの面白い問題だと思ったが、解答の方はすっきりいかず、面白い答えにはならなかった。最長の入力文字列を求めないとならないことから、どうしても、ロジックが２パスになってしまう。その辺がすきっりしない理由かな。

Big primes

Groovy で解いた。BigDecimal#modPow()を使えば、フェルマーの小定理による素数判定が簡単にできる。しかも、本問の場合、カーマイケル数とかも含まれてなく、単に、2g.modPow(p,p)==2 一発で判定できてしまう。出題者はその特殊な範囲を選んだのかな？

FRACTRAN fixed

なんだかよくわからない言語だが、Conway が示した素数を生成する FRACTRAN のプログラムはなんとも不思議だな、すべての素数が現れるのか。Conway に興味をもったので、Amazon で「素数が香り、形がきこえる」をオーダーした。ほんとは原書をほしかったのだけど、高い。４倍くらいする。なんで翻訳の方が安いんだろう。輸送費か。

How did youtube film you

なんだかすごいことになっていたけど、この元ネタはそれなりに面白かった。オリジナルの質問自体がネタなのかな？それとも、本気？ありえるな、アメリカだと。

私の出題。あまり人気なかった。残念。「エラストテネスのふるい」のような「ふるい(sieve)」ロジックだ。面白そうに思ったのだが。。。
C では、not さんが 101B でトップ。強い。しかし、配列の中身がインデックスであらわされる数に対するフラグなんだな。私の解では、配列の中身は、その求める数自体だ。そういうデータの持ち方、勉強になった。
ところで、この Lucky Number に対しても、ゴールドバッハ予想と同等のものが成り立つ(というか、これも予想なのか？)とか。おもしろいな。

Non Decreasing Digits

これも面白い問題だと思ったけど、人気はいまいちだったな。きちんと考えてはいないけど、答えをみると、55, 220 となっているので、その構造が簡単に想像つく。つまり、

55   : 10*11 / 1*2
220  : 10*11*12 / 1*2*3
715  : 10*11*12*13 / 1*2*3*4
2002 : 10*11*12*13*14 / 1*2*3*4*5

最近、この手の、階乗系の問題が結構多いな。

alphabet ranges

う〜ん、惨敗を喫した。でも、良問だな。

C

twobit さんの解。

i,j,a,c;
main(b){
    for(;~c;j-i&&putchar(i)){a=b;b=c;c=getchar();j=i;i=c-a==2?45:b;}
}

入力側３世代(a/b/c)、出力側２世代(i/j)でうまくストリーム処理している。見事。ただ、C はあまり経験ないのかな？さらに、3〜4B 縮みそう。

JavaScript

0mg さんの解。localeCompare() か。知らなかった。Groovy の "<=>" 演算子と同じか。いや、ちょっと違う。距離を返すようだ。

"a".localeCompare("b")       // ==> -1
"a".localeCompare("c")       // ==> -2
"abc".localeCompare("abf")   // ==> -3

MDN の Reference でもそうは書いていないな。-1 を返すと書いてある。ECMA-262 でも、そこまでは規定していない。Undocumented Behaviour だな。ちょっと関数名が長いけど、ほかの問題にも使えそうだ。

Arecibo message

ちょうど今読んでいる本(女王国の城：有栖川有栖さん)にもアレシボ天文台の話題が出てきた。偶然。
単純な問題だが、C がはまった。いい意味で。endless 問題だから、解答が出せないな。時間が経ったら公開しようか。そういえば、ほかの endless 問題の解答も公開してみようかな、そのうち。

Decomposition

私の出題。endless 問題として出した。なんか、この数の分解は面白そうだと思って、第一弾として出題した。本問は、実際には、入力の数を分解する必要はない。第二弾は実際に分解する必要のある問題を考えていたのだが、実際にやってみると結構な計算量が必要になることが分かった。たとえば、819 という数をこの方法で分解すると、最長の分解の仕方が、31,185 通りある(私の計算が間違っていなければ)。もっと良いロジックもあるのかもしれないが、試したところ、時間がかかりすぎ、タイムアウトを起こしやすかったのでやめた。
〜〜〜〜〜〜〜〜〜〜
現在アクティブな問題では、

nn_xの日記