salvageon

結城浩さんのcodeIQの問題 https://codeiq.jp/ace/yuki_hiroshi/q1215

フィードバックをいただきました。両方正解でした。
Rを使っていた人は2名だけのようでしたが,ビッグデータの取り扱いは統計ツールを日常的に使う人にも関係は深いと思うので,もっとR使いがいてもいいのではないでしょうか。私はgmpというパッケージで超長整数を扱って計算しました。
DB1は単調増加とわかった段階で,微分方程式の数値解析のオイラー法みたいな計算をしましたが,解説ではバイナリサーチをしていました。この場合はオイラー法のほうがAPIをたたく回数は減ると思いますが…

解答集
http://togetter.com/li/758302

以下にanswer.txtをさらします。(画面からはみ出る部分に改行を追加)

V406435859539156181269150751031
V1101943557675920722238136981003
ENV: 最終的に「R」。途中経過で電卓,Excel, 少しだけpython
POINT: DB1はキーが単調増加。DB2はキーを100bitの2進数で表し
いちばん下の1の桁を上下反転させたものに残りの桁を加えたもの
の順に並んでいる。
(キーQを割り切れる最大の2のべき乗を2^k(k>=0)とした時,
2^(99-k)+(Q-2^k)/2^(k+1)がindexになる)

Rのソースと実行結果

  • -
#DB=1 library(gmp) db0 <- as.bigz(0) #小さいほう db1 <- pow.bigz(2,100) - as.bigz(1) #大きいほう target <- as.bigz("208050656559285601386927895421059705239114932023754") #クォーテーションマークでくくることが重要 VV <- "" k <- 0 urltext <- paste("http://salvageon.textfile.org/?db=1&index=", db0, sep="") dd <- read.table(file=url(urltext), header=F, sep=" ", colClasses = "character") #多倍長整数も文字列で取り込む ddl <- data.frame(dd) k <- k + 1 ky0 <- as.bigz(substr(dd[,3],2,100)) Sys.sleep(1.0) urltext <- paste("http://salvageon.textfile.org/?db=1&index=", db1, sep="") dd <- read.table(file=url(urltext), header=F, sep=" ", colClasses = "character") ddl <- rbind(ddl, dd) k <- k + 1 ky1 <- as.bigz(substr(dd[,3],2,100)) Sys.sleep(1.0) while (VV == "") { dbx <- as.bigz(sub.bigz(target,ky0)/sub.bigz(ky1,ky0)*as.bigq(sub.bigz(db1,db0))+_ as.bigq(db0)) #均一の増加率だと仮定して探し出すキーのインデックスをあたりをつける urltext <- paste("http://salvageon.textfile.org/?db=1&index=", dbx, sep="") dd <- read.table(file=url(urltext), header=F, sep=" ", colClasses = "character") ddl <- rbind(ddl, dd) k <- k + 1 kyx <- as.bigz(substr(dd[,3],2,100)) dbx Sys.sleep(1.0) if (sign(sub.bigz(kyx,target)) == 1) { db1 <- dbx ky1 <- kyx } else if (sign(sub.bigz(kyx,target)) == -1) { db0 <- dbx ky0 <- kyx } else { VV <- dd[,4] } }
  • -
> VV [1] "V406435859539156181269150751031" > ddl V1 V2 1 1 0 2 1 1267650600228229401496703205375 3 1 2565070352901388243030490 4 1 2565070352901388243030491 V3 1 K19584500653053662232211568267 2 K102818053067020370282264996429296647301172110315939147734 3 K208050656559285601386927806221480835207699089545741 4 K208050656559285601386927895421059705239114932023754 V4 V5 1 V830542486163201924733591581247 1267650600228229401496703205376 2 V764581954396429898637988092086 1267650600228229401496703205376 3 V400774553816906363998664980394 1267650600228229401496703205376 4 V406435859539156181269150751031 1267650600228229401496703205376
  • -
#最初の数個を見た限りでは単調増加とはいえkeyの階差数列はばらつきが 大きいようでしたが,はさみうちをするつもりで書いたwhile文ではわず か2回目で解にたどり着きました。 #多倍長整数の計算でうっかりnumericにしてしまうと32bitで丸められて しまって正しい数字にならないというバグを探すのにてこずりました。 targetをクォーテーションマークでくくっていなかったために変な数(bigz) になっていました。
  • -
> target <- as.bigz("208050656559285601386927895421059705239114932023754") > target Big Integer ('bigz') : [1] 208050656559285601386927895421059705239114932023754 > target <- as.bigz(208050656559285601386927895421059705239114932023754) > target Big Integer ('bigz') : [1] 208050656559285588701770946804922019477298484346880 >
  • -
  • -
#DB=2 db0 <- as.bigz(0) db1 <- pow.bigz(2,100) - as.bigz(1) target <- as.bigz("2023636070998557444542586045") VV <- "" urltext <- paste("http://salvageon.textfile.org/?db=2&index=", db0, sep="") dd<-read.table(file=url(urltext), header=F, sep=" ", colClasses = "character") ddl <- data.frame(dd) #規則性を発見する過程は略 for (i in 1:20) { dbx <- as.bigz(i) urltext <- paste("http://salvageon.textfile.org/?db=2&index=", dbx, sep="") dd<-read.table(file=url(urltext), header=F, sep=" ", colClasses = "character") ddl <- rbind(ddl,dd) Sys.sleep(1.0) } dbx <- add.bigz(pow.bigz(2,99),as.bigz(sub.bigz(target,as.bigz(1))/as.bigz(2))) urltext <- paste("http://salvageon.textfile.org/?db=2&index=", dbx, sep="") dd<-read.table(file=url(urltext), header=F, sep=" ", colClasses = "character") ddl <- rbind(ddl,dd) kyx <- as.bigz(substr(dd[,3],2,100)) VV <- dd[,4]
  • -
> VV [1] "V1101943557675920722238136981003" > ddl V1 V2 V3 1 2 0 K0 2 2 1 K633825300114114700748351602688 3 2 2 K316912650057057350374175801344 4 2 3 K950737950171172051122527404032 5 2 4 K158456325028528675187087900672 6 2 5 K475368975085586025561263702016 7 2 6 K792281625142643375935439503360 8 2 7 K1109194275199700726309615304704 9 2 8 K79228162514264337593543950336 10 2 9 K237684487542793012780631851008 11 2 10 K396140812571321687967719751680 12 2 11 K554597137599850363154807652352 13 2 12 K713053462628379038341895553024 14 2 13 K871509787656907713528983453696 15 2 14 K1029966112685436388716071354368 16 2 15 K1188422437713965063903159255040 17 2 16 K39614081257132168796771975168 18 2 17 K118842243771396506390315925504 19 2 18 K198070406285660843983859875840 20 2 19 K277298568799925181577403826176 21 2 20 K356526731314189519170947776512 22 2 634837118149613979470622895710 K2023636070998557444542586045 V4 V5 1 V866608106806207094188269706010 1267650600228229401496703205376 2 V179347330550907655201591936271 1267650600228229401496703205376 3 V967874566490056905763590096976 1267650600228229401496703205376 4 V21007428639505136878697302990 1267650600228229401496703205376 5 V499903880406975167914626368467 1267650600228229401496703205376 6 V137612525995897340648000428116 1267650600228229401496703205376 7 V1013924898829306772380170269614 1267650600228229401496703205376 8 V1252404645056427291182533085987 1267650600228229401496703205376 9 V520595999339570965993883078828 1267650600228229401496703205376 10 V1256891284967277336714134496424 1267650600228229401496703205376 11 V710302931554296640526866843240 1267650600228229401496703205376 12 V545375329928202174295039839589 1267650600228229401496703205376 13 V848644394970802704508212815012 1267650600228229401496703205376 14 V871991163218223896080356075737 1267650600228229401496703205376 15 V958747346069852079160957398348 1267650600228229401496703205376 16 V805754670819605302288978300850 1267650600228229401496703205376 17 V115917505363134018513900007273 1267650600228229401496703205376 18 V154823019080372587041596024019 1267650600228229401496703205376 19 V108729423996271630976080975567 1267650600228229401496703205376 20 V886213339588600673938994101775 1267650600228229401496703205376 21 V334205435694911673982823977556 1267650600228229401496703205376 22 V1101943557675920722238136981003 1267650600228229401496703205376
  • -
#最初の20個と最後の1個を見て,データの個数が2の100乗でindexとkeyが 重複しないことから2進数の100桁の数字の桁の入れ替えで作られている ようだとわかりました。

実はRで解く前にwindowsの電卓(超長整数を扱えるようだ)を使っていろいろ試していたのですが,DB2では2進数と10進数の変換に以下のサイトが役立ちました。
http://hogehoge.tk/tool/number.html
ありがとうございます。