• HOME
  • 競プロ
  • ブログ
  • 問い合わせ

文系独学プログラマーの仕訳帳

  • HOME
  • 競プロ
  • ブログ
  • 問い合わせ
  • HOME
  • 競プロ
  • ブログ
  • 問い合わせ
  1. HOME >
  2. Edit >

Edit

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

2022年1月24日

問題概要

問題ページ

[st-card-ex url="https://atcoder.jp/contests/zone2021/tasks/zone2021_c" target="_blank" rel="nofollow" label="" name="" bgcolor="" color="" readmore="問題ページへ移動する"]

ストーリー

さて、本格的に 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()

プログラミング

  • TwitterTwitter
  • Share Share
  • PocketPocket
  • Hatena Hatena
  • LINE
  • URLコピー

-Edit
-二分探索, BitDP, ABC-Like-C

author

関連記事

no image
【pythonでABC177を解説】A - Don't be late
no image
【pythonでABC199を解説】A - Square Inequality
no image
【初心者向け】レッドローチの飼育環境の作り方
no image
【pythonでABC208を解説】C - Fair Candy Distribution
no image
【pythonでABC168を解説】B - ... (Triple Dots)
no image
【pythonでABC095を解説】D - Static Sushi
no image
【pythonでABC167を解説】B - Easy Linear Programming

【pythonでZONE2021を解説】B - Sign of Friendship

【pythonでZONE2021を解説】D - Message from Aliens

  • 管理人

たびすけ

東証1部上場企業の社畜
プログラミングとブログが趣味
勉強好きの怠け者
プログラミングを独学

サイト内検索

カテゴリ

最近のつぶやき

Tweets by XXXHOLiC_xxx
  • ブログ
  • プログラミング
    • python
    • Excel
    • データベース
  • 競技プログラミング
    • AtCoder Beginner Contest
  • カナヘビ
  • 雑記
  • Edit

タグ

ABC-A (68) ABC-B (55) ABC-C (43) ABC-D (37) ABC-E (21) ABC-F (11) ABC-Like-A (1) ABC-Like-B (1) ABC-Like-C (1) ABC-Like-D (1) BitDP (2) deque (3) DP (1) heapq (1) imos法 (1) n進数 (1) Union Find (3) Zアルゴリズム (1) セグメントツリー (2) ダイクストラ法 (1) トポロジカル (1) メモ化再帰 (3) レッドローチ (1) ワーシャルフロイド (1) 二分探索 (2) 幅優先探索 (2) 深さ優先探索 (1) 素数 (1) 組み合わせ (3) 論理演算 (4)
  • HOME
  • 競プロ
  • ブログ
  • 問い合わせ

文系独学プログラマーの仕訳帳

© 2023 文系独学プログラマーの仕訳帳