AtCoder / 二分探索で例外が処理しきれない

Question

#問題

AtCoder Beginner Contest 205 D問題 より

#今回参考にしている入力例

#方針
checkとliの1つのリストは、各Kの入力に対してそれに対応する今回の問題の答えが「check[i]より大きい時(iはそのような条件を満たす最小の値)、その答えの値からli[i]を引いたものがKである」と言う風に考え設定しました。例えば、「入力例1」で言うとK2にあたる5について言えば、それに対応する答えの9が「check[4] = 7より大きい時、その答えの値からli[4] = 4を引いたもの(=5)がKである」といった要領です。この方針ではAC×21, WA×2でほとんどのテストケースには正解しているのですが、ごく一部のケースで間違いであるようです。昨日行われたばかりのコンテストであるため、テストケース自体は未だ公開されておりません。

#ソースコード

from itertools import accumulate
from bisect import bisect_left

N, Q = map(int, input().split())
A = list(map(int, input().split()))

check = [0] + [a for a in A]
li = [0] + list(accumulate([1 for _ in range(len(check) - 1)]))
#[0, 3, 5, 6, 7]
#[0, 1, 2, 3, 4]

def find_ind(k):
    left = 1
    right = 10 ** 19
    while right - left > 1:
        mid = (left + right) // 2
        if mid - li[bisect_left(check, mid) - 1] <= k:
            left = mid
        else:
            right = mid
    return left
for _ in range(Q):
    K = int(input())
    print(find_ind(K))

#考えたこと・質問
何か見えない例外が発生し、本当の答えが実はleftではなくrightなのではないか？と言うことを考え、leftが条件式left - li[bisect_left(check, left) - 1] == kを満たさない場合はrightを代わりに出力するようにしても、やはり該当のテストケース2つでWAをくらったため、leftにもrightにも正解がないようなケースが発生していることがわかりました。どのような見落としが考えられるのでしょうか。自分で思いつくケースは色々と模索したものの一向に答えにたどり着く兆しが見えません。お力添え頂ける箇所がございましたら、ご教授のほど何卒よろしくお願い申し上げます。

Answer 1

例えば、この問題文のプログラムで以下の入力を実行すると明らかに間違った答えが出ます。

2 1
2 999999999999999999
1000000000000000000

期待する答えは 1000000000000000002になるはずですが、実行結果は 999999999999999999 になります。
これは意地悪な境界値ケースで発生します。テストケースにkillerとついていますが、おそらく「二分木探索での実装者を殺しに来る」意味合いなのかなと思います。問題文のミスリードを利用した引っ掛け問題です。

A,Nともに取りうる値は10^18までですが、数列Aの最大数が10^6あるため、答えとなりうる値が最大で10^10+10^6あることになります。このプログラムでは答えとして取りうる値の最大値をright側に入れて開始していますが、最大値が実際に取りうる最大値に足りていないので答えとして10^18以上の数値が来た場合にこれ以上の数が探索できずにleftにひたすらmidが加算されていきます。最終的にright未満の数値である10^18-1までしかleftが増加しません。

なので、対策としてはrightの初期値をもう少し増やしてあげれば良い、ということになります。最低10^18 + 10^6 + 1 あれば大丈夫だと思いますが、それより大きい値でも2倍程度なら処理速度に大差ありません。10^18*2くらいで開始すれば問題なくACが取れると思います。

なお、このコードをpypyではなくpythonで実行するとLTEだらけになります。処理速度をもっと向上させるアルゴリズムを考えるのも勉強になるかと思います。

Comments

[kay_ventris4]

ご教授頂いた通りrightの上限を大きめに取ったところ、全てACしました。
下限の検討はしていたのですが、答えの上限を検討するところを怠っておりました。
ご丁寧にありがとうございました。