Zenn
🎉

AtCoder Beginner Contest 246

2022/04/03に公開
Python
競技プログラミング
AtCoder
abc
tech

ABC246お疲れ様でした。ABCDの4完(71分, 0WA)でした！
結果

E問題がどうしてもTLEとなってしまったので、しっかり解きなおしたいと思います...!

A - Four Points

import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
  x,y = defaultdict(int), defaultdict(int)
  for _ in range(3):
    a,b = map(int, input().split())
    x[a] += 1
    y[b] += 1
  ans = [-1, -1]
  for k,v in x.items():
    if v==1:
      ans[0] = k
  for k,v in y.items():
    if v==1:
      ans[1] = k
  print(*ans)

if __name__ == '__main__':
  main()

x座標, y座標を別々に考えると、それぞれ同じ座標が2回ずつ現れます。
よって出現回数を数えて1度のみの座標が答えとなります。

B - Get Closer

import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
  a,b = map(int, input().split())
  d = math.sqrt(a**2+b**2)
  print(a/d, b/d)

if __name__ == '__main__':
  main()

原点(0,0)と点(A,B)間の距離 d は以下の式で算出されます。

d = \sqrt{ A^{2}+B^{2} }

ここでd>1であることが制約から保証されているので、原点との距離が1となる線分上の座標は(A/d, B/d)となります。

C - Coupon

import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
  n,k,x = map(int, input().split())
  a = list(map(int, inputs().split()))
  cnt = 0
  for aa in a:
    cnt += aa//x
  if k<=cnt:
    print(sum(a)-k*x)
  else:
    rem = k-cnt
    a = [i%x for i in a]
    a = sorted(a, reverse=True)
    print(sum(a[rem:]))

if __name__ == '__main__':
  main()

クーポン券を1枚使うと最大でX円お得になります。ただし端数を0にする際にはなるべく大きな端数を選んであげた方がお得になります。
よって合計金額を最小にするためには、「X円減らせる商品からクーポンを使っていく」→「クーポンが余った場合には、大きい端数から貪欲にクーポンを使用していく」という方針が成り立ちます。

D - 2-variable Function

import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def func(u,v):
  return u**3 + v*(u**2) + u*(v**2) + v**3
  
def main():
  n = int(input())
  mx = 10**6+1
  ans = inf

  for a in range(mx):
    l,r = -1, mx
    while abs(r-l)>1:
      mid = (r+l)//2
      val = func(a, mid)
      if val>=n:
        r = mid
      else:
        l = mid
    x = func(a, r)
    ans = min(ans, x)
  print(ans)

if __name__ == '__main__':
  main()

制約の0 \leq N \leq 10^{18}に着目すると大体0 \leq a,b \leq 10^{6}の範囲であることがわかるため、非負整数(a,b)の組を全探索しようとするとO({10^6}^2)となってTLEしてしまいそうです。

始めは以下の式変形を考えi=a+b, j=abを満たす(i,j)を考えることで効率化できないか？ということを延々と考えていました。

X = a^3+a^2b+ab^2+b^3 = (a+b)^3 - 2ab(a+b) = i^3 - 2ij

しかしi,jの値を決定しても、i=a+bかつj=abを満たす非負整数組(a,b)が存在するということは保証できないため、結局(a,b)の値を考えることになってしまうという理由からこの方針を断念しました。

よってaを何かしらの値で決めたとき、「X \geq Nを満たすbを高速に求めることができるか？」を考えます。しかし一意にbを式変形や計算で求めることはできず、ある程度bも探索する必要性がありそうということから、bについては二分探索をするという手法に到達できました。
まとめると以下の手順となります。

  1. aは0 \leq a \leq 10^{6}の範囲で全探索する
  2. X=a^3+a^2b+ab^2+b^3 \geq Nを満たすbを二分探索
  3. 最終的に決定した(a,b)に対してXを計算

実行時間に少しの不安が残ったものの、上記の方針で無事にACできました。

Discussion