F - Programming Contest
皆さん、こんにちは！
ハリーです。今回は競プロを始めて以来、精進で初めて F 問題を解くことができたので解説記事を書いていこうと思います。
それでは解いていきましょう！
F - Programming Contest
問題文
高橋くんはプログラミングコンテストに参加します。 このコンテストのコンテスト時間は $T$ 分間で、 $N$ 問の問題が出題されます。
高橋くんは超能力者なので、$ i $ 番目の問題が$ A_i$ 分で解けることが分かっています。
高橋くんは $N$ 問の中から $0$ 問以上を、解くのにかかる時間の総和が $T$ 分以下になるように選び、それらの問題を解きます。
選んだ問題を解くのにかかる時間の総和の最大値を求めてください。
制約
- 入力は全て整数
- $1 \leq N \leq 40$
- $1 \leq T \leq 10^9$
- $1 \leq A_i \leq 10^9$
入力例１
5 17 2 3 5 7 11
出力例１
17
入力例２
6 100 1 2 7 5 8 10
出力例２
33
入力例３
6 100 101 102 103 104 105 106
出力例３
0
入力例４
7 273599681 6706927 91566569 89131517 71069699 75200339 98298649 92857057
出力例４
273555143
実装方法
まず、この問題を実装するにあたって、使用するアルゴリズムは「半分全列挙」と「二分探索」、「bit 全探索」です。そして、bisect というPythonのモジュールを使用します。
半分全列挙
今回の問題を普通に bit 全探索すると計算量が $O(2^N)$ もかかってしまいます。すると、最大の計算量は $2^40$ もかかってしまいます。この計算量を抑えるために半分全列挙を使います。
まず、配列を半分に分けます。そして、分けた配列それぞれを全探索すると計算量は $O(2 × 2^N/2)$ まで抑えることができます。
これが半分全列挙のおおまかな概要です。
参考サイト
それぞれのアルゴリズムと bisect について詳細に解説している、私が参考にしたサイトは以下の 3 つです。
Pythonでの実装
まず初めに、bisect モジュールをインポートします。
import bisect
入力を受け取ります。
N, T = map(int,input().split())
A = list(map(int,input().split()))
配列 A を半分に分けます。
A1 = A[:20]
A2 = A[20:]
次に、分けた配列をそれぞれ bit 全探索していきます。
sum = [0]
for i in range(2 ** len(A1)):
total = 0
for j in range(len(A1)):
if (i >> j) & 1:
total += A1[j]
sum.append(total)
sum2 = [0]
for i in range(2 ** len(A2)):
total = 0
for j in range(len(A2)):
if (i >> j) & 1:
total += A2[j]
sum2.append(total)
bit 全探索で求めたそれぞれの配列の和のリストを昇順にソートします。
sum.sort()
sum2.sort()
最後に二分探索を行い、条件を満たす最大値を探します。
二分探索を行うとき、片方のリストの要素を固定して行います。今回は前半の 20 個の和を保存している配列 sum を固定して探索を行います。そして、最大値を更新していき、最後に出力すれば終わりです。
ans = 0
for i in sum:
if T - i >= 0:
ans = max(ans, i + sum2[bisect.bisect_right(sum2, T - i)-1])
print(ans)
ACコード
import bisect
N, T = map(int,input().split())
A = list(map(int,input().split()))
A1 = A[:20]
A2 = A[20:]
sum = [0]
for i in range(2 ** len(A1)):
total = 0
for j in range(len(A1)):
if (i >> j) & 1:
total += A1[j]
sum.append(total)
sum2 = [0]
for i in range(2 ** len(A2)):
total = 0
for j in range(len(A2)):
if (i >> j) & 1:
total += A2[j]
sum2.append(total)
sum.sort()
sum2.sort()
ans = 0
for i in sum:
if T - i >= 0:
ans = max(ans, i + sum2[bisect.bisect_right(sum2, T - i)-1])
print(ans)
おわりに
いかがだったでしょうか？今回は初 F 問題 AC できたので、興奮してすぐに記事を書いてしまいました！半分全列挙を用いた問題だったのですが、個人的にはとても面白かったです。灰コーダーの私でも解くことができたので、是非皆さんも解いてみてはいかがでしょうか？
それではまた！
