---
tags: Programming Contest
---

# AtCoder Beginner Contest 180 題解

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

## 心得

賽後才來寫的，這場比賽跟 cf 連在一起，所以就沒打這場了。

## A, B, C

都是水題。
聽說第二題會卡 double，得用 long double 才會過，用 python 的表示有這回事嗎 ¯\(°_o)/¯

## D. Takahashi Unevolved

一開始我的想法是 greedy，看第一種操作還是第二種操作產出來的數字小就用哪種，但這樣會 TLE。重新看題目發現 A >= 2 這個條件，這代表說我如果全部都用第一種，那時間是 O(lgY)。

於是我的想法修正成：一次第一種操作等價於（最多）幾次第二種操作？假設是 k 次，只要 k >= 1 那代表我用 k 次第二種操作比較好，要不然還是用一次第一種操作。我不斷重覆上述流程，直到 X 再也不能更大為止。

k 可以透過解不等式 $X + kB \le X \cdot A$ 求得，小心別讓 $X + kB \ge Y$ 了（也就是說要保證 $X + kB < Y$）。

X, Y, A, B = map(int, input().split())

ans = 0
while True:
    if min(X * A, X + B) >= Y:
        break
    k = (min(X * A, Y - 1) - X) // B
    if k >= 1:
        X = X + k * B
        ans += k
    else:
        X = X * A
        ans += 1
print(ans)

AC 後看了其他人的 code 才發現有「一定會先用第一種操作才會用第二種操作」這樣的性質。

## E. Traveling Salesman among Aerial Cities

第二筆測資的另一個答案為 [1, 2, 3, 1]，不需要走到一個城市多次。因為給定的距離函式且足三角不等式 $dist(city_u, city_v) \le dist(city_u, city_k) + dist(city_k, city_v)$，所以這題等價標準的 TSP。若不滿足的話，我們得先 floyd warshall 把城市之間的最短距離找出來再跑 TSP。

我個人習慣的 TSP 寫法是用 bitmask dp 求出 Hamiltonian Path，最後再看看「停在城市 $v$ 的 Hamiltonian Path 加上從該城市到起始點的距離」的最小值是多少。

設 $dp[S, v]$ 代表我們走過的城市集合是 $S$，且我們最後停在城市 $v$ 的 minimum cost。考慮城市 $v$ 的上一個城市 $u$ 是那些，即我們是從哪些城市走過來的，我們可以得到以下轉移方程：

$$
dp[S, v] = \min_{u \in S} dp[S - \{v\}, u] + dist(city_u, city_v)
$$

其中 $-$ 是集合的差運算。

該 dp 的初使化為每項都是無窮大，除了 $dp[\{1\}, 1] = 0$，因為我們一開始就在城市 1。

「停在城市 $v$ 的 Hamiltonian Path」就是 $dp[\{1, 2, \cdots, N\}, v]$，如果此值再加上城市 $v$ 到城市 $1$ 的距離 $dist(city_v, city_1)$，那就是對應的 Hamiltonian Cycle。

於是題目所求就是：

$$
\min_v dp[\{1, 2, \cdots, N\}, v] + dist(city_v, city_1)
$$

實作上使用 0-based index，且用 bitmask 來表示集合，整體時間 $O(2^N \cdot N^2)$。
使用 c++ 或 pypy 都可以過，以下給出 c++ 的程式碼。

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

using ll = long long;
using City = tuple<ll, ll, ll>;

ll dist(City city1, City city2) {
    auto [a, b, c] = city1;
    auto [p, q, r] = city2;
    return abs(p - a) + abs(q - b) + max(0ll, r - c);
}

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

    int N;
    cin >> N;
    vector<City> cities;
    for (int i = 0; i < N; i++) {
        ll x, y, z;
        cin >> x >> y >> z;
        cities.push_back({x, y, z});
    }

    const ll inf = 1e15;
    auto dp = vector<vector<ll>>(1 << N, vector<ll>(N, inf));

    dp[1 << 0][0] = 0;

    for (int s = 1; s < (1 << N); s++) {
        for (int v = 0; v < N; v++) {
            if (s & (1 << v)) {
                for (int u = 0; u < N; u++) {
                    if (s & (1 << u)) {
                        ll val = dp[s ^ (1 << v)][u] + dist(cities[u], cities[v]);
                        dp[s][v] = min(dp[s][v], val);
                    }
                }
            }
        }
    }

    ll ans = inf;
    for (int v = 0; v < N; v++) {
        ans = min(ans, dp[(1 << N) - 1][v] + dist(cities[v], cities[0]));
    }
    cout << ans << endl;

    return 0;
}

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