AtCoder ABC 359 B - Couples (6Q, 灰色, 150 点)

条件を上手に言い換えて、探索しやすい感じにしよう！

• 問題へのリンク

問題概要

をちょうど 2 個ずつ含む数列 が与えられる。

次の条件を満たす の個数を求めよ。

「数列中の、値が であるような 2 つの要素は、ちょうど 1 個の他の要素を挟む」

制約

• 

考えたこと

この手の「条件が複雑に見える」問題では、いかに条件をわかりやすく言い換えるかが肝となります。今回の問題は、次のように言い換えても良いです。

---

のうち、

であるような の個数を求めよ。

---

つまり、「ちょうど 1 個の要素を挟む 2 つの値の組」を、「右に 2 つ進んだ要素の値が自分自身と等しいような要素」に対応づけるのです。

このように問題を言い換えれば、あとは単純な for 文で解けます。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N * 2);
    for (int i = 0; i < N * 2; ++i) cin >> A[i];
    
    int res = 0;
    for (int i = 0; i + 2 < N * 2; ++i) {
        if (A[i] == A[i + 2]) ++res;
    }
    cout << res << endl;
}