Atcoder ABC246 振り返り
シンプルなことに気付くのにとても時間がかかりWAを連発してしまった……前回前々回で上げたレートが……
A - Four Points【AC】
長方形なのでx,yそれぞれ同じ値が2つずつあるはずなので,たりないものを表示します.
X = [] Y = [] for _ in range(3): x, y = map(int, input().split()) if x in X: X.remove(x) else: X.append(x) if y in Y: Y.remove(y) else: Y.append(y) print(X[0], Y[0])
B - Get Closer【AC】
解くのにとんでもなく時間がかかってしまった……距離1進むというのはつまり半径1の円周上のどこかの点に移動すると言うことです.その円周と(0,0)(A,B)の線分の交点が求める点です.2乗する関係で-が消えてしまいますが,(A,B)の象限と交点の象限は必ず一致するので,ABの正負を記録しておいて,xyでその正負を反映させるようにします.
A, B = map(int, input().split()) if A == 0: print(0, 1) else: x = (1/(1+(B/A)**2))**(0.5) if A < 0: x *= -1 y = (B/A)*x if B < 0: y *= -1 print(x, y)
C - Coupon【AC】
貪欲法だ!そのためにはソートだ!と考えてしまったため沼ってしまいました……どんな金額の商品でも,クーポン1枚で引かれる金額は同じです.さらに,合計金額を最小化するので,Xより高い金額の商品ならどれでもクーポンを使うべきです.X未満の金額の商品では,引かれる金額は商品自身なので,商品によって引かれる金額が変わります.よって,X未満の金額の商品のみをソートして,クーポンが使える回数分上位の商品を引くべきです.実装ではsum(A[:-K])としています.なお,この場合K=0の時A[:]となってしまうので気をつけます.
N, K, X = map(int, input().split()) A = [int(i) for i in input().split()] AA = [] for a in A: if K > 0 and a >= X: if K >= a // X: K -= a // X AA.append(a%X) else: AA.append(a-K*X) K = 0 else: AA.append(a) A = sorted(AA) if K == 0: print(sum(A)) elif len(A) > K: print(sum(A[:-K])) else: print(0)
D - 2-variable Function【解説AC】
aとbは3乗されており,Nが10^18なのでabは最大10^6であることには気付いていました.これを尺とり法のように範囲を狭めていけば良いと言うことを学びました.
式から,aとbは対称です.よって,i1
このことから,aは0から,bは10^6から探索することで最小値を見つけることが出来ます.
N = int(input()) X = 1<<60 b = 10**6 def f(a, b): return a**3 + a**2*b + a*b**2 + b**3 for a in range(10**6+1): while f(a, b) >= N and b >= 0: X = min(X, f(a, b)) b -= 1 print(X)