競プロ初中級者100問

パ研杯2019 3C カラオケ

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

全探索

はじめに

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

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

問題

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c

この問題は全探索を用いて解くことができます。

方針

曲の組み合わせはM^2のオーダーで、生徒はN人なので全探索の計算量はO(NM^2)となります。これは、この問題の制約条件から考えて問題がない計算量です。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from itertools import combinations
N, M = map(int, input().split())
A = []
for n in range(N):
    a = list(map(int, input().split()))
    A.append(a)

ans = 0
for m1, m2 in combinations(range(M),2):
    score = 0
    for a in A:
        score += max(a[m1],a[m2])
    ans = max(ans, score)
print (ans)

記事情報

  • 投稿日：2020年5月15日
  • 最終更新日：2020年5月15日