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)Related Pages
- →アルゴリズム×蟻本×区間スケジューリング×二分探索木×unionfind×最短路問題×最小全域木×ユークリッドの互除法×ニ分探索×しゃくとり法×半分全列挙×座標圧縮×セグメント木×binary_lndexed_tree×バケット法×平方分割×ビットdp×bitdp×行列累乗×繰り返し二乗法×最大流×最小カット×二部マッチング×一般マッチング×マッチング×辺カバー×安定集合×点カバー×最小費用流×凸包×grundy数×強連結成分分解×2-sat×lca×ダブリング×接尾辞配列×sparse_table×rmq×atcoder→
- →アルゴリズム実技検定×atcoder×past3×past202005×past3d×past3e×past3f×past3g×past3h×past3i×past3j×past3k×past3l×past3m×past3n×past3o→
- →atcoder×atcoder_library_practice_contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×lcp_array×pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×unionfind×最大流×最小費用流×scc×2-sat→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]