長さ20万の数列が二つ与えられる(A,B)。Aの先頭i個とBの先頭j個を足した時に、与えられた数Kを超えないような、最大のi+jを答えよ、という問題。
コンテスト中の思考
- 問題文では「数列の先頭から一つずつ取り…」と書いてあるが、小さい方を取ればOKか？
- 反例が見つかった
- 6以下であることが求められてるとして、正解は3,1,1,1で6にすることなのに、先に2を取ってしまうと2,3,1になってしまう。これは最適解ではない。
- 反例が見つかった
- 取る順番は関係ない
- Aを取ってからBを取っても、その逆でも、やる計算は「足し合わせ」なので同じ値になる
- 問題文の順にやらない
- i+jが小さい方から順にチェックしよう
コンテスト後
- 上のやり方でダメな理由
- 数列が全部1で、Kが50万だとすると、正方形を全部チェックすることになる
- これには400億回の比較が必要
正解のやり方
- 右上隅から初める
- NGであるなら右に進む
- Kを超えててもっと減らす必要があるから
- OKなら下に進む
- そこより右はOKだが、i+jが小さいからチェックする意味がない
- 右端からやる必要はない
- NGの下はNGだから(既に超えてるなら、増やしても超えてる)
- 多くてもN+M回の比較で各行で一番右にあるOKマスを確実に踏むことができる
python
def solve(N, M, K, sA, sB):
max_can_read = 0
last_max_j = M
for i in range(N + 1):
j = last_max_j
while j >= 0:
if sA[i] + sB[j] <= K:
if max_can_read < i + j:
max_can_read = i + j
last_max_j = j
break
j -= 1
print(max_can_read)