ABC188

NISHIO Hirokazu [Translate]
ABC188
AtCoder Beginner Contest 188 - AtCoder
全問正解でした。最初の25分でA〜Eを解いた後、Fにハマって50分くらい使ってしまった。焦りは途中完全に焦ってしまっててペナルティが6つもついてしまった。


A - Three-Point Shot
「点数の低い方に」という条件を見落として1WA、交換します
pythonX, Y = map(int, input().split())
if X > Y:
    Y, X = X, Y
if X + 3 > Y:
    print("Yes")
else:
    print("No")

B - Orthogonality
ループで掛けて足すのを繰り返す
pythondef 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")

C - ABC Tournament
次の試合に出る人のIDのリストを作ってN-1回トーナメントをやり、最後の2人が得られるので負ける側のIDを返す
pythondef 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
なるほど！

D - Snuke Prime
プライムの入会退会にペナルティがないので、日額コストを計算してCを超えた日には入会してCを払うのでよい
日毎の日額コストを求めたいが10^5回、最大10^9日の区間に加算をするのは無理
そこでRangeAddは二つのPointAdd
10^9日の区間は配列で持つのが辛い
そこで辞書でやる
pythondef 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)
Twitter
>ABC183Dの解説にあるシミュレーションをすればいい src
座標圧縮をするという意見、なるほど確かにそれでもいいね
いもす法とかイベントソートとか、いろんな名前で言及されてるね、イベントソートって言葉は初耳なのだが「区間の開始イベントと終了イベントをまとめてソート」ということか。僕は「時刻→増減」の辞書を使ったが、「(時刻, 増減)」のリストを使うということだろう。同じ時刻のイベントがあるので少し手間かも

E - Peddler
各頂点から各頂点への到達可能性を知りたいが素朴にやると間に合わなさそう
「Xi<Yiが保証されてる」という特殊な制約がキモ
つまりiの小さい順に「そこに到達できる頂点での最小仕入れコスト」を更新していけば良い
pythondef 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)

F - +1-1x2
時間軸反転
+1した後に-1することはない
+1した後に+1することはない、なぜなら+1,+1,/2より/2,+1の方が安いから
伏線: ここにミスがあります
YがXより小さくなったら+1しかできない
優先度付きキューに入れて、コストが安い方から試していく
観察したらキューに同じ値が何度も入ってたので辞書を組み合わせる heapq+dict
12WA
しばらくドタバタしてから、素朴解法を実装して小さい値の範囲で食い違いを観察
pythondef 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が来ることはないが、そのままゴールインすることはあり得た
pythondef 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)
Twitter
> y<xならx-yが答えなのだ。そうじゃないときはAGC044Aと大体同じなのだ。逆から考えて、最後以外は±1が連続しないことを使って、メモ化再帰すれば状態数が少なくて解ける src