🙈

AtCoder Beginner Contest 216

2022/03/31に公開約3,400字

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()

S_iT_iは共に英小文字(a~z)なので、適当な記号で連結した後に集合を見てあげれば十分です。

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

ログインするとコメントできます