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

Posted on Edited on In ,

動機

刷 板中的講義題單 的時候寫到了這一題，發現單純利用 sliding windows 過不了，花了大約四小時的時間去優化它才成功 AC。然後因為想寫題解，所以就順便來寫這一篇紀錄一下。

題意

給你 \(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) \notag\] （\(\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! = 3\,628\,800\)。如果對每次詢問都重新查詢一遍，那複雜度會爛到 \(\mathcal{O}(QP)\)，顯然無法通過。

範例 code 
1
2
3
4
5
6
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\) 的最大值，複雜度是 \(\mathcal{O}(Q \lg P)\)，應該可以拿到 \(51\) 或 \(61\) 分。

滑動窗口

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

常數優化 1

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

範例 code 
1
2
3
4
5
6
7
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，有興趣的人也可以去參考一下。

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

常數優化 3

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

範例 code 
1
2
3
4
5
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