Home / Python /

第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）をPythonで解く

投稿日：　 更新日：2023/10/17

Atcoder Python

B!
Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, Shinoryoです.

今回は第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）を, Pythonで解いてみた結果を書き連ねていこうと思います.

AtCoder Beginner Contest 313 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

目次[非表示]

A - To Be Saikyo

1人のみの場合と2人以上の場合で分けて考えると, 分かりやすいです.

# 入力
N = int(input())
P = list(map(int, input().split()))
# 1人の場合
if N < 2:
print(0)
exit()
# 2人以上の場合
max_power = max(P[1:])
if P[0] > max_power:
print(0)
else:
print(max_power - P[0] + 1)
view raw atcoder-abc-313-a.py hosted with ❤ by GitHub

B - Who is Saikyo?

ある人Xが最強であるための必要条件は, Xより誰かが強いという情報がないことです. したがって, 強さに関する情報を用いて弱い人を脱落させていって, 残った人数が1人かどうかで出力を分岐させればよいです.

# 入力
N, M = map(int, input().split())
# メンバーのリストから弱い人を消していく
remaining = set(range(1, N + 1))
for _ in range(M):
_, B = map(int, input().split())
remaining.discard(B)
# 出力
if len(remaining) == 1:
print(remaining.pop())
else:
print(-1)
view raw atcoder-abc-313-b.py hosted with ❤ by GitHub

C - Approximate Equalization 2

今回の操作では, 整数列Aの総和は変化しません. これを考慮すると, 最小値と最大値の差が1以下になったとき, Aの各項はAの平均値の切り捨て値または切り上げ値のいずれかにならなければなりません. そこで, 以下のような操作をすることを考えます.

  • Aの平均値よりも大きい項：Aの平均値の切り上げ値になるまで減算する(減算回数decrement)
  • Aの平均値以下の項：Aの平均値の切り捨て値になるまで加算する(加算回数increment)

問題文の制約によって, decrement=incrementが求められます. しかし, Aの最小値と最大値を変化させないように少ない方の操作を行えばよいです. したがって, 最終的な出力はdecrementとincrementのうち大きい方となります.

# 入力
N = int(input())
A = list(map(int, input().split()))
# Aの平均値とその切り捨て・切り上げを求める
sum_A = sum(A)
ave_A = sum_A / N
ave_A_floor = sum_A // N
ave_A_ceil = (sum_A + N - 1) // N
# 減算する回数と加算する回数を求める
decrement_count = 0
increment_count = 0
for i in range(N):
if A[i] <= ave_A:
decrement_count += ave_A_floor - A[i]
else:
increment_count += A[i] - ave_A_ceil
# 出力
print(max(increment_count, decrement_count))
view raw atcoder-abc-313-c.py hosted with ❤ by GitHub

D - Odd or Even

解説にある解法の通りです. 偶奇の計算の際には排他的論理和 XORを適切に用いることができます.

# 入力
N, K = map(int, input().split())
# 求める整数列A
A = [0 for _ in range(N)]
# クエリの応答結果を格納しておく数列T
T = [0 for _ in range(N)]
# A_1からA_(K + 1)までのパリティ
parity_from_1_to_K_plus_1 = 0
# A_1からA_(K + 1)までを求める
for i in range(K + 1):
query_x = [x % (K + 1) + 1 for x in range(i, i + K)]
print("?", *query_x)
T[i] = int(input())
parity_from_1_to_K_plus_1 ^= T[i]
for i in range(K + 1):
A[i] = parity_from_1_to_K_plus_1 ^ T[(i + 1) % (K + 1)]
# A_(K + 2)からA_Nまでを求める
for i in range(K + 1, N):
print("?", *range(1, K), i + 1)
T[i] = int(input())
for j in range(K - 1):
T[i] ^= A[j]
A[i] = T[i]
# 出力
print("!", *A)
view raw atcoder-abc-313-d.py hosted with ❤ by GitHub

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等