[Home]Memo/Q1215

Amatubu_Wiki | Memo | RecentChanges | Preferences

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

問題

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

回答

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
になりました。

はまったこと

感想

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

Amatubu_Wiki | Memo | RecentChanges | Preferences
This page is read-only | View other revisions
Last edited December 16, 2014 15:26 by Amatubu (diff)
Search:

Copyright (c) 1996-2006 naoki iimura e-mail