1427 . 卡片遊戲
TopCoder
Tags
Description
汐莉、美胡與比名子正在玩遊戲，現在桌子上一共擺了 $n$ 張卡片，第 $i$ 張卡片有著數字 $a_i$ 與顏色 $c_i$。一開始比名子會先移除一些卡片，讓每一種顏色的卡片都留下恰好一張。之後汐莉跟美胡會輪流進行以下操作，由汐莉先開始，直到桌子上沒有卡片為止：
- 選擇一張卡片，假設該卡片上的數字為 $x$，則將自己的分數增加 $x$ 並將該卡片移除。
兩人的初始分數皆為 $0$，且兩人的目標都是要最大化自己的分數減掉對手的分數。而比名子希望兩人能夠相處融洽，她想要讓兩人的分數差距的絕對值盡量小。在三個人都用最優策略按照自己的目標行動的情況下，你能夠預測最後汐莉跟美胡的分數差的絕對值是多少嗎？
Input Format
輸入第一行有兩個正整數 $n, k$，分別代表有幾張卡片以及卡片有幾種顏色。
輸入第二行有 $n$ 個正整數 $a_1, a_2, \ldots, a_n$，其中 $a_i$ 代表第 $i$ 張卡片上面的數字。
輸入第三行有 $n$ 個正整數 $c_1, c_2, \ldots, c_n$，其中 $c_i$ 代表第 $i$ 張卡片上面的顏色。
- $1 \leq n \leq 5 \times 10^ 5$
- $1 \leq k \leq \min(n, 22)$
- $1 \leq a_i \leq 10^ {15}$
- $1 \leq c_i \leq k$
- 對於所有 $1 \leq i \leq k$，保證至少有一張卡片的顏色為 $i$。
Output Format
輸出一個整數代表在三個人都用最優策略按照自己的目標行動的情況下，汐莉跟美胡的分數差的絕對值。
Sample Input 1
8 4 5 19 1 14 10 11 2 7 1 1 2 2 3 3 4 4
Sample Output 1
5
Sample Input 2
9 9 8 6 4 1 9 7 5 3 2 1 2 3 4 5 6 7 8 9
Sample Output 2
5
Sample Input 3
20 10 135 163 941 505 845 164 44 261 671 70 973 927 319 884 985 24 832 788 79 921 10 3 1 7 8 3 5 4 8 10 8 2 10 2 3 6 5 9 6 1
Sample Output 3
315
Hints
在第一筆範例測資中，若比名子選擇留下這 $4$ 張卡片：
- 顏色 $1$、數字 $5$ 的卡片
- 顏色 $2$、數字 $14$ 的卡片
- 顏色 $3$、數字 $11$ 的卡片
- 顏色 $4$、數字 $7$ 的卡片
這樣一來汐莉與美胡的得分差為 $5$。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資。 | 0 |
| 2 | 0~17 | $n \leq 200, k \leq 18$ | 20 |
| 3 | 0~32 | $k \leq 18$ | 60 |
| 4 | 0~52 | 無額外限制。 | 20 |