AtCoder Beginner Contest 246 (ABC246)
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>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()
制約の
始めは以下の式変形を考え
しかしi,jの値を決定しても、i=a+bかつj=abを満たす非負整数組(a,b)が存在するということは保証できないため、結局(a,b)の値を考えることになってしまうという理由からこの方針を断念しました。
よってaを何かしらの値で決めたとき、「
まとめると以下の手順となります。
- aは
の範囲で全探索する0 \leq a \leq 10^{6} -
を満たすbを二分探索X=a^3+a^2b+ab^2+b^3 \geq N - 最終的に決定した(a,b)に対してXを計算
実行時間に少しの不安が残ったものの、上記の方針で無事にACできました。
Author And Source
この問題について(AtCoder Beginner Contest 246 (ABC246)), 我々は、より多くの情報をここで見つけました https://zenn.dev/ohnuma/articles/4af467d93b5e78著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol