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

result=0 とする。

まず、$i=0$ の場合を考える。
カードを $0$ 枚使うパターンは、${}_3\mathrm{C}_0=1$ 個ある。
このパターンを、まだ割り当てていない最大の値 5 に割り当てる。

カードを $0$ 枚使い、5 は $1$ 桁なので、result に $0\times 1=0$ を加える。
k=4 となる。

次に、$i=1$ の場合を考える。
カードを $1$ 枚使うパターンは、${}_3\mathrm{C}_1=3$ 個ある。
これらを、4, 3, 2 に割り当てる。

いずれも $1$ 桁なので、result に、

$$
1\times 1+1\times 1+1\times 1=3
$$

を加える。
result=3, k=1 となる。

次に、$i=2$ の場合を考える。
カードを $2$ 枚使うパターンは、${}_3\mathrm{C}_2=3$ 個ある。
しかし、まだ割り当てていない値は 1 だけなので、$1$ パターンだけ使用する。

1 は $1$ 桁なので、result に $2\times 1=2$ を加える。
result=5, k=0 となる。

すべての値への割り当てが終わったので、答えは $5$ である。

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

特になし。