【pythonでZONE2021を解説】C - MAD TEAM

問題概要

問題ページ

C - MAD TEAM

問題ページへ移動する

ストーリー

さて、本格的に UFO と対峙する仲間を集めることにしよう。それも、とびきり MAD で優秀な。
俺は数多の天才たちと競い合ってきた「AtCoder」上でメンバーを集めることにした。
名の知れたプログラマに片っ端から声をかけてもいいが、どうせなら得意分野のバランスが良い少数精鋭で最高なチームを作るとしよう。

問題文

\(N\) 人のメンバー候補がおり、それぞれの人は、パワー・スピード・テクニック・知識・発想力の \(5\) 種類の能力値を持っています。
\(i\) 番目の人のパワーは \(A_i\) 、スピードは \(B_i\) 、テクニックは \(C_i\) 、知識は \(D_i\) 、発想力は \(E_i\) です。
あなたは、\(N\) 人のメンバー候補から \(3\) 人を選び、\(1\) つのチームを作ります。
チーム全体のパワーをチームメンバーのパワーの最大値で定義します。スピード・テクニック・知識・発想力についても同様に定義します。
チームの総合力を、チーム全体のパワー・スピード・テクニック・知識・発想力の最小値で定義します。
チームの総合力としてありえる最大値を求めてください。

制約

• 入力は全て整数
• \(3 ≤ N ≤ 3000\)
• \(1 ≤ A_i, B_i, C_i, D_i, E_i ≤ 10^9\)

問題の考察

ACコード

import sys
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    abcde = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    cor_v = -1
    inc_v = 10 ** 10
    while - cor_v + inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = False
        bt_ls = [[False] * pow(2, 5) for _ in range(4)]
        bt_ls[0][0] = True
        #条件を満たすcostを全検索
        for i in range(len(abcde)):
            bt = 0
            for j in range(5):
                if abcde[i][j] >= bin_v:
                    bt += pow(2, j)
            for j in range(3, 0, -1):
                for k in range(pow(2, 5)):
                    p = k | bt
                    bt_ls[j][p] = bt_ls[j][p] | bt_ls[j-1][k]
        #costが制約を満たすか
        if bt_ls[-1][-1]:
            cor_v = bin_v
        else:
            inc_v = bin_v
    print(cor_v)


if __name__ == '__main__':
    solve()