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

なるほど！

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

各頂点から各頂点への到達可能性を知りたいが素朴にやると間に合わなさそう

つまり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())

INF = 9223372036854775807

ret = -INF

for i in range(N):

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