CodeIQ サルベジオン問題

CodeIQで結城先生が出題されているということで、久しぶりに挑戦してみました。せっかくブログを始めたので、その解答を晒しておきたいと思います。

【問題】

今回の問題、サルベジオン問題は、データベースからWebAPIを用いてあるキーに対応するバリューを取得するというものです。ただし、厄介なことにデータベースが故障しているため、キーを入力してバリューを得るということができません。その代わりに、データのインデクスを入力することで、そのインデクスに対応するキーとバリューのペアを得ることができます。この条件で、あるキーに対応するバリューを取得せよというのが問題です。

なおデータベースはdb1とdb2の2つがあり、それぞれ1つのキーに対応するバリューを求めます。また、データベースへのアクセスは1秒に1回だけという制限があります。

【解法】

db1は最初の100個ぐらいを出力してみて、キーが単調増加っぽいなーと思ったので、とりあえず二分探索してみると、目的のキーのインデクスを求めることができました。

db2も最初の100個ぐらいを出力してみて、キーの規則性を探しました。ここで、データの個数が $2^{100}$ に等しいということがわかりました。なんとなく眺めていると、いくつか単調増加したあとに小さくなり、また単調増加して、というのが繰り返されているように見え、また単調増加の長さがだんだんと長くなっているということに気が付きました。

そこで、単調増加の始点のインデクスを見てみると、すべて2のべき乗だったので、2のべき乗ごとに何らかの規則で単調増加しているのだろうと思いました。そこから、差分をとったり、インデクスが2のべき乗のキーを眺めてみたり、なんやかんやすると、

${ \displaystyle K(2^{n} + m) = \frac{(2m+1)K(1)}{2^{n}},\ n \geq 0, \ 0 \leq m \lt 2^{n} }$

という規則があることに気が付きました。ここで $K(x)$ はインデクスが $x$ であるキーを表します。よってインデクスを求めたいキーを $k$ とすると、
${ \displaystyle \frac{(2m+1)K(1)}{2^{n}} = k }$

を満たす $(n, m)$ を見つければ良いことになります。なので私は $n$ を0から100まで動かした時の $\displaystyle{m}$ を上の式から求め、インデクスが $\displaystyle{2^{n}+m}$ のデータをひとつひとつ調べました。

以下がそのコード(Python)です。コード中では上で出てきた $\displaystyle{K(1)}$ をN、 $\displaystyle{k}$ をKとしています。

db1

import urllib2
import time

def getData(db, index):
    response = urllib2.urlopen('http://salvageon.textfile.org/?db=%d&index=%d' % (db, index))
    list = response.read().split(' ')
    key = int(list[2].translate(None, 'K'))
    value = int(list[3].translate(None, 'V'))
    return [key, value]

K = 208050656559285601386927895421059705239114932023754
lb = 0
ub = 1267650600228229401496703205376

while ub - lb > 1:
    mid = (ub + lb) / 2
    print '%d, %d' % (lb, ub)
    data = getData(1, mid)
    if data[0] == K:
        print "index:%d, value:%d" % (mid, data[1])
        break
    if data[0] > K:
        ub = mid
    if data[0] < K:
        lb = mid
    time.sleep(1)

db2

import urllib2
import time

def getData(db, index):
    response = urllib2.urlopen('http://salvageon.textfile.org/?db=%d&index=%d' % (db, index))
    list = response.read().split(' ')
    key = int(list[2].translate(None, 'K'))
    value = int(list[3].translate(None, 'V'))
    return [key, value]

N = 633825300114114700748351602688
K = 2023636070998557444542586045

for n in range(101):
    m = ((2**n * K) / N - 1) / 2
    if m < 0 or m >= 2**n:
        continue
    index = 2**n + m
    data = getData(2, index)
    print "%d, %d, %d" % (n, m, index)
    if data[0] == K:
        print "index:%d, value:%d" % (index, data[1])
        break
    time.sleep(1)