ABC172C

NISHIO Hirokazu [Translate]

ABC172C
長さ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マスを確実に踏むことができる

pythondef 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)
AC https://atcoder.jp/contests/abc172/submissions/14782042

atcoder