競プロ初中級者100問

ALDS1 5A 総当たり

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

全探索

はじめに

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

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

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja

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

方針

nの最大値は20なので、計算量がO(2^n)であるビット全探索でも十分間に合います。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from itertools import product
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

create = [0] * 40001

for p in product([0,1], repeat=n):
    sm = 0
    for i in range(n):
        if p[i]==1:
            sm += A[i]
    create[sm] = 1

for m in M:
    if create[m]:
        print('yes')
    else:
        print ('no')

記事情報

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