2540 [ CODE FESTIVAL 2018 Final A]

https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_a

解説

https://beta.atcoder.jp/contests/code-festival-2018-final-open/submissions/3622174

条件が

• a＜c
• a != b
• b != c

を満たす(a,b,c)となっているが、この条件をまずは言い換えてみよう。
まずは、a!=bかつb!=cであるが、a=bやb=cとなることは無いので、考える必要はない。
残る条件はa＜cである。
a=cとなる場合は(a,b)と(b,c)は同じ辺となるので、同じ辺ではないという条件に言い換えられる。
あとは、a＞cとなる組(a,b,c)が会ったときに、aとcを入れ替えることで、a＜cを満たす組に1対1対応させることができる。
この組を1つとして数えるために、(a,b,c)は順列ではなく、組み合わせとして考えることにする。
同じ辺ではないというのと、組み合わせとして考えることを総括すると、条件は以下のように言い換えられる。
「2つの異なる辺の組み合わせのうち、端点を共有し、長さの和が2540となる組み合わせ」

これを数えるために、以下を用意する。
cnt[i][l] := 端点のどちらかが頂点iで、長さがlである辺の本数
これを用意した後に、辺を0からM-1まで順番に処理していくが、ループの最初でi番目の辺のcntを消しておくと、
cntの中身は辺[i+1,M)の情報が入っていることになる。
なので、辺iの情報と、cntの情報を使うことで、組み合わせをダブりなく数えることができる。
あとは、条件通り、端点を共有して、長さの和が2540となる個数を取ってくればいい。

int N, M, A[101010], B[101010], L[101010];
map<int,int> cnt[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(m, 0, M) {
        cin >> A[m] >> B[m] >> L[m];
        A[m]--; B[m]--;
        cnt[A[m]][L[m]]++;
        cnt[B[m]][L[m]]++;
    }
 
    ll ans = 0;
    rep(m, 0, M) {
        cnt[A[m]][L[m]]--;
        cnt[B[m]][L[m]]--;
        ans += cnt[A[m]][2540 - L[m]];
        ans += cnt[B[m]][2540 - L[m]];
    }
    cout << ans << endl;
}