---
tags: Programming Contest
---

# AtCoder Beginner Contest 175 題解

[題目連結](https://atcoder.jp/contests/abc175/tasks)

## 心得

C 鬼打牆卡了好久，打錯變數…只解出三題，大扣分。就算賽後寫起來，我還是覺得這回偏難啊。

## A, B

簽到。

## C. Walking Takahashi

假設我們想找到 $f(t; X, D) = |X + tD|$ 的最小值，其中 $t \in [lb, ub], t \in \mathbb{Z}$，我們可以在 $O(1)$ 時間算出：因為這是一個一次絕對值函式，極值要嘛發生在端點，要嘛發生在使 $f(t) = 0$ 的附近，所以我們就將 $t=lb, t=ub, t = \lfloor \frac{-X}{D} \rfloor, t=\lceil \frac{-X}{D} \rceil$ 這四個值代入 $f(t; X, D)$ 看最小是多少。

當 $K$ 是偶數時，可能的位置是從 X 出發，一次移動 $2D$ 的距離，只能移動 $K/2$ 次，這對應了 $f(t; X, D), t \in [-\frac{K}{2}, +\frac{K}{2}]$。

當 $K$ 是奇數時，我們先移動一次（到 $X + D$ 或 $X - D$），剩餘移動次數是偶數次，就用是偶數時的解法來做。

from math import floor, ceil

def solve(X, D, lb, ub):
    # min abs(X + t * D) (lb <= t <= ub) (lb, ub, t are int)
    ts = [
        lb,
        ub,
        max(min(floor(-X / D), ub), lb),
        max(min(ceil(-X / D), ub), lb),
    ]
    return min([abs(X + t * D) for t in ts])

X, K, D = map(int, input().split())
if K % 2 == 0:
    ans = solve(X, D * 2, -(K // 2), +(K // 2))
else:
    ans1 = solve(X + D, D * 2, -((K + 1) // 2), +((K - 1)) // 2)
    ans2 = solve(X - D, D * 2, -((K - 1) // 2), +((K + 1)) // 2)
    ans = min(ans1, ans2)
print(ans)

## D. Moving Piece

題目說得有點繞口，基本上就是說給一個由 permutation 形成的 graph，每個節點都有個數字，你可以任選一個位置開始，走最多 K 步，你的得分是經過的那些節點的數字和，求最大可以是多少。

由 permutation 構成的的 graph，這種 graphy 的特點就是整個 graph 可以分解成一個或多個環。現在問題是我們要選哪個點開始，與要走幾步。

假設我們枚舉每個節點，也枚舉可能的步數，那這樣明顯會 TLE。一個有趣的觀察是我們不用真的考慮所有的可能步數 [1, K]。假設節點 v 所在的環長度是 L，數字和是 S。我們可以將所有可能的步數 [1, K] 寫成 q * L + r 的型式：

<0L + r>: 0L + 1, 0L + 2, ..., 0L + L
<1L + r>: 1L + 1, 1L + 2, ..., 1L + L
    ⋮ 
<tL + r>: tL + 1, tL + 2, ...

當 S > 0，我們不用去考慮步數 `<0L + r>`, `<1L + r>`, `...`, `<(t - 1>)L + r`，因為步數 `<tL + r>` 的數字和一定比他們大。所以我們只需檢查型式如 `<tL + r>` 的那些步數。

當 S <= 0，我們不用去考慮步數 `<1L + r>`, `<2L + r>`, `...`, `<tL + r>`，因為步數 `<0L + r>` 的數字和一定最大。所以我們只需檢查型式如 `<0L + r>` 的那些步數。

枚舉步數的時間 **amortized** 下去是 $O(N)$，再加上枚舉點的 $O(N)$，整體時間只有 $O(N)$。
實作上有點複雜，要注意 K < L 的情況，以下為使用 pypy 的 AC Code:

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))

vis = [False] * N
ans = [-float('inf')] * N

for root in range(N):
    if vis[root]:
        continue

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]
    
    for u in cycle:
        vis[u] = True

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        if S > 0:
            rem_cost = 0
            for rem in range(1, min(L, K) + 1):
                rem_cost += costs[(i + rem) % L]
                t = (K - rem) // L
                ans[v] = max(ans[v], rem_cost + t * S)
        else:
            rem_cost = 0
            for rem in range(1, min(L, K) + 1):
                rem_cost += costs[(i + rem) % L]
                ans[v] = max(ans[v], rem_cost)

print(max(ans))

## E. Picking Goods

因為官方題解沒有出來，這是我研究別人 AC Code 所得出的題解，請注意。


設 `dp[r, c, p]` = 走到 (r, c) 時，所能得到的最大價值和，且 (r, c) 及以左的格子所撿的物件數量為 p。如圖 (1) 所示，走至青綠色格子時，深綠色與青綠色的格子中所撿的物件數為 p。題目所求是 `max(dp[R - 1][C - 1][p] for p in [0, 3])`

這題的轉移方程用 **遞推** 方式來想會簡單許多。考慮在 (r, c) 時，我們可以向下走或向右走，再考慮要不要撿起，我們有四種情況：

1. walk down and pick (if there's an item)
2. walk down and don't pick
3. walk right and pick (if there's an item)
4. walk right and don't pick

情況 1, 2 對應圖 (2)，情況 3, 4 對應圖 (3)。我們從青綠色格子移動至紅色格子。

**當向下走時，代表我們放棄了圖 (2) 中橘色區域的那些物件**。也就是說情況 1 我們一定轉移至 `dp[r + 1, c, 1]`，不管我們是 `dp[r, c, 0]`, `dp[r, c, 1`] 還是 `dp[r, c, p]`。同理，情況 2 一定會轉移至 `dp[r + 1, c, 0]`，無關 row r 撿了多少物件。

當向右走時，就是標準的 dp 了。情況 3，讓我們從 `dp[r, c, p]` 轉移至 `dp[r, c + 1, p + 1]`；情況 4，從 `dp[r, c, p]` 轉移至 `dp[r, c + 1, p]`。

以下給出 C++ 的 AC Code：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

ll solve() {
    int R, C, K;
    cin >> R >> C >> K;

    auto A = vector<vector<ll>>(R + 1, vector<ll>(C + 1, 0));
    for (int k = 0; k < K; k++) {
        int r, c, v; cin >> r >> c >> v; r--; c--;
        A[r][c] = v;
    }

    auto dp = vector<vector<vector<ll>>>(R + 1, 
                vector<vector<ll>>(C + 1, 
                    vector<ll>(5, 0)));
    
    dp[0][0][1] = ((A[0][0] > 0) ? A[0][0] : 0);
    
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            for (int p = 0; p < 4; p++) {
                // walk down and pick
                if (A[r + 1][c] > 0) {
                    dp[r + 1][c][1] = max(
                        dp[r + 1][c][1], 
                        dp[r][c][p] + A[r + 1][c]
                    );
                }
                // walk down and don't pick
                dp[r + 1][c][0] = max(
                    dp[r + 1][c][0], 
                    dp[r][c][p]
                );
                // walk right and pick
                if (A[r][c + 1] > 0) {
                    dp[r][c + 1][p + 1] = max(
                        dp[r][c + 1][p + 1], 
                        dp[r][c][p] + A[r][c + 1]
                    );
                }
                // walk right and don't pick
                dp[r][c + 1][p] = max(
                    dp[r][c + 1][p], 
                    dp[r][c][p]
                );
            }
        }
    }

    return *max_element(dp[R - 1][C - 1].begin(), dp[R - 1][C - 1].begin() + 4);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << solve() << endl;

    return 0;
}

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