ARC229 F - Angst for All Pairs 2
全ペアへの苦悩2
考え方
まず、$1$ と $2$ を選んだら条件違反になるケースを考える。
すぐに思いつくのは、$1$ も $2$ もどこにもないケース。
これは明らかに違反している。
さらに、$1$ があるのに違反しているケースもある。
この場合、$1$ があるカードを選んでも違反なのだから、$2$ もそのカードにあるはず。
すると $2$ が書いてあるカードが存在することになり、逆のこともいえる。
つまり、$1$ または $2$ が書いてあるカードが全て $1$ と $2$ の組であると条件違反である。
とはいえ、全く同一のカードを $2$ つ用意する意味はない。
したがって、実質的に、唯一の $1$ と唯一の $2$ が同じカードに書かれている場合ということになる。
これが、$1$ と書かれたカードがあるのに条件違反になる唯一のケース。
そして、この $2$ つ以外はどんな場合でも $1$ と $2$ を選んだら条件違反になるケースはない。
ということは、条件は以下のように言い換えることができる。
- $1$ つも書かれていない数は、高々 $1$ つまで
- $1$ つしか書かれていない数同士がペアになってはいけない
この言い換えをしたうえで、最小コストを考えよう。
ソートをすることで、数が小さい方がコストが少ない（あるいは等しい）と思ってよい。
その前提で、いくつかの貪欲法が成立する。
まず、$2$ 以上の数を $3$ 回以上使う意味はない。
そのうち $1$ つを $1$ に変えれば、条件を壊さずに結果を同等以上にできる。
さらに、コスト最大の数を $1$ 回以上使う意味もない。
他に未使用の数があればその数に、なければ $1$ に変えれば、条件を壊さずに結果を同等以上にできる。
そして、$2$ を $1$ 回しか使わないのに $3$ を $2$ 回使うようなものも考えなくてよい。
この場合、$2$ と $3$ をまるごと入れ替えれば、条件を壊さずに結果を同等以上にできる。
ということで、$2$ 以上の使用回数を数列にすると、途中まで $2$、途中から $1$、最後だけ $0$ という列になる。
この貪欲条件を採用すると、あり得るパターンは限られる。
例えば数が $11$ までだとしよう。
使用回数が $\{?,1,1,1,1,1,1,1,1,1,0\}$ なら、唯一同士を組にできないので以下のようになる。
| カード1 | カード2 | カード3 | カード4 | カード5 | カード6 | カード7 | カード8 | カード9 | |
|---|---|---|---|---|---|---|---|---|---|
| 表 | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ |
| 裏 | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
使用回数が $\{?,2,1,1,1,1,1,1,1,1,0\}$ なら、以下のようになる。
| カード1 | カード2 | カード3 | カード4 | カード5 | カード6 | カード7 | カード8 | |
|---|---|---|---|---|---|---|---|---|
| 表 | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $2$ | $2$ |
| 裏 | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
使用回数が $\{?,2,2,1,1,1,1,1,1,1,0\}$ なら、以下のようになる。
| カード1 | カード2 | カード3 | カード4 | カード5 | カード6 | カード7 | |
|---|---|---|---|---|---|---|---|
| 表 | $1$ | $1$ | $1$ | $2$ | $2$ | $3$ | $3$ |
| 裏 | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
つまり、$2$ 以上の安い方から順に、$1$ を $3$ つ消してその数を $1$ 増やすことができると考えられる。
これは $1$ の残り個数が $2$ 個以上残る範囲で実行できる。
よって、この調査で最小値を探せばよい。
凸関数であるため、$2$ 回使用の個数が少ない順に調査し、最小値記録更新失敗した時点で打ち切ってよい。
これで解答……と思いきや、コーナーケースが存在する。
$N=2$ の場合には、この方法ではカードが $0$ 枚ということになってしまう。
よって、$1-1$ のペアを $1$ 枚特別に用意する必要がある。
$N=3$ の場合には、この方法だと $1-2$ ペア $1$ 枚だけになって条件違反。
よって、$1-1$ のペアを $1$ 枚特別に用意する必要がある。
これらの対応をすれば完了。
計算量はソート部分が支配的で $O(N\log N)$ である。
入力例1での動作
入力例1の $1$ 番目と $3$ 番目のテストケースを考える。
まず、$1$ 番目のテストケースを考える。
入力を受け取る。
n: 3
a: {3, 2, 5}コストを昇順にソートすると $\{2,3,5\}$ となる。
通常の形では、最大コストの数を使わず、中央のコスト $3$ を $1$ 回、最小コスト $2$ を $N-2=1$ 回使う。
この時点のコストは $3+2=5$ である。
しかし、$N=3$ ではこれだけだと、使用回数が $1$ 回の数同士だけを組にしたカード $1$ 枚になってしまう。
そこで最小コストの数を両面に書いたカードを $1$ 枚追加する。
追加コストは $2\times2=4$ なので、答えは $5+4=9$ となる。
次に、$3$ 番目のテストケースを考える。
入力を受け取る。
n: 7
a: {12, 42, 21, 10, 29, 33, 18}コストを昇順にソートすると $\{10,12,18,21,29,33,42\}$ となる。
まず、最大コスト $42$ の数を $0$ 回、最小コスト $10$ の数を $N-2=5$ 回、残りを $1$ 回ずつ使う。
コストは $12+18+21+29+33+10\times5=163$ である。
ここから、最小コスト $10$ の数 $3$ 回の代わりに、次に安いコスト $12$ の数をもう $1$ 回使うことを考える。
コストは $10\times3=30$ から $12$ になるため、$18$ 改善する。
したがって、答えは $163-18=145$ となる。
注意点
答えは int 型からはみ出る。
long long 型を用いること。
別解
特になし。