---
tags: Editorial
---

# ZeroJudge c272. 趙哥的養成計畫 I --- 題解

### 題意

[題目連結](https://zerojudge.tw/ShowProblem?problemid=c272)

給你 $N$ ($N \le 10$) 個數字 $A_1 \sim A_N$ ($|A_i| \le 10^6$) 跟一個計分函式 $score(i) = A_{\sigma_i} \times (M - \min\{i, M + 1\} + 1)$ ($\sigma$ 是一個 $1 \sim N$ 的排列)，接著有 $Q$ ($Q \le 10^6$) 次詢問，請找出在分數不超過 $qs$ ($-2^{46} < qs < 2^{25}$) 的前提下最多可以拿多少分。

### 暴力做法

首先，C++ 裡可以透過 `std::next_permutation` 來找到所有排列，再依序計算出每個排列的分數。因為 $N \le 10$，所以排列個數 $P \le 10! = 3628800$。如果對每次詢問都重新查詢一遍，那複雜度會爛到 $O(QP)$，顯然無法通過。

int A[N];
for (int i = 0; i < N; ++i) cin >> A[i];
sort(A, A + N);
do {
    /* calculate score */
} while (next_permutation(A, A + N));

### 二分搜

不過因為每次詢問的排列都是相同的，先把所有排列的分數處理出來再利用二分搜 (或直接用 `std::prev(std::upper_bound)`) 得到第一個 $\le qs$ 的最大值，複雜度是 $O(Q \lg P)$，應該可以拿到 51 或 61 分。

### 滑動窗口

這樣還是太慢了，觀察到 $qs$ 越大相應的答案就越大，考慮把所有詢問先拿出來排序，最後利用 sliding windows 的方法維護答案，複雜度是 $O(Q \lg Q + P)$，還是只能拿到 51 或 61 分。

### 常數優化 1

分數的最大值不會超過 $\max\{A_i\} \times M \le 10^7$，所以不用使用 `long long`，可以用 `int` 處理就好，但要注意的是 $qs$ 的範圍會到 `long long`，可以先把他判斷掉。

long long qs;
vector<pair<int, int>> query(Q);
for (int i = 0; i < Q; ++i) {
    cin >> qs;
    if (qs < all_score[0]) qs = all_score[0] - 1;
    query[i].first = qs, query[i].second = i;
}

### 常數優化 2

把所有 vector 都拔掉換成一般的 array、把區域變數開到全域、開 `#pragma GCC optimize("Ofast", "unroll-loops")`。

### I/O 優化

因為輸入大約有 $6 \times 10^6$ 個字元，輸出可能會到 $2.5 \times 10^7$ 個字元 (假設都是 `Case #xxxxx` 跟 `No Solution!`)，所以需要進行「適量」的優化。輸入跟輸出就選擇使用 `read()` 跟 `write()` 從 buffer 裡面一次讀進來跟印出去。

我的 I/O 模板是參考 FHVirus 的[這篇 Blog](https://fhvirus.github.io/blog/2020/fhvirus-io/)，有興趣的人也可以去參考一下。

另外就是如果你是使用 `getchar()` 跟 `putchar()` 會拿到 74 分，使用 `getchar_unlocked()` 跟 `putchar_unlocked()` 也可以拿到滿分。

### 常數優化 3

因為不知道出題人是怎麼把空間壓到只有 1.5 MB 的，所以就嘗試只當連續枚舉的答案不相同時才把答案加入陣列中，並把原本的滑動窗口改成二分搜，意外的直接拿到 TopCoder。

do {
    int score = 0;
    for (int i = 0; i < M; ++i) score += A[i] * (M - i);
    if (score != all_score[all_score_sz-1]) all_score[all_score_sz++] = score;
} while (next_permutation(A, A + N));

這個方法只要 $N = M = 10$ 就可以輕鬆卡掉，測資竟然沒出滿 OAO！

### AC code

- 滑動窗口：https://github.com/SorahISA/competitive_programming/blob/master/ZeroJudge/c/c272-1.cpp
- 二分搜：https://github.com/SorahISA/competitive_programming/blob/master/ZeroJudge/c/c272-2.cpp