🙈
AtCoder Beginner Contest 216
A - Signed Difficulty
import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def main():
x,y = input().split('.')
y = int(y)
if 0<=y<=2:
print('{}-'.format(x))
elif 3<=y<=6:
print('{}'.format(x))
else:
print('{}+'.format(x))
if __name__ == '__main__':
main()
入力を'.'区切りで受け取ります
出力の際には文字列に変数を組み込めるformatメソッドを使うと便利です。
B - Same Name
import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def main():
n = int(input())
lst = []
for _ in range(n):
s,t = input().split()
lst.append(s+'&'+t)
print('Yes' if len(set(lst))!=n else 'No')
if __name__ == '__main__':
main()
C - Many Balls
import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def main():
n = int(input())
ans = ''
while n>0:
if n%2==0:
ans += 'B'
n //= 2
else:
ans += 'A'
n -= 1
print(ans[::-1])
if __name__ == '__main__':
main()
魔法Bの方が魔法Aよりもコスパよくボールの数を増やせそうなことに着目しましょう。
ここでは操作を逆に考えて(魔法Aでボールが1つ減る・魔法Bでボールの数が半分になる)、N個のボールから減らしていけば良いです。
この時に、魔法Bを優先的に使うことでなるべく少ない操作数で行えます。
D - Pair of Balls
import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def main():
n,m = map(int, inputs().split())
lst = []
idx = [[] for _ in range(n+1)]
que = deque([])
cnt = defaultdict(int)
for i in range(m):
k = int(input())
a = list(map(int, inputs().split()))
lst.append(a)
for x in a:
idx[x].append(i)
cnt[a[-1]] += 1
if cnt[a[-1]] == 2:
que.append(a[-1])
while que:
x = que.popleft()
a,b = idx[x]
lst[a].pop()
lst[b].pop()
if lst[a]:
y = lst[a][-1]
cnt[y] += 1
if cnt[y] == 2:
que.append(y)
if lst[b]:
y = lst[b][-1]
cnt[y] += 1
if cnt[y] == 2:
que.append(y)
print('Yes' if set([len(x) for x in lst])=={0} else 'No')
if __name__ == '__main__':
main()
見えているボールのうち同じ色のボールの組があるかどうかを見ていきます。
前から見ていくとindexの管理が面倒なので、末尾からボールを削除していきました。
最後に全てのボールが削除できているかどうかを確認しましょう。
E - Amusement Park
import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)
def main():
n,k = map(int, inputs().split())
a = list(map(int, inputs().split()))
l,r = 0, 2*10**19+10
while abs(r-l)>1:
mid = (r+l)//2
cnt = 0
for x in a:
if x>=mid:
cnt += x-mid+1
if cnt<=k:
r = mid
else:
l = mid
ans = 0
rem = k
for i in range(n):
if a[i]>=r:
d = a[i]-r+1
ans += d*(a[i]+r)//2
rem -= d
ans += rem*(r-1)
print(ans)
if __name__ == '__main__':
main()
Kがとても大きいのでBを愚直の並べてソートする、といった手法は難しそうです。
二分探索を使って境界となる数値を求めたのち、等差数列の和を加算していきます。
Discussion