AtCoder Beginner Contest 188 C,E,F問題メモ

AtCoder Beginner Contest 188

C - ABC Tournament

• $2^N$ 人でトーナメントを行う
• トーナメント表で左から $i$ 番目の人のレートは $A_i$ で、各試合では $A_i$ が大きい方が勝つ
• 準優勝する人が左から何番目の人だったか答えよ
• $1 \le N \le 16$
• $A_i$ は全て異なる

やってることが、まんま最大値を求めるセグメント木の初期化だったので、ついそれ貼ってしまった。

よく考えたら左半分と右半分の最大値勝負でいける。

Python3

n = int(input())
aaa = list(map(int, input().split()))
semi = min(max(aaa[:1 << (n - 1)]), max(aaa[1 << (n - 1):]))
print(aaa.index(semi) + 1)

E - Peddler

• トポロジカルソートされた $N$ 個の都市と $M$ 本の有向道路が与えられる
• 都市 $i$ では、金が1kg $A_i$ 円で売買されている
• 行商人が、好きな都市で金を1kgだけ買い、そこから道路を辿って行ける他の都市で売る
• 行商人が得ることのできる最大利益（売却額-購入額）を求めよ
• $2 \le N \le 2 \times 10^5$

先頭から考えてもいいんだけど、後ろから考えた。

• $DP[i]=$ 都市 $i$ から到達できる都市（$i$ を含めて）の中で、最も高く売れる都市の売却額

こうして後ろから $i$ を埋めていく。

都市 $i$ で買ったときの最適な売却額 $S_i$ は、都市 $i$ から直接道がつながる都市 $j_1,j_2,...$ の中で、最も $DP[j]$ が高いもの。（無い場合は0とでもしておく）

よって、ここで買った場合は $S_i-A_i$ 円の利益を手にすることができる。

また、$DP[i]=\max(A_i, S_i)$ として更新しておく。

各都市についてこれを調べ、最も利益の高いものが答え。

買った都市と別の都市で売らないといけないので、$DP[j]$ の情報を取得する→利益を求める→$DP[i]$ を更新する という順番に注意。

Python3

n, m = map(int, input().split())
aaa = list(map(int, input().split()))
links = [set() for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    links[x].add(y)

dp = [0] * n
ans = -10 ** 18
for i in range(n - 1, -1, -1):
    best_sell = 0
    for u in links[i]:
        best_sell = max(best_sell, dp[u])
    if best_sell > 0:
        ans = max(ans, best_sell - aaa[i])
    dp[i] = max(aaa[i], best_sell)

print(ans)

F - +1-1x2

• 以下の操作を繰り返して、整数 $X$ を $Y$ にする最小手数を求めよ
• 操作
  • $X$ に1足す
  • $X$ から1引く
  • $X$ を2倍する
• $1 \le X,Y \le 10^{18}$

少し前に、より操作の種類が増えた類題がAGCで出題されていた。（LINK）

愚直には整数の値をそのまま頂点とした幅優先探索やDijkstraで解けるが、$X,Y$ が大きすぎるのでアウト。

ここで操作の性質に着目すると、「2倍してから+1を2回」するくらいなら「+1してから2倍」した方が絶対によい。
したがって、「一度2倍する操作をしたら、そこからは+1,-1は連続しては使わない」ということがいえる。

これにより、操作を大幅に限定することができる。

しかし、それでも最初に2倍する操作までは何回足したり引いたりすればいいかわからない。

これは、操作を逆から考えることで求めることができる。

• $Y$ から1引く
• $Y$ に1足す
• $Y$ を半分にする（割り切れる場合のみ）

こうすると、以下の2種類の操作で、$Y$ を必ず約半分にできる。

• $Y$ が偶数の時、半分にする
• $Y$ が奇数の時、+1または-1してから半分にする（2通りに遷移する）

そして、$Y$ が十分 $X$ に近づいたら、そのときの $|Y-X|$ が「最初に足したり引いたりすべき回数」となる。

まぁ、「十分近づいたら」といっても厳密にどのタイミングかわかりづらいので、「とりあえず訪れた $Y$ があったら毎回 $|Y-X|$ を計算しといて、その中の最小値が答え」としてよい。 調べるのは $X \le Y$ の間だけでよくて、最大でも $\log_2{10^{18}}=60$ 回程度でたどり着ける。

調べることになる状態数を考える。

$Y$ が奇数の時に2通りに遷移するので、最悪の場合 $2^{60}$ 回程度になる？とか一瞬思ってしまうが、このときに遷移する2つの状態は隣り合っているので、多くがかぶる。

例えば、$Y=63$ とすると、

63 → (31, 32) → (15, 16) → (7, 8) → (3, 4) → (1,2) → 0

というように、2で割った回数が同じ数字は、たかだか2つしかない。よって調べる状態数はせいぜい120通りくらいしかない。

Python3

from heapq import heappop, heappush


def solve(x, y):
    if x >= y:
        return x - y
    q = [(0, y)]
    checked = set()
    ans = 10 ** 18
    while q:
        c, v = heappop(q)
        if v in checked:
            continue
        checked.add(v)

        ans = min(ans, c + abs(v - x))

        if v % 2 == 0:
            if v // 2 not in checked:
                heappush(q, (c + 1, v // 2))
        else:
            if v // 2 not in checked:
                heappush(q, (c + 2, v // 2))
            if v // 2 + 1 not in checked:
                heappush(q, (c + 2, v // 2 + 1))

    return ans


x, y = map(int, input().split())

print(solve(x, y))