配列の足し算？がわかりません...

Question

https://atcoder.jp/contests/abc159/tasks/abc159_d

こちらの問題に関して質問がございます。解説動画では以下のようなコードを書いていました。

#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;

ll choose2(ll n){
  return n*(n-1)/2;
}

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  rep(i,n) a[i]--;
  vector<int> cnt(n);
  rep(i,n) cnt[a[i]]++;
  ll tot=0;
  rep(i,n) {
    tot+=choose2(cnt[i]);
  }
  rep(i,n) {
    ll ans=tot;
    ans-=choose2(cnt[a[i]]);
    ans+=choose2(cnt[a[i]]-1);
    cout << ans << endl;
  }
  return 0;
}  

ここでrep(i,n) cnt[a[i]]++;というところが理解できません。これの2行下での操作は入力例1で言うとcnt[i]に3と2が入ると思うのですが、ということはcnt[a[i]]++で異なる数字の個数をそれぞれ計算できているということですか？例えば1 4 3 3 5 6 3 2 1 1という文字列があったらcnt[a[i]]++で3 1 3 1 1 1となり、それをcnt[i]が受け取り、choose2の関数に入れて計算しているのでしょうか？説明がわかりにくくて恐縮ですが、よろしくお願い致します・

Answer 1

cnt[a[i]]++で異なる数字の個数をそれぞれ計算できているということですか？例えば1 4 3 3 5 6 3 2 1 1という文字列があったらcnt[a[i]]++で3 1 3 1 1 1となり、それをcnt[i]が受け取り、choose2の関数に入れて計算しているのでしょうか？

そのとおりです。repという、見慣れないマクロを使うと余計にわかりにくくなるので、展開したforループで書いたほうがいいでしょう。

Comments

[maisumakun]

どの辺がわからなかったのか、掘り下げていただくことはできますか？

[cunwe]

「cnt[a[i]]++」で異なる数字の個数をそれぞれ計算できているということですがその仕組みがよくわからないです...。「cnt[a[i]]++」だけでなぜ「異なる数字の個数をそれぞれ計算」という高度な？ことができているのか教えていただけますか？

[maisumakun]

ループ1回毎に、cntの1要素へ1を足している、それだけです（1を足した回数=個数です）。何も「高度」なことはありません。

[cunwe]

くどい質問で恐縮ですが「同じ数を見つけて」ということはどう行われているのでしょうか？

[maisumakun]

「見つけて」などいません。3があったらcnt[3]に1を足す、5があればcnt[5]に1を足す、それだけです。

[cunwe]

そういうことですか納得できました、ありがとうございました！