JOI2008本選C ダーツ

この記事で使うアルゴリズム

二分探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_c
https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=6

この問題は二分探索で解くことができます。

方針

まず全探索の計算量はO(N^4)なので、最悪のケースN=1000では間に合いません。

次に単純な二分探索について考えます。ダーツを3回投げたのち、最後の1回でどこに投げれば良いかを二分探索します。これは計算量がO((N^3)logN)なので、これでも最悪のケースN=1000では間に合いません。

より計算量を削減する方法としてダーツを2本ずつにまとめて考えます。二分探索をすると、計算量は、O((N^2)log(N^2))となります。(log(N^2)=2logNなので計算量はO((N^2)logN)とも表せます)

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import bisect
N, M = map(int, input().split())
P = [0]
for n in range(N):
P.append(int(input()))
P.sort()
S = []
for p1 in P:
for p2 in P:
S.append(p1+p2)
S.sort()
ans = 0
for s in S:
if M < s:
break
i = bisect.bisect(S, M-s)-1
ans = max(s+S[i], ans)
print (ans)

記事情報

  • 投稿日:2020年5月25日
  • 最終更新日:2020年5月25日