ARC224 D - Angst for All Pairs

全ペアへの苦悩

考え方

ある数に着目し、各カードにその数が書いてあれば 1、書いていなければ 0 を対応させる。
すると、書き込みパターンは $N$ 桁の二進数で表現できる。
条件の、片方のみが書かれているカードが存在というのは、この二進数が異なることに他ならない。

これに気づけば、ただの簡単な貪欲法である。
$0$ から $2^N-1$ までの書き込みパターンの中で、1 が少ないものを桁数が多い数に割り当てればよい。
1 の個数が $i$ 個である書き込みパターンの個数は、二項係数 ${}_N\mathrm{C}_i$ として求められる。

$0$ から $2^N-1$ までを全部使い切っても足りない場合は、不可能なので $-1$ を出力。

同じ桁数のものをまとめて処理すれば高速であるが、愚直にやっても $O\left(\sum K\right)$ なので十分間に合う。

$1$ つ目のテストケースのみ考える。

入力を受け取る。

n: 3
k: 5

カードを $0$ 枚使う書き込みパターンは ${}_3\mathrm{C}_0=1$ 個ある。
これを最も大きい値 $5$ に割り当てる。
$5$ は $1$ 桁なので、この割り当てによるコストは $0\times1=0$ である。

カードを $1$ 枚使う書き込みパターンは ${}_3\mathrm{C}_1=3$ 個ある。
これらを次に大きい値 $4,3,2$ に割り当てる。
いずれも $1$ 桁なので、コストの合計は $1+1+1=3$ である。

カードを $2$ 枚使う書き込みパターンは ${}_3\mathrm{C}_2=3$ 個ある。
まだ割り当てていない値は $1$ だけなので、そのうち $1$ パターンを値 $1$ に割り当てる。
このコストは $2\times1=2$ である。

以上より、最小の総コストは $0+3+2=5$ となる。

答えは、int 型からはみ出る。
long long 型を用いること。

特になし。