筆者はレート800前後の茶～緑コーダ
ABC当日にACできなかった問題を解いていく
ABC321のD問題を解いていく
実装コード
主菜の価格を降順、副菜の価格を昇順にソートする。
この状態では、主菜 + 副菜の合計がある境界を超えた時点以降は、すべてセット価格 P が適用される。
そのため、各主菜に対して 副菜をどこまで通常価格で足せるか を 尺取法 によって求められる。
- なお、尺取法の代わりに 二分探索 を用いれば、主菜側をソートする必要はない
あとは、副菜の 累積和 をあらかじめ計算しておくことで、
各主菜を使った定食価格の総和を高速に算出できる。
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def main():
N, M, P = rLI()
A = rLI()
B = rLI()
A.sort(reverse=True)
B.sort()
Sb = [0] + list(accumulate(B))
# Sb = list(accumulate(B))
# err(A)
# err(B)
j = 0
ans = 0
# err(P)
for a in A:
while j < M and a+B[j] < P:
j += 1
# if IS_LOCAL:
# t = [a+b for b in B]
# t.insert(j,"|")
# err(*t)
# err(j,Sb[j] + a*(j) + P * (M-j))
ans += Sb[j] + a*(j) + P * (M-j)
print(ans)
if __name__ == '__main__':
main()
感想
二分探索／尺取法と累積和を組み合わせるという全体の構想までは立てられた。
一方で、各主菜を固定したときの定食価格の総和をどう数式として表現するか
という核心部分を自力で組み立てきれず、最終的に解説を参照する形になった。
アルゴリズムの選択自体は合っていたので、
今後は「条件分岐された和をどう分解して式に落とすか」を意識的に訓練していきたい。