nashidos’s diary

アルゴリズムとか機械学習とか色々

トップ > 半分全列挙 > Pythonで半分全列挙を実装してみる-ABC184

Pythonで半分全列挙を実装してみる-ABC184

半分全列挙 二分探索 Atcoder

本記事では、半分全列挙をPythonで実装していきます。

実際に一緒に問題を解きながら半分全列挙を理解しましょう。

半分全列挙とは

半分全列挙は、その名の通りN個の要素を半分に分けてそれぞれを全列挙し、半分に分けたグループから組み合わせを考えることで高速に解を求める方法です。

具体的には以下のような流れになることが多いです。

  1. 半分のグループLを全列挙
  2. もう半分のグループRを全列挙
  3. Lから要素を1つ選び固定し、二分探索を用いて最適な組み合わせを探す（全ての要素に対して繰り返す）

それでは、実際に例題を解きながら理解していきましょう。


例題

今回は以下の問題を扱います。
atcoder.jp

問題文

高橋くんはプログラミングコンテストに参加します。 このコンテストのコンテスト時間は T 分間で、 N 問の問題が出題されます。高橋くんは超能力者なので、 i 番目の問題が A_i 分で解けることが分かっています。高橋くんは N 問の中から 0 問以上を、解くのにかかる時間の総和が T 分以下になるように選び、それらの問題を解きます。
選んだ問題を解くのにかかる時間の総和の最大値を求めてください。

制約

  • 入力は全て整数
  • 1≤N≤40
  • 1≤T≤10^9
  • 1≤A_i≤10^9

実装

選んだ問題を「解く」「解かない」の2パターンで考えることができるので全探索で答えを求めることはできます。

しかし、この例題における全探索の計算量はO(N^2)です。また、1≤N≤40なので、到底全探索では間に合いません。

そこで、半分だけ全列挙した場合の計算量を考えてみましょう。半分であれば最大でもN=20なので2^{20}≒10^6程度で計算することが可能です。

半分全列挙した前半のグループをL、後半のグループをRと呼ぶことにします。

半分に全列挙することができれば、あとは皆さんご存知の二分探索で解を求めることができます。

例えば、Lの要素であるL_iを固定した場合、「T-L_i>=R_iという条件を満たす最大のR_iを探す」という話になります。

Pの要素を固定して全探索するにはO(N^{N/2})かかり、二分探索にはO(log(2^{N/2}))かかるので、全体でO(N2^{N/2})でこの問題を解くことができます。

以下が実装例のコードです。

from bisect import bisect_right
 
N, T = map(int, input().split())
A = list(map(int, input().split()))
L = [0]
R = [0]
for x in A[:20]:
    for i in range(len(L)):
        L.append(x + L[i])
for x in A[20:]:
    for i in range(len(R)):
        R.append(x + R[i])
R.sort()

ans = 0
for x in L:
    if x > T:
        continue
    y = R[bisect_right(R, T - x) - 1]
    if ans < x + y:
        ans = x + y

print(ans)

参考元：https://atcoder.jp/contests/abc184/submissions/18300926

まとめ

半分全列挙はさほど難しいアルゴリズムではないですね。

正しく列挙し、二分探索を行うことができれば解ける問題でした。

Nの数が少ない場合などに半分全列挙の可能性を考えてみてもいいかもしれません。

おわり