C++ STLコンテナmapを用いてABC159 D問題を解く

競技プログラミングの備忘録用
今回はSTLコンテナmapを用いてABC159 D問題を解く．

[D - Banned K](https://atcoder.jp/contests/abc159/tasks/abc159_d)

###問題文
ボールが$N$個あり，$i$番目のボールには整数$A_i$が書かれています。
$k=1,2,...,N$に対して以下の問題を解いて、答えをそれぞれ出力してください。
$k$番目のボールを除いた$N−1$個のボールから、書かれている整数が等しいような異なる$2$つのボールを選び出す方法の数を求めてください。選ぶ順序は考慮しません。

###制約
- $3≤N≤2×10^5$
- $1≤A_i≤N$
- 入力はすべて整数である。

###入力例
```
5
1 1 2 1 2
```
###出力例
```
2
2
3
2
3
```
###方針
入力例を用いて考える．
入力例の場合，同じ数字のペアを作るすべての組み合わせの総数は1が3つ，2が2つあるため，3C2+2C2=3+1=4より4通りとなる．
ここで1番目以外の数字から同じ数字のペアを作る組み合わせの総数は1が2つ，2が2つあるため，2C2+2C2=1+1=2より2通りとなる．
この場合の組み合わせの減少数は3C2-2C2=3-1=2となる．
これを一般化して考えると,k番目の数字が数列中にn個存在すると仮定すると，k番目の数字以外から同じ数のペアを作る組み合わせの数は，ペアを作ることができるすべての組み合わせの総数からnC2-n-1C2を引けば求めることができる．
ここでnC2-n-1C2を展開すると以下のようになる．

```math
\begin{align}
_n C_2- _{n-1} C_2 = &\frac{n(n-1)}{2}-\frac{(n-1)(n-2)}{2}\\
\\
= &\frac{2(n-1)}{2}\\
\\
= &n-1
\end{align}
```
よって本問題の解法ををまとめると

- 全てのペアを作ることができる組み合わせの総数を求める．
- k番目の値以外のペアの組み合わせの総数を求めるときはk番目の値の個数-1を全てのペアの総数から引く
- これを全ての種類の数について実行

###mapの宣言
```c++
map<ll, ll> value_count;
```
keyと値が両方long long型のmapを宣言する．
value_countは数の種類別に数列中の個数をカウントする．

###値の有無を確認し値が存在するときは個数をインクリメント存在しないときは個数を1にセットする
```c++
if(value_count.count(A.at(i))){
    value_count[A.at(i)]++;
}
else{
    value_count[A.at(i)]=1;
}
```

###map内の要素を走査して全ての組み合わせ数を求める
```c++

for(auto i=value_count.begin(); i!=value_count.end(); i++){
    all_conbination+=i->second*(i->second-1)/2;
}
```
ここでのall_conbinationは全ての数の組み合わせ数

###k番目の数の個数-1を全ての組み合わせ数から引き出力する．
```c++
for(int i=0; i<N; i++){
    cout << all_conbination-value_count[A.at(i)]+1 << endl;
}
```
A.at(i)は入力された数列の各要素を表している．

解法コード

```c++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (ll i=0; i<(ll)(n); i++)
#define repd(i,n) for (ll i=n-1; i>=0; i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define PB push_back

int main()
{
    ll N; cin >> N;
    map<ll, ll> value_count;
    vector<ll> A(N);
    rep(i, N){
        cin >> A.at(i);
        if(value_count.count(A.at(i))){
            value_count[A.at(i)]++;
        }
        else{
            value_count[A.at(i)]=1;
        }
    }
    ll all_conbination=0;
    for(auto i=value_count.begin(); i!=value_count.end(); i++){
        all_conbination+=i->S*(i->S-1)/2;
    }
    rep(i,N)
        cout << all_conbination-value_count[A.at(i)]+1 << endl;
}
```
追記
mapコンテナは新たなkeyを追加するときデフォルトでkeyに紐づく値を0にして追加してくれるそう.
これを踏まえると以下のコードの条件分岐は必要なくなる.

```c++
if(value_count.count(A.at(i))){
    value_count[A.at(i)]++;
}
else{
    value_count[A.at(i)]=1;
}
```

以上のコードは以下の1行で代替できる.

```c++
value_count[A.at(i)]++;
```

修正版解法コード

```c++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (ll i=0; i<(ll)(n); i++)
#define repd(i,n) for (ll i=n-1; i>=0; i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define PB push_back

int main()
{
    ll N; cin >> N;
    map<ll, ll> value_count;
    vector<ll> A(N);
    rep(i, N){
        cin >> A.at(i);
        value_count[A.at(i)]++;
    }
    ll all_conbination=0;
    for(auto i=value_count.begin(); i!=value_count.end(); i++){
        all_conbination+=i->S*(i->S-1)/2;
    }
    rep(i,N)
        cout << all_conbination-value_count[A.at(i)]+1 << endl;
}
```
かなり短くなりました.