---
tags: Programming Contest
---

# AtCoder Regular Contest 109 題解

## 心得

賽後寫的。

## A. [Hands](https://atcoder.jp/contests/arc109/tasks/arc109_a)

第一直覺就 Dijsktra 模板用起來，不過既然是賽後才寫還是慢慢想吧，第一題不太可能是模板題。

可以發現對 b 來說，向下一層樓有兩種路線：

1. 直接往下，成本 `y`。
2. 透過水平的通道到 A 樓，再走斜著的通道回 B，成本 `2x`。

因此若 `a < b`，最小成本就是 `x + (b - a) * min(y, 2 * x)`。而 `a > b` 時也可以類推，不過因為有斜著的通道，向上時會少走一個樓層。

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

if a == b:
    print(x)
elif a > b: # b go up
    print(x + (a - 1 - b) * min(2 * x, y))
else: # b go down
    print(x + (b - a) * min(2 * x, y))

## B. [log](https://atcoder.jp/contests/arc109/tasks/arc109_b)

題目即為最小化丟棄的總和，一個想法是有長度為 $l$ 的 log 的需求，我就買長度為 $l$ 的 log，但明顯我們又需要買長度為 $n + 1$ 的那個 log，因此想到可以將 $n + 1$ 分解成需求中最小的那 $x$ 個。例如 `n = 8`，最佳的買法為 `8, 7, 6, 5, 4, 9`。最後的那個 `9` 會被分解成 `3, 2, 1, 丟棄`。

所以題目變成求 $x$ 是多少？根據上述想法，我們可以列出不等式：

$$
1 + 2 + 3 + \cdots + x \le n + 1
$$

可求出 $x = \lfloor \frac{\sqrt{8n + 9} - 1}{2} \rfloor$。而購買花費為 $n - x + 1$。

實作上如果直接用 float 算會因浮點誤差 WA，可以轉用 python 的 decimals 或用二分搜求出 $x$。

from decimal import Decimal
n = int(input())
x = int((Decimal(8 * n + 9).sqrt() - 1) // 2)
print(n - x + 1)

# max x such that x * (x + 1) / 2 <= n + 1
n = int(input())
lb, ub = 0, n + 1
while ub - lb > 1:
    m = (lb + ub) // 2
    if (m + 1) * m // 2 <= n + 1:
        lb = m
    else:
        ub = m
x = lb
print(n - x + 1)

## C. [Large RPS Tournament](https://atcoder.jp/contests/arc109/tasks/arc109_c)

這題很有趣，基於以下觀察：

1. 區間的長度是 2 的指數。
2. Players $[a, b)$ 之間的比賽結果等價於 $[a \bmod n, b \bmod n)$ 的比賽結果。

第一點讓我想到倍方法：設 $dp[i, r]$ 代表 players $[r, r + 2^i)$ 的比賽結果。

題目所求為 $dp[k, 0]$。根據題意 $dp[0, r] = s[r \bmod n]$。

如同標準的倍方法，我們可以寫出轉移：

$$
dp[i, r] = judge(dp[i - 1, r], dp[i - 1, r + 2^{i-1}])
$$

$judge$ 是取出他們的 winner。$r + 2^{i-1}$ 會是一個極大的值，但因為第二點，可以寫成：

$$
dp[i, r] = judge(dp[i - 1, r], dp[i - 1, (r + 2^{i-1}) \bmod n])
$$

所以 dp 的維度只需 $(k+1) \times n$。

n, k = map(int, input().split())
s = input()

def judge(a, b):
    if (a, b) in [('R', 'S'), ('P', 'R'), ('S', 'P')]:
        return a
    else:
        return b

# dp[i, r] = fav hand of winner of [r, r + 2**i)
dp = [[None for _ in range(n)] for _ in range(k + 1)]
for r in range(n):
    dp[0][r] = s[r % n]
for i in range(1, k + 1):
    for r in range(n):
        dp[i][r] = judge(dp[i - 1][r], dp[i - 1][(r + 2 ** (i - 1)) % n])
print(dp[k][0])

## D. []()

想不出來，等題解。

:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::