ABC188
全問正解でした。最初の25分でA〜Eを解いた後、Fにハマって50分くらい使ってしまった。焦りは途中完全に焦ってしまっててペナルティが6つもついてしまった。
https://gyazo.com/c4d11f9ce3d61e26fe505cf52f0fcaeb
https://gyazo.com/4609564a3c452f696c5c8b8ae80f176e
https://gyazo.com/9440dcf0419562d1b705b2004be36511
「点数の低い方に」という条件を見落として1WA、交換します
code:python
X, Y = map(int, input().split())
if X > Y:
Y, X = X, Y
if X + 3 > Y:
print("Yes")
else:
print("No")
https://gyazo.com/d780c78a7d0081ce919dd80c915291da
ループで掛けて足すのを繰り返す
code:python
def main():
N = int(input())
AS = list(map(int, input().split()))
BS = list(map(int, input().split()))
ret = 0
for i in range(N):
if ret == 0:
print("Yes")
else:
print("No")
https://gyazo.com/0b911fc8e109fee21c9c592e6e26e671
次の試合に出る人のIDのリストを作ってN-1回トーナメントをやり、最後の2人が得られるので負ける側のIDを返す
code:python
def main():
N = int(input())
AS = list(map(int, input().split()))
PS = range(2 ** N)
for _r in range(N - 1):
newPS = []
for i in range(0, len(PS), 2):
else:
PS = newPS
else:
Twitter
「準優勝するのは、優勝する選手と反対のブロックを勝ち上がった選手」だから、右半分とmaxと左半分のmaxの小さい方のindexが答え src なるほど!
https://gyazo.com/9e383b268bf227d379e4cef649a273e1
プライムの入会退会にペナルティがないので、日額コストを計算してCを超えた日には入会してCを払うのでよい
日毎の日額コストを求めたいが10^5回、最大10^9日の区間に加算をするのは無理
10^9日の区間は配列で持つのが辛い
そこで辞書でやる
code:python
def main():
N, C = map(int, input().split())
from collections import defaultdict
diff = defaultdict(int)
for _n in range(N):
a, b, c = map(int, input().split())
keys = list(sorted(diff))
cost = 0
ret = 0
for i in range(1, len(keys)):
ret += min(cost, C) * days
print(ret)
Twitter
座標圧縮をするという意見、なるほど確かにそれでもいいね いもす法とかイベントソートとか、いろんな名前で言及されてるね、イベントソートって言葉は初耳なのだが「区間の開始イベントと終了イベントをまとめてソート」ということか。僕は「時刻→増減」の辞書を使ったが、「(時刻, 増減)」のリストを使うということだろう。同じ時刻のイベントがあるので少し手間かも https://gyazo.com/643399598cd75f589f09039a4773f7d8
各頂点から各頂点への到達可能性を知りたいが素朴にやると間に合わなさそう
「Xi<Yiが保証されてる」という特殊な制約がキモ つまりiの小さい順に「そこに到達できる頂点での最小仕入れコスト」を更新していけば良い
code:python
def main():
N, M = map(int, input().split())
AS = list(map(int, input().split()))
from collections import defaultdict
edges = defaultdict(list)
for _i in range(M):
frm, to = map(int, input().split())
edgesfrm - 1.append(to - 1) # -1 for 1-origin vertexes INF = 9223372036854775807
ret = -INF
for i in range(N):
ret = max(ret, ASi - minBuyCosti) m = min(minBuyCosti, ASi) minBuyCostj = min(minBuyCostj, m) print(ret)
https://gyazo.com/2f312cac88ff2f3803637e6be88c1ff5
+1した後に-1することはない
+1した後に+1することはない、なぜなら+1,+1,/2より/2,+1の方が安いから
伏線: ここにミスがあります
YがXより小さくなったら+1しかできない
優先度付きキューに入れて、コストが安い方から試していく
12WA
しばらくドタバタしてから、素朴解法を実装して小さい値の範囲で食い違いを観察
code:python
def blute(X, Y):
queue = {X}
ret = 0
while True:
newqueue = set()
if Y in queue:
return ret
ret += 1
for x in queue:
newqueue.add(x * 2)
newqueue.add(x + 1)
newqueue.add(x - 1)
queue = newqueue
def fulltest():
for x in range(20):
for y in range(20):
s = solve(x, y)
b = blute(x, y)
if s != b:
print(x, y, s, b)
ミスの原因「+1や-1の連続が最短経路のケースを取りこぼしてる」
下記コードの(1)のところ
「+1した後に+1することはない」は間違い。
その後に/2が来ることはないが、そのままゴールインすることはあり得た
code:python
def solve(X, Y):
from heapq import heappush, heappop
minCost = {Y: 0}
INF = 9223372036854775807
def add(cost, y):
c = minCost.get(y, INF)
if cost < c:
heappush(queue, (cost, y))
while True:
cost, y = heappop(queue)
if y == X:
return cost
if y < X:
add(cost + (X - y), X)
continue
if y == X + 1:
add(cost + 1, X)
continue
add(cost + (y - X), X) # (1)
if y % 2 == 0:
add(cost + 1, y // 2)
else:
add(cost + 2, (y + 1) // 2)
add(cost + 2, (y - 1) // 2)
Twitter
y<xならx-yが答えなのだ。そうじゃないときはAGC044Aと大体同じなのだ。逆から考えて、最後以外は±1が連続しないことを使って、メモ化再帰すれば状態数が少なくて解ける src