AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

JOI難易度6 ダーツ

問題原文

atcoder.jp

問題要旨

 M を超えないように  N 個の整数  p_1, p_2, ... p_{N} の中から重複を許して 0個以上4個以下選ぶ時、その和とし取りうる最大値は何か?

  •   1 \leq N \leq 1000
  •   1 \leq M \leq 2×10^{8}
  •  1 \leq p_i \leq 10^{8}

解法

整数を2つ選んだ場合の和のリストをあらかじめ計算しておく。(これを  X とする。)
すると、 ある  x_i について、 M を超えないような最大の和を作るペアは、二分探索で求められる。
あらかじめ  P に0を追加しておけば、4個選ばない場合も考慮できる。

計算量は  O(N^{2}logN)。重複を許してくれてるのでうれしい。

実装

実行時間制限もメモリ制限も厳しいので、少し気にしながらやる。
たぶん 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点が取れてしまうので、いかに競プロ界のレベルが上がっているかがわかる気がします。