[AtCoder] ABC 159 D – Banned K

問題

方針

\( k \) 番目のボールを除いたときに整数が等しいような異なる \( 2 \) つのボールを選び出す方法の数が変化する整数は、\( A_k \) だけなので、全体の組み合わせから \( A_k \) の値を引くような方針で考えます。\( b(x) \) を整数 \( x \) の個数とすると、整数 \( x \) の選び方は、

\[ \dfrac{b(x)(b(x) – 1)}{2}\]

となります。したがって、\( N \) 個のボールに対する整数が等しいような異なる \( 2 \) つのボールを選び出す方法の数を \( s \) とすると、\( k \) 番目のボールを取り除くと、

\[s – \dfrac{b(A_k)(b(A_k) – 1)}{2} + \dfrac{(b(A_k) – 1)(b(A_k) – 2)}{2}\]

となります。

コード