ABC216のA-E問題の解説。
目次
A - Signed Difficulty
B - Same Name
C - Many Balls
D - Pair of Balls
E - Amusement Park
A - Signed Difficulty
解説
$X.Y$を$Y$に対して、$X$の表示方法を変えるという条件分岐問題。
.に対して、2つに分けることができればAC。
コード
def main():
x, y = map(int, input().split('.'))
if 0 <= y and y <= 2:
print(str(x)+'-')
elif 3 <= y and y <= 6:
print(str(x))
elif 7 <= y and y <= 9:
print(str(x)+'+')
if __name__ == '__main__':
main()
B - Same Name
解説
問題文を簡潔にまとめると、ひとりひとり順番に名前を記録していき、記録した名前の中に同姓同名の名前があれば、Yesを出力、なければ、Noを出力するという問題。
そのとおりに実装すればAC。
コード
def main():
n = int(input())
names = []
for i in range(n):
s, t = map(str, input().split())
if (s, t) in names:
print('Yes')
exit()
names.append((s, t))
print('No')
if __name__ == '__main__':
main()
C - Many Balls
解説
箱の中にボールを1つ増やすのと、箱の中のボールの数を2倍にする、という2つの操作ではこの中のボールの数をちょうどN個にする方法を探す問題。
合計120回という制約があるが、例えば、魔法Bだけを最大回数使った場合、最大値は$2^{120}$、つまり、$1.3 \times 10^{36}$なので、制約$(1 \leq N \leq 10^{18}) \leq 10^{36}$より十分満たしています。したがって、2倍が使えるときは積極的に魔法Bを使います。
解法の1つとして、Nを逆順に操作するという方法があります。Nが偶数のときは2で割った数をNに再代入、Nが奇数のときは1を引いた数をNに再代入、これをNが0よりも大きいときに続けて、A, Bを順番に並べます。
最後にこの順番は逆順で操作しているので、文字列自体を反転させることでACできる。
コード
def main():
n = int(input())
ans = ''
while n > 0:
if n % 2 == 0:
n //= 2
ans += 'B'
else:
n -= 1
ans += 'A'
print(''.join(list(reversed(ans))))
if __name__ == '__main__':
main()
D - Pair of Balls
解説
今、$1$以上$N$以下で表される色を持ったボールが$2N$個ある。各色で塗られたボールは、ちょうど2個ずつ存在することが保証されている。
このとき、$i$番目の筒に$k_i$個のボールが入っている。上から$j$番目のボールの色は$a_{i, j}$で表される。
このとき、異なる2つの筒の一番上にある色のなかに同じ色があれば、それを取り出し、筒の中を空にすることができるかという問題。
ある容器から取り出す操作があるので、dequeを使うのが無難である。
まず、それぞれのボールを保存する筒と、筒の一番上のボールを保存する容器を用意する。このとき、同じ色を持つボールを管理する容器として、dequeを用いる。
すべての筒の一番上のボールを保存する容器をtopとする。topにボールを入れるとき、筒の番号を挿入する。こうすることで、次にボールとりだす筒を判定することができる。
各筒から一番上のボールをそれぞれ1つとりだし、その2つについて、ボールの色が揃っているかどうか判定する。もし色が揃っているボールが存在したら、queに追加する。もし、queに値がない、つまり、色が揃っているボールの色が存在しなくなったら、whileループを抜けて判定に入る。
どれかの筒に1つでも値が残っていたら、今回の「筒の中を空にする」という条件をみたしていないので、ifがFalseとなる。逆に、筒がすべて空になっていれば条件を見対しているので、ifがTrueになる。
コード
def main():
from collections import deque
n, m = map(int, input().split())
tubes = []
for _ in range(m): # それぞれのボールを保存する筒を準備する
k = int(input())
tube = list(map(lambda x: x-1, list(map(int, input().split()))))
tubes.append(tube)
top = [[] for _ in range(n)] # n色分の容器を用意
for i in range(m):
if tubes[i]:
top[tubes[i][-1]].append(i)
que = deque([i for i in range(n) if len(top[i]) == 2]) # 同じボールが2個ある容器をqueに入れる
while que:
v = que.popleft()
i, j = top[v]
tubes[i].pop() # tubeから揃ったボールを取り出す
tubes[j].pop() # tubeから揃ったボールを取り出す
if tubes[i]:
top[tubes[i][-1]].append(i) # 新しいボールをtopに追加
if len(top[tubes[i][-1]]) == 2: # 同じ色のボールが2つ揃ったら
que.append(tubes[i][-1]) # queに追加
if tubes[j]:
top[tubes[j][-1]].append(j) # 同様
if len(top[tubes[j][-1]]) == 2:
que.append(tubes[j][-1])
if all(not tubes[i] for i in range(m)): # すべてのtubeが空、つまり、[]であれば
print('Yes')
else:
print('No')
if __name__ == '__main__':
main()
E - Amusement Park
解説
N個のアトラクションにそれぞれの満足度が与えられいて、1回乗るごとにそのアトラクションの満足度は1減少する。また、アトラクションは$K$回まで乗ることができる。
このとき、高橋くんの最終的な「満足度」の最大値はいくつかを答える問題。
$A$をソートして、常に最大値を取り続けるという方法が考えられるが、この操作を$K$回行うと、制約が最大$2 \times 10^9$なので、AtCoderの判定には間に合わない。
では、どうすればよいか。以下の記事でも解説しているが、1) 最大値を求める、2) 制約が$10^9$、という2つが読み取れるので、二分探索を用いることで、今回の答えを求めることができる。
二分探索を用いて、どんな判定問題を考えればいいかというと、以下のような数列$B$を考えて、
$B = [1, 2, ..., A_1, 1, 2, ..., A_2, ..., 1, 2, ..., A_N]$
数列$B$に含まれているm以上の値は$K$個以下か？
という単調性を持つ問題を考えれば良い。この$m$を求める操作に、二分探索を用いる。
例えば、$A = [10, 8, 6]$という数列$A$で$K = 5$のときを考える。これは、$B = [1, 2, ..., 10, 1, 2, ..., 8, 1, 2, ..., 6]$から、$m$以上の値を持つものが$K$個以下であるかを判定すれば良い。
二分探索によりこの$m$は8であることがわかる。よって$B$から、8, 8, 9, 10の4つがとりだせる。これは合計$K$回以内を満たしている。$5 - 4 = 1$でまだ1回分残っているがとりあえずは気にする必要はない。
これで$B$の値を全部足せば良い、が、制約が大きいので実際に$B$という数列を作り出すことはできない。ではどうすればよいかというと、「$1$から$A$までの和」から「$1$から求めた$m$までの和」を引くことで、$B$を再現することができる。参考までに$1$から$n$までの和を示した式を以下に示しておく。
$\frac{1}{2} n (n+1)$
これで、$B$から取り出した$m$以上の和を実装できる。残りの1回分は$m$から1引いた数を$K$回分、先程の答えに足してやれば、最大の「満足度」を求めることができる。
二分探索について深堀りしたい方は、こちらの記事からさまざまな問題に取り組んでいただきたい。
コード
def main():
def is_ok(x):
now = 0
for i in range(n):
if alist[i] >= x: # A_iがx以上の数であるとき
now += alist[i]-x+1 # iのアトラクションに何回乗ったか
return now <= k
# めぐる式二分探索
def meguru_bisect(ng, ok):
while (abs(ok - ng) > 1):
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
return ok
n, k = map(int, input().split())
alist = list(map(int, input().split()))
ng, ok = -1, 2*10**9+1
ok = meguru_bisect(ng, ok)
temp = 0
cnt = 0
for i in range(n):
if alist[i] >= ok: # Aの中でok以上の数ならば
cnt += alist[i] - ok + 1 # アトラクションiに乗った回数
# 初項A公差-1の0までの和と初項ok公差-1の0までの和を引いた値（満足度）
temp += alist[i]*(alist[i]+1)//2 - ok*(ok-1)//2
if ok != 0:
temp += (ok-1) * (k-cnt) # アトラクションの残り回数を使い切る
print(temp)
if __name__ == '__main__':
main()
編集後記
E問題、二分探索ということに気づけて、初めて解けるかなーと思ったが、条件文を全く思いつくことできず、コンテストが終了してしまった...。