AtCoder Beginner Contest 188 - AtCoder 全問正解でした。最初の25分でA〜Eを解いた後、Fにハマって50分くらい使ってしまった。焦りは途中完全に焦ってしまっててペナルティが6つもついてしまった。
- 「点数の低い方に」という条件を見落として1WA、交換します python
X, Y = map(int, input().split())
if X > Y:
Y, X = X, Y
if X + 3 > Y:
print("Yes")
else:
print("No")
- ループで掛けて足すのを繰り返す 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):
ret += AS[i] * BS[i]
if ret == 0:
print("Yes")
else:
print("No")
- 次の試合に出る人のIDのリストを作ってN-1回トーナメントをやり、最後の2人が得られるので負ける側のIDを返す 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):
if AS[PS[i]] > AS[PS[i + 1]]:
newPS.append(PS[i])
else:
newPS.append(PS[i + 1])
PS = newPS
if AS[PS[0]] > AS[PS[1]]:
print(PS[1] + 1)
else:
print(PS[0] + 1)
- Twitter
-
「準優勝するのは、優勝する選手と反対のブロックを勝ち上がった選手」だから、右半分とmaxと左半分のmaxの小さい方のindexが答え src
- なるほど！
-
- プライムの入会退会にペナルティがないので、日額コストを計算してCを超えた日には入会してCを払うのでよい
- 日毎の日額コストを求めたいが10^5回、最大10^9日の区間に加算をするのは無理
- そこでRangeAddは二つのPointAdd
- 10^9日の区間は配列で持つのが辛い
- そこで辞書でやる 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())
diff[a] += c
diff[b + 1] -= c
keys = list(sorted(diff))
cost = 0
ret = 0
for i in range(1, len(keys)):
cost += diff[keys[i - 1]]
days = keys[i] - keys[i - 1]
ret += min(cost, C) * days
print(ret)
- 各頂点から各頂点への到達可能性を知りたいが素朴にやると間に合わなさそう
- 「Xi<Yiが保証されてる」という特殊な制約がキモ
- つまりiの小さい順に「そこに到達できる頂点での最小仕入れコスト」を更新していけば良い 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())
edges[frm - 1].append(to - 1) # -1 for 1-origin vertexes
INF = 9223372036854775807
minBuyCost = [INF] * N
ret = -INF
for i in range(N):
ret = max(ret, AS[i] - minBuyCost[i])
m = min(minBuyCost[i], AS[i])
for j in edges[i]:
minBuyCost[j] = min(minBuyCost[j], m)
print(ret)
- 時間軸反転
- +1した後に-1することはない
- +1した後に+1することはない、なぜなら+1,+1,/2より/2,+1の方が安いから
- 伏線: ここにミスがあります
- YがXより小さくなったら+1しかできない
- 優先度付きキューに入れて、コストが安い方から試していく
- 観察したらキューに同じ値が何度も入ってたので辞書を組み合わせる heapq+dict
- 12WA
- しばらくドタバタしてから、素朴解法を実装して小さい値の範囲で食い違いを観察 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が来ることはないが、そのままゴールインすることはあり得た
python
def solve(X, Y):
from heapq import heappush, heappop
queue = [(0, Y)]
minCost = {Y: 0}
INF = 9223372036854775807
def add(cost, y):
c = minCost.get(y, INF)
if cost < c:
minCost[y] = cost
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)