サルベジオン社で宇宙船のデータを救え
問題
- [サルベジオン社で宇宙船のデータを救え]
回答
- 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 なので安心感はありました。が、ちょっと物足りない気も。