サルベジオン社で宇宙船のデータを救え

問題

[サルベジオン社で宇宙船のデータを救え]

回答

V406435859539156181269150751031

V1101943557675920722238136981003

ENV: Perl

POINT: db 1 は key が単調増加していること、db 2 は key と index の関係を調べて解きました

db1

先頭から 5 件をとりだしてみると

1 0 K19584500653053662232211568267 V830542486163201924733591581247 1267650600228229401496703205376

1 1 K19623607256232418445590556076 V1151579720490916693165541876145 1267650600228229401496703205376

1 2 K19718984353819469994289486141 V803371842571480223738576246215 1267650600228229401496703205376

1 3 K19781945725870318832662826826 V314778970077814367350137878130 1267650600228229401496703205376

1 4 K19854960460600482668081543475 V526182689909684857174556484180 1267650600228229401496703205376

1 5 K19919585540538830893087306729 V1159567921864854161141993697539 1267650600228229401496703205376

となっており、データベースのサイズは 1267650600228229401496703205376 = 2^100 であることがわかりました。

また、key が単調増加しているように思われました。

そのため、引き続き 100 件取り出したところ、やはり徐々に増加していました。

ということで、全体で key が単調増加していると仮定し、二分探索で目的の key を探すことにしました。

[db1.pl]

98回の試行で、めでたく問題の

K208050656559285601386927895421059705239114932023754

に対応する value

V406435859539156181269150751031

を発見することができました。

db2

同じように先頭から 5 件を取り出してみたところ

2 0 K0 V866608106806207094188269706010 1267650600228229401496703205376

2 1 K633825300114114700748351602688 V179347330550907655201591936271 1267650600228229401496703205376

2 2 K316912650057057350374175801344 V967874566490056905763590096976 1267650600228229401496703205376

2 3 K950737950171172051122527404032 V21007428639505136878697302990 1267650600228229401496703205376

2 4 K158456325028528675187087900672 V499903880406975167914626368467 1267650600228229401496703205376

という結果で、こちらは key の増減があり、単調増加ではなさそうでした。

引き続き 100 件取り出してみたところ、ほとんどの箇所では増加しているものの、

一部減少しているところがあることがわかりました。一つ前の index の key と

比較して key が減少しているところだけを取り出すと、

2 1 K633825300114114700748351602688 V179347330550907655201591936271 1267650600228229401496703205376

2 2 K316912650057057350374175801344 V967874566490056905763590096976 1267650600228229401496703205376

2 4 K158456325028528675187087900672 V499903880406975167914626368467 1267650600228229401496703205376

2 8 K79228162514264337593543950336 V520595999339570965993883078828 1267650600228229401496703205376

2 16 K39614081257132168796771975168 V115917505363134018513900007273 1267650600228229401496703205376

2 32 K19807040628566084398385987584 V122797100145332764131814244111 1267650600228229401496703205376

2 64 K9903520314283042199192993792 V977867368495222217606468785532 1267650600228229401496703205376

と、index が 2^n のところで減少しているようであることがわかりました。

さらに、key になっている値を素因数分解してみると、

index 1 の key は 2^99

index 2 の key は 2^98

index 4 の key は 2^97

index 8 の key は 2^96

index 16 の key は 2^95

index 32 の key は 2^94

index 64 の key は 2^93

となっていることがわかりました。

また、その間のものについても、

index 3 の key は 3 * 2^98

index 5 の key は 3 * 2^97

index 7 の key は 5 * 2^97

index 9 の key は 3 * 2^96

index 10 の key は 5 * 2^96

index 11 の key は 7 * 2^96

index 12 の key は 9 * 2^96

index 13 の key は 11 * 2^96

となっていました。

最後の index 2^100-1 は

2 1267650600228229401496703205375 K1267650600228229401496703205375 V223306160806266923362780715474 1267650600228229401496703205376

で、この key は 2^100-1 です。

そして、index 2^99 は

2 633825300114114700748351602688 K1 V330246403271289337606844181441 1267650600228229401496703205376

で、key は 1 です。

これらのことから、key k * 2^n (k は奇数、n は 0 以上の整数) に対応する index は

2^(99-n) + (k-1)/2 となっているのではないかと推測しました。

実際に上記に適用してみると、その予想は正しそうでした。

問題の key 2023636070998557444542586045 は 2 では割れないので、k * 2^n にあてはめると、k=2023636070998557444542586045, n=0

2^(99-0) + (2023636070998557444542586045-1)/2 = 634837118149613979470622895710

http://www.wolframalpha.com/input/?i=2^%2899-0%29+%2B+%282023636070998557444542586045-1%29%2F2

なので、おそらく index 634837118149613979470622895710 の value が求める値だろう

[getdb.sh]

$ sh getdb.sh 2 634837118149613979470622895710

2 634837118149613979470622895710 K2023636070998557444542586045 V1101943557675920722238136981003 1267650600228229401496703205376

予想どおり、求めたい key を発見。

問題の

K2023636070998557444542586045

に対する value は

V1101943557675920722238136981003

になりました。

はまったこと

• db1 では、二分探索が使えそうというところはすぐに気がついたのだが、「min と max の中間」を求めるのになぜか (max - min) / 2 を計算してしまい、時間を浪費した。言うまでもなく、中間は (max + min) / 2 である。
• db2 は、最初の方のキーを素因数分解して法則を見つけた。とくにはまりどころはなかったかな。

感想

いつもは回答ができても「本当にこれであっているのだろうか...」と不安が残るものですが、今回は key と value を見つけてしまえば ok なので安心感はありました。が、ちょっと物足りない気も。