---
tags: Programming Contest
---

# AtCoder Beginner Contest 184 題解

## 心得

排 1057，積分 +46。

前二題很快的解出，第三題想不出來，先跳去解第四、第五題。第四題輕鬆過了，第五題在兩個測資會 TLE，回去解第三題，終於在測資的幫忙下弄出來了，最後一點時間將第五題的程式優化，在第 99 分鐘 AC，雖然是假解 XD。第六題也是能解的題目，第三、第五題卡太久了。

拼到最後真的累。

source: 點兔第三季

## A, B

略

## C. [Super Ryuma](https://atcoder.jp/contests/abc184/tasks/abc184_c)

情況還挺複雜的，但範測給得很完整，基本上各個方法都出現了。

方法有以下幾種：

1. 題目所述 1 步。
2. 二個斜線可到的位置。
3. 一步到相鄰點再走一步。
4. 剩下的所有位置都可以用 3 步走到（走二個斜線再走一步）。

def in_one_step(r1, c1, r2, c2):
    return r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2 or abs(r1 - r2) + abs(c1 - c2) <= 3

r1, c1 = map(int, input().split())
r2, c2 = map(int, input().split())

if r1 == r2 and c1 == c2:
    print(0)
elif in_one_step(r1, c1, r2, c2):
    print(1)
elif (abs(r2 - r1) % 2 + abs(c2 - c1) % 2) % 2 == 0:
    print(2)
else:
    adjs = [(r, c) for r in range(r1 - 2, r1 + 3) for c in range(c1 - 2, c1 + 3)]
    adjs.append((r1 - 3, c1))
    adjs.append((r1 + 3, c1))
    adjs.append((r1, c1 - 3))
    adjs.append((r1, c1 + 3))
    if any(in_one_step(r, c, r2, c2) for (r, c) in adjs):
        print(2)
    else:
        print(3)

## D. [increment of coins](https://atcoder.jp/contests/abc184/tasks/abc184_d)

有寫過 AtCoder DP Contest 的 [Sushi](https://hackmd.io/@amoshyc/BJu3KvntP#J-Sushi) 應該都能解出這題，這題就只是簡單版。

設 $E(a, b, c)$ 代表將 $(a, b, c)$ 其中一個到達 $100$ 所需的期望操作次數。
明顯若 $a, b, c$ 有任一個已經達成，那所需次數為 $0$。

考慮下一次操作：

1. $\frac{a}{a + b + c}$ 的機率選到 a coins，操作結束後，a coins 增加了一個，我們轉移至 $E(a + 1, b, c)$。
2. $\frac{b}{a + b + c}$ 的機率選到 b coins，操作結束後，b coins 增加了一個，我們轉移至 $E(a, b + 1, c)$。
3. $\frac{c}{a + b + c}$ 的機率選到 c coins，操作結束後，c coins 增加了一個，我們轉移至 $E(a, b, c + 1)$。

因為是 top-down dp，所以採用 c++ 來實作。

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

using real = long double;

real dp[111][111][111];

real E(int a, int b, int c) {
    if (dp[a][b][c] >= 0) {
        return dp[a][b][c];
    }

    if (a >= 100 or b >= 100 or c >= 100) {
        dp[a][b][c] = 0;
        return dp[a][b][c];
    }

    real res = 1;
    res += real(a) / real(a + b + c) * E(a + 1, b, c);
    res += real(b) / real(a + b + c) * E(a, b + 1, c);
    res += real(c) / real(a + b + c) * E(a, b, c + 1);
    
    dp[a][b][c] = res;
    return res;
}

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

    int a, b, c;
    cin >> a >> b >> c;

    for (int i = 0; i < 111; i++) {
        for (int j = 0; j < 111; j++) {
            for (int k = 0; k < 111; k++) {
                dp[i][j][k] = -1.0;
            }
        }
    }

    cout << fixed << setprecision(15) << E(a, b, c) << endl;

    return 0;
}

## E. [Third Avenue](https://atcoder.jp/contests/abc184/tasks/abc184_e)

大家都能想出這是 BFS，但裸著刻會在三筆測資 TLE，這題最重要的是**剪枝**。

當局面每一格都是同樣字母時，若是標準的 BFS，我們在每一格都會對其他所有格（因為是同樣的字母）檢查是否有走過，因此會 TLE。剪枝的部份在於：假設我們將某字母 $a$ 的格子都走完後，我們再遇到 $a$ 時就不用再檢查這些跳躍的相鄰格是否有走過了，因為**已經走過了**。少掉這部份的檢查能讓時間從 2255ms 變成 274ms。

實作上我們可以將該字母的跳躍相鄰格清空（第 68 行）。

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

int dr[] = {-1, +1, 0, 0};
int dc[] = {0, 0, -1, +1};

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

    int H, W;
    cin >> H >> W;

    int sr, sc;
    int gr, gc;
    vector<tuple<int, int>> jumps[26];
    vector<string> A(H);
    for (int r = 0; r < H; r++) {
        cin >> A[r];
        for (int c = 0; c < W; c++) {
            if (A[r][c] == 'S') {
                sr = r;
                sc = c;
            } else if (A[r][c] == 'G') {
                gr = r;
                gc = c;
            } else if ('a' <= A[r][c] and A[r][c] <= 'z') {
                jumps[A[r][c] - 'a'].push_back({r, c});
            }
        }
    }

    queue<tuple<int, int, int>> que;
    vector<vector<int>> dis(H, vector<int>(W, -1));

    dis[sr][sc] = 0;
    que.push({sr, sc, 0});

    while (!que.empty()) {
        auto [r, c, d] = que.front();
        que.pop();

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 or nr >= H)
                continue;
            if (nc < 0 or nc >= W)
                continue;
            if (A[nr][nc] == '#')
                continue;
            if (dis[nr][nc] != -1)
                continue;
            dis[nr][nc] = d + 1;
            que.push({nr, nc, d + 1});
        }

        if ('a' <= A[r][c] and A[r][c] <= 'z') {
            for (auto [nr, nc] : jumps[A[r][c] - 'a']) {
                if (dis[nr][nc] == -1) {
                    dis[nr][nc] = d + 1;
                    que.push({nr, nc, d + 1});
                }
            }
            jumps[A[r][c] - 'a'].clear();
        }
    }

    cout << dis[gr][gc] << endl;

    return 0;
}

## F. [Programming Contest](https://atcoder.jp/contests/abc184/tasks/abc184_f)

注意到 $N$ 很小，但 $T, A_i$ 都很大，所以將之視為背包的作法不可行，讓我們考慮 dp 以外的作法。

可以發現這是標準的折半完全列舉，實作上用 set 或 vector 都可以，但後者會快上非常多。

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

using ll = long long;

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

    ll N, T;
    cin >> N >> T;

    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    int N1 = N / 2;
    int N2 = N - N1;

    vector<ll> s1;
    for (int mask = 0; mask < (1 << N1); mask++) {
        ll sum = 0;
        for (int i = 0; i < N1; i++) {
            if (mask & (1 << i)) {
                sum += A[i];
            }
        }
        s1.push_back(sum);
    }

    vector<ll> s2;
    for (int mask = 0; mask < (1 << N2); mask++) {
        ll sum = 0;
        for (int i = 0; i < N2; i++) {
            if (mask & (1 << i)) {
                sum += A[N1 + i];
            }
        }
        s2.push_back(sum);
    }

    sort(s2.begin(), s2.end());

    ll ans = -1;
    for (auto sum1 : s1) {
        auto ub = upper_bound(s2.begin(), s2.end(), T - sum1);
        if (ub != s2.begin()) {
            ll sum2 = *(--ub);
            ans = max(ans, sum1 + sum2);
        }
    }

    cout << ans << endl;

    return 0;
}

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