初めに
ABC334のA~D問題をPythonで解きました。
A: Christmas Present
コード
B, G = map(int, input().split())
if B > G:
print("Bat")
else:
print("Glove")
B: Christmas Trees
解説がみんなスマートすぎるので僕がコンテスト中に書いた場合分け解法を紹介します。
もっとスマートな解法はこちら
まずはLとRからAを引いてやり、クリスマスツリーがMの倍数地点に立つようにします。
あとはLとRの間に立っているツリーの本数計算ですが、これはLとRが共に正の時、「Rまでに立っているツリーの本数」- 「L-1までに立っているツリーの本数」で求められます。
更に、LとRが共に負の時、0を軸に正の方向にひっくり返す操作をすることで「abs(L)までに立っているツリーの本数」 - 「abs(R)-1までに立っているツリーの本数」で同様の計算により答えが求められます。
最後に、Lが負でRが正の時、負の方向に何本立つか、正の方向に何本立つかをそれぞれ求めて合計することで答えが求められます。０にもツリーが立つことに注意します。
コード
A, M, L, R = map(int, input().split())
L -= A
R -= A
if R <= 0:
# 共に負なので、絶対値を取って正に戻す
L, R = abs(L), abs(R)
# Lの方が0から遠いことに注意
l = L//M
r = (R-1)//M
print(l-r)
elif L < 0 < R:
# 間に0が挟まっているので、LとRを別々に計算して足してやる
l = abs(L)//M
r = R//M
print(l+r+1)
else:
# 共に正、一つ目の場合と同様に計算する
# Rの方が遠いことに注意
l = (L-1)//M
r = R//M
print(r-l)
C: Socks 2
まず、同じ色の靴下が二枚ある場合、それらはペアにするのが最適です。これは、下の図のように同じ色でペアにしても奇妙さが変わらないことからも分かります。
従ってAに含まれる色だけを使って奇妙さを最小にすることを考えます。
Aの要素数が偶数の時、前から貪欲にペアを作っていくのが良いです。
Aの要素数が奇数の時、一つだけ使わない靴下が出るので、それを全探索します。
最初は一つ目の靴下を使わないシナリオで奇妙さの合計を求めておきます。その後は使わない靴下を順番に探索していくのですが、下の図のように、2番目の靴下を除外すると1番と3番をペアにすることになり、2番を跨ぐことになって奇妙さが増えてしまいます(下図2行目)。
従って、除外する靴下として考えるのは1番目、3番目、5番目…の奇数番目のものだけで良いです。
では、除外するときにどのような操作をすればよいか考えてみます。具体的には、図の１行目から3行目に移るときにどのような操作をするかを考えます。
1行目から3行目に移るとき、2番と3番のペアを解消して1番と2番のペアを作っています。この操作は、直前の奇妙さの合計を$S$とし、1番、2番、3番目の靴下をそれぞれ$A[i-1], A[i], A[i+1]$とすると
$$S - (A[i+1]-A[i]) + (A[i]-A[i-1])$$
と表せます。
コード
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
# 貪欲に前からペアを作っていくとき
greedy_pair = 0
# 0番目を飛ばしてペアを作るとき
skip = 0
for i in range(0, K-1, 2):
greedy_pair += A[i+1]-A[i]
if i+2 < K:
skip += A[i+2]-A[i+1]
# あり得る奇妙さの合計のリスト
skipped_list = [skip]
# 偶数なら前から貪欲に
if K%2 == 0:
print(greedy_pair)
# 奇数なら除外する靴下を全探索
else:
for j in range(1, K, 2):
# ペアを変更
skip = skip - (A[j+1] - A[j]) + (A[j] - A[j-1])
skipped_list.append(skip)
# Aの要素数が１の時はその靴下を除外するだけ
if len(skipped_list) == 0:
print(0)
else:
print(min(skipped_list))
公式解説放送がとてもわかりやすかったのでこちらも是非。
D: Reindeer and Sleigh
ソリの番号は関係ないので、昇順でソートしておきます。できるだけトナカイの必要数が少ないソリから使っていきます。
これは、「0からｘ台目のソリまで使う時に必要なトナカイ数」を累積和で前計算できるので、あとは実際のトナカイの数を用いて二分探索をし、答えを求めることができます。
コード
from bisect import bisect_right
N, Q = map(int, input().split())
R = sorted(list(map(int, input().split())))
A = [0]
for i in range(len(R)):
A.append(A[-1]+R[i])
for _ in range(Q):
q = int(input())
idx = bisect_right(A, q)
print(idx-1)