Atcoder ABC253 振り返り
1WAに延々苦しめられるの久しぶりにやりました……
A - Median?【AC】
bが中央値の時,a,b,cを数値順に並べた時にbが真ん中に来るため,それをif文にかければ良いです.
a, b, c = map(int, input().split()) if a <= b <= c or a>= b >= c: print("Yes") else: print("No")
B - Distance Between Tokens【AC】
(x1, y1)と(x2, y2)の最短移動距離は|x1-x2|+|y1-y2|で求まります.oの位置を一つずつ確認すれば求められます.
H, W = map(int, input().split()) koma = [] for i in range(H): S = input() for j in range(W): if S[j] == "o": koma.append([i, j]) print(abs(koma[0][0] - koma[1][0]) + abs(koma[0][1] - koma[1][1]))
C - Max - Min Query【AC】
このクエリでやるべきタスクは二つあります.一つ目がSにxがいくつ入っているかを調べる,二つ目がSの最小値と最大値を取り出すというタスクです.一つ目は辞書を使えば良さそうです.追加のクエリが来たら辞書に対応する値を+1,削除するクエリが来たら辞書に対応する値を-1すれば良いです.
しかし,辞書では高速に最小値最大値を取り出す事は出来ないので二つ目のタスクをこなすことができません.そのため,最小値をlog nで取り出す事が出来るヒープ構造を使います.新しい数字が追加されたらヒープにその数字をpushします.そして,popすると最小値を取り出す事が出来ます.そのpopした数字が辞書で0でなければ,Sにその数字があるという事なのでそれを最小値にします.辞書で0ならば,その数字はすでに削除されていたと言う事なので,もう一度popし次に最小の値を取り出します.
最大値は各要素に-1を掛けて,その最小値を取り出せば良いです.
取り出した最小値と最大値は再びヒープの中にpushするのを忘れないようにします.
import heapq num = [] num_ = [] dic = {} for _ in range(int(input())): query = [int(i) for i in input().split()] if query[0] == 1: dic.setdefault(query[1], 0) dic[query[1]] += 1 if dic[query[1]] == 1: heapq.heappush(num, query[1]) heapq.heappush(num_, -query[1]) elif query[0] == 2: dic.setdefault(query[1], 0) dic[query[1]] -= min(query[2], dic[query[1]]) else: max_num = -heapq.heappop(num_) while dic[max_num] == 0: max_num = -heapq.heappop(num_) min_num = heapq.heappop(num) while dic[min_num] == 0: min_num = heapq.heappop(num) heapq.heappush(num_, -max_num) heapq.heappush(num, min_num) print(max_num-min_num)
D - FizzBuzz Sum Hard【解説AC】
Nまでの総和-Aの倍数の総和-Bの倍数の総和+AとBの倍数の総和が答えになります.
AとBの倍数はAとBの最小公倍数です……A*Bではありません……
import math N, A, B = map(int, input().split()) NA = N // A NB = N // B AB = A*B // math.gcd(A, B) NAB = N // AB max_a = NA * A max_b = NB * B max_ab = NAB * AB if A % B == 0: print(N*(N+1)//2 - NB*(B+max_b)//2) elif B % A == 0: print(N*(N+1)//2 - NA*(A+max_a)//2) else: print(N*(N+1)//2 - NA*(A+max_a)//2 - NB*(B+max_b)//2 + NAB*(AB+max_ab)//2)