JOI難易度6 ダーツ
問題原文
問題要旨
を超えないように 個の整数 の中から重複を許して 0個以上4個以下選ぶ時、その和とし取りうる最大値は何か?
解法
整数を2つ選んだ場合の和のリストをあらかじめ計算しておく。(これを とする。)
すると、 ある について、 を超えないような最大の和を作るペアは、二分探索で求められる。
あらかじめ に0を追加しておけば、4個選ばない場合も考慮できる。
計算量は 。重複を許してくれてるのでうれしい。
実装
実行時間制限もメモリ制限も厳しいので、少し気にしながらやる。
たぶん PyPyだとMLEするのでPythonで。
from bisect import bisect_left N, M = map(int, input().split()) P = [0] + [int(input()) for i in range(N)] X = set() for p1 in P: for p2 in P: if p1 + p2 < M: X.add(p1 + p2) X = list(X) X.sort() ans = 0 for x in X: i = max(0, bisect_left(X, M - x) - 1) tmp_ans = x + X[i] if tmp_ans > M: continue ans = max(ans, x + X[i]) print(ans)
感想
🐜本のおみくじですね。
ところでこれで当時の本戦Aランク条件38点のうち20点が取れてしまうので、いかに競プロ界のレベルが上がっているかがわかる気がします。