[ABC272 Python]AtCoder Beginner Contest 272 A~C問題Python解説
ABC272の解説記事です。
質問・ミス等はコメントにてお願いいたします。
A問題
N = int(input())
A = list(map(int, input().split()))
print(sum(A))
いろいろ解き方が考えられますので、
解けた方も考えてみましょう。
N個の整数を全てリストAに入れます。
リストAの合計値を出力するためには
sum(A)で回答できます。
B問題
import itertools
N, M = map(int, input().split())
participant = []
for i in range(M):
kx = list(map(int, input().split()))
x = kx[1:]
participant.append(x)
people = [_ for _ in range(1, N+1)]
for i in itertools.combinations(people, 2):
i = list(i)
c = 0
for j in participant:
if i[0] in j and i[1] in j:
c += 1
if c == 0:
print("No")
exit()
print("Yes")
少し問題文の理解が難しいですね。
例として、3人の人(人1、人2、人3)がいるとすると、
①人1と人2が参加している舞踏会が存在する。
②人2と人3が参加している舞踏会が存在する。
③人3と人1が参加している舞踏会が存在する。
この①~③をすべて満たせばYes、
1つでも満たさないものがあればNo
と出力するという問題になります。
まずは、開催した舞踏会とそれに参加した人の名前を記録した
リストparticipantを作ります。
次に、2人の組み合わせを列挙したいので、
itertools.combinations()を使います。
itertoolsについては以下を参考にしてください。
全ての2人について、
1つでも2人とも参加した舞踏会があれば続けますが、
もしそのような舞踏会が存在しなければその時点でNoとなります。
全ての舞踏会に対して、2人とも参加しているかどうか確認し、
2人とも参加している舞踏会が1以上なら大丈夫という考え方をします。
C問題
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
odd = []
even = []
for i in A:
if i%2 == 0:
even.append(i)
else:
odd.append(i)
odd_len = len(odd)
even_len = len(even)
if odd_len<2 and even_len<2:
print(-1)
elif odd_len<2:
print(even[0]+even[1])
elif even_len<2:
print(odd[0]+odd[1])
else:
print(max(odd[0]+odd[1], even[0]+even[1]))
B問題で2種類の組み合わせの問題を扱いましたが、
この問題にも適用して、2要素の和をすべて列挙するとTLEになります。
計算量を工夫して減らさなければいけません。
2要素の和が偶数になるので、
それぞれの要素は、
「奇数+奇数」か
「偶数+偶数」の
2種類しか考えられません。
また、それぞれの最大値は
「奇数の最大値+奇数の2番目に大きい値」と
「偶数の最大値+偶数の2番目に大きい値」
のそれぞれ1種類ずつしか考えられないのです。
この2種類を比較して大きいほうが最大値となります。
では、スクリプトを見ていきましょう。
まずは、Aを大きい順に並べ替えます。
A.sort()では小さい順になるので、
reverse=Trueにして、逆順に並べます。
次に並べ替えたAを偶数と奇数に分けます。
分け方は2で割った余りが0なら偶数、それ以外は奇数です。
最後に最大値を求めます。
基本的には上記に示した、
「奇数の最大値+奇数の2番目に大きい値」と
「偶数の最大値+偶数の2番目に大きい値」
の大きいほうを出力するのですが、
何個かエラーが出るパターンがあるので、
条件を分岐しておきましょう。
どういうパターンがエラーになるかというと、
例えば偶数が1個しかなかった場合、
「偶数の2番目に大きい値」がないことになるので、
エラーとなります。
なので、奇数と偶数についてそれぞれ個数を確認して、
それぞれ値が0個ないし1個しかない場合は注意しなければなりません。
詳しくはスクリプトをご覧ください。
この記事が気に入ったらサポートをしてみませんか?