[ABC313 A~D Python]第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）
A問題
# 入力N,P
N = int(input())
P = list(map(int, input().split()))
# 人1が最強かつ他にも最強な人がいる場合
if P.count(P[0]) >= 2 and P[0] == max(P):
print(1)
# 人1のみが最強かつ他に最強な人がいない場合
elif P[0] == max(P):
print(0)
# その他の場合
else:
print(max(P)-P[0]+1)パターンとしては3パターンです。
①人1は最強で、他にも最強がいる
②人1は最強で、他に最強はいない
③人1は最強ではない
パターンごとにそれぞれプログラミング力を上げていけば、
答えを導くことができます。
B問題
# 入力N,M
N, M = map(int, input().split())
# 強弱の関係
# relationship[i][j] = -1 → iはjより弱い
# relationship[i][j] = 0 → iとjの関係はわからない
# relationship[i][j] = 1 → iはjより強い
relationship = [[0]*N for _ in range(N)]
# 全ての情報について
for i in range(M):
# 入力A,B
A, B = map(int, input().split())
A -= 1
B -= 1
# AはBより強い
relationship[A][B] = 1
# BはAより弱い
relationship[B][A] = -1
# 最強プログラマーの候補
ans = []
# N人全員について
for i in range(N):
# 人iが最強である可能性
judge = True
# 他の人全員について
for j in range(N):
# iがjより弱かったら、
if relationship[i][j] == -1:
# 最強の可能性がなくなる
judge = False
break
# 最強の可能性があるなら
if judge:
# 候補に追加する
ans.append(i+1)
# 候補が2人以上いるなら、
# 特定できないので、-1を出力する
if len(ans) >= 2:
print(-1)
# 候補が一人なら、その人が最強プログラマー
else:
print(ans[0])
情報が一部しか分かっていないので、
プログラムが特定できない場合があります。
ですので、分かっていない勝敗に関してはそのままにして、
全ての人に対して、最強プログラマーになることができるかどうか確認します。
最強プログラマーになる可能性があるのは、
「情報から誰にも負けていないことが分かる人」
です。
C問題
# 入力N,A
N = int(input())
A = list(map(int, input().split()))
# Aを順番に並べ替える
A.sort()
# Aの合計
sumA = sum(A)
# 操作後の数列B
B = [sumA//N for _ in range(N)]
# 余りを順に数列に加える
for i in range(sumA%N):
B[i] += 1
# Bを順番に並べ替える
B.sort()
# 操作回数
ans = 0
for i in range(N):
# 操作前から操作後に操作するのに何回必要か
ans += abs(A[i]-B[i])
# 操作は1回で2回分できるので、
# 2で割る
print(ans//2) 操作後の整数列をBとします。
操作は何回でもできますが、
Aiを+1、Ajを-1するので、数列の合計は変わりません。
つまり、sum(A)=sum(B)となります。
sum(A)=sum(B)とBの最大値-B最小値=1という条件から、
Aの平均値と平均値+1から数列Bを作ることができます。
必要回数はA[i]とB[i]の差から求めることができます。
D問題
後日記載します。