AtCoder Beginners Contest 313 (ABC313) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - To Be Saikyo
問題ページ
考察
$P_1$ だけをint型の整数として受け取って、残りはリストとして受け取ります。( $N=1$ がコーナーケースで注意！)
人 $1$ が最強になるために必要な力は、 $(リスト内の最大値)+1-(人1の値)$ です。
これを計算してあげて、もし負の数になったらすでに人 $1$ が最強だということなので、その値を0にします(下のコードでは、はしょってmax関数で処理しています)。
コード
N = int(input())
if N == 1:
print(0)
exit()
p1, *p = map(int, input().split())
ans = max(max(p) + 1 - p1, 0)
print(ans)
B - Who is Saikyo?
問題ページ
考察
「人Aは人Bより強い」の情報がいくつかとんできます。
これを、頂点B → 頂点A の有向辺だと思うことにします。
ある頂点C から伸びている辺がない(出次数が0の)とき、人Cよりも明確に強い人がいないので、人Cは最強の可能性があります。
伸びている辺がない頂点の数が $1$ つだけのとき、その頂点の番号を出力します。もし $2$ つ以上あるときは、最強の人が確定しないので、 $-1$ を出力します。
コード
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
a, b = map(lambda x: int(x) - 1, input().split())
G[b].append(a)
winner = []
for i in range(N):
if len(G[i]) == 0:
winner.append(i)
if len(winner) == 1:
print(winner[0] + 1)
else:
print(-1)
C - Approximate Equalization 2
問題ページ
考察
「$A_i$ を1減らして、 $A_j$ を1増やす」の操作は、何度やってもリストAの要素の総和は変わりません。
たとえばサンプル1では、$A=[4,7,3,7]$ です。総和は $21$ で要素数が $4$ なので、操作後は $A=[5,5,5,6]$ や $A=[5,6,5,5]$ のようになっているはずです。
ただ、わざわざ最小値の3を6にして $A=[5,5,6,5]$ とはしなさそうです。
この問題では要素の順番はどうでもよさそうなので、リストAは受け取ってすぐに昇順にソートしちゃいます。
ソートすることで、$A=[5,6,5,5]$ や $A=[5,5,6,5]$ などは考えずに $A=[5,5,5,6]$ になるように操作を行っていけばokになってうれしいです。これで操作後のリストが確定しました。
「$A_i$ を1減らして、 $A_j$ を1増やす」の操作を同時に逐一シミュレーションしてられないので、次のように言い換えます。
あなたは次の2種類の操作を行うことができます。
- $A_i$ を1減らす
- $A_i$ を1増やす
操作回数を2で割った値を出力してください。
操作前のリストと操作後のリストは決まっているので、同じインデックスにある要素の差の絶対値を逐一たしていけば答えになります。
コード
N = int(input())
A = list(map(int, input().split()))
A.sort()
sum_A = sum(A)
base, zan = divmod(sum_A, N)
B = [base] * N
i = N - 1
for _ in range(zan):
B[i] += 1
i -= 1
ans = 0
for a, b in zip(A, B):
ans += abs(b - a)
print(ans // 2)
D - Odd or Even
問題ページ
ひとこと
あまり一般的な解法ではないと思います。
「こんな解き方もあるんだな～」程度に見てもらえるとありがたいです。
考察
たとえば $A=[1,0,1,1,0,0,1]$ で、 $K=5$ とします。
最初2回で、$(A_1, A_2,A_3,A_4 ,A_6)$ と $(A_1, A_2,A_3,A_4, A_7)$ の偶奇を聞きます。
そうすると、ジャッジから返ってきた2つの値が等しければ、$A_6=A_7$ で、2つの値が異なっていれば $A_6 \neq A_7$ です。また、 $A_6+A_7$ の偶奇も分かります($A_6=A_7$ のとき偶数、$A_6 \neq A_7$ のとき奇数)。
実はこれで、$N=7,K=5$ の問題だったのが、 $N=5,K=3$ の問題に落ちています。
なぜなら、たとえば $(A_1, A_2, A_4)$の偶奇を知りたかったら、$(A_1, A_2, A_4, A_6, A_7)$ をジャッジに聞けば、私たちはすでに $A_6+A_7$ の偶奇を知っていて、 $(A_1, A_2, A_4)$ でジャッジに聞いているのとほぼ同じになっているからです。
ジャッジに$(A_1, A_2, A_4)$ と $(A_1, A_2, A_5)$ を聞いている感覚で、ジャッジに $(A_1, A_2, A_4, A_6, A_7)$ と $(A_1, A_2, A_5, A_6, A_7)$ を聞くことで、先ほどと同じ議論で $A_4+A_5$ の偶奇が分かります。そして、$N=3, K=1$ の問題に落とせます。
ジャッジに $(A_1, A_4, A_5, A_6, A_7)$ を聞くと、$A_4+A_5$ と $A_6+A_7$ の偶奇は分かっているので $A_1$ の値が分かります。
$(A_2, A_4, A_5, A_6, A_7)$ をジャッジに聞いて $A_2$ の値が分かり、$(A_3, A_4, A_5, A_6, A_7)$ をジャッジに聞いて $A_3$ の値が分かります。
これで質問回数はすべて使い果たしました。
ここから残りの $A_4$ ～ $A_7$ を求めます。
$(A_1, A_2, A_4, A_6, A_7)$ を質問した結果はすでに知っています。 $A_1$ と $A_2$ は求まっていて、 $A_6+A_7$ の偶奇は知っているので、$A_4$ の値が分かります。
同様にして、$(A_1, A_2, A_5, A_6, A_7)$ を質問した結果から、 $A_5$ の値が分かります。
$(A_1, A_2,A_3,A_4 ,A_6)$ を質問した結果と、$A_1$ ～ $A_5$ の値を知っていることから、 $A_6$ の値も分かります。
同様にして、$(A_1, A_2,A_3,A_4 ,A_7)$ から $A_7$ の値も分かります。
以上より、リスト $A$ のすべての値が特定できました。
(一般化して書くのは長くなるので省略します。)
コード
N, K = map(int, input().split())
if K == 1:
ans = []
for i in range(1, N + 1):
print('?', i)
el = int(input())
ans.append(el)
print('!', *ans)
exit()
ans = [None] * N
qed = [] # 右側ですでに偶奇が分かってるペアを格納する。
question_stack = [] # 質問したリストを格納する。
def question(n, k):
if k == 1:
val = 0
for i in qed:
val += ans[i - 1]
val %= 2
for i in range(1, n + 1):
print('?', *qed + [i])
el = int(input())
ans[i - 1] = (el - val) % 2
# print(f'{ans=}')
for i in range(n, N):
ls = question_stack.pop()
# print(f'{i=}, {ls=}')
val = 0
for idx in ls:
if idx - 1 != i:
val += ans[idx - 1]
val %= 2
if val == ans[i]:
ans[i] = 0
else:
ans[i] = 1
return
q_lst = [i for i in range(1, k)]
t1 = q_lst + [n - 1] + qed
print('?', *t1)
el = int(input())
ans[n - 2] = el
t2 = q_lst + [n] + qed
print('?', *t2)
el = int(input())
ans[n - 1] = el
question_stack.append(t2)
question_stack.append(t1)
qed.append(n - 1)
qed.append(n)
if k - 2 >= 1:
question(n - 2, k - 2)
question(N, K)
print('!', *ans)