形状データ処理 [パソコン甲子園2016 予選 E]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0339?year=2016

考察過程

1. 集合として見た時に同様のものがあれば消すことができる
2. 集合として等しい判定をするにはいろいろな方法があるので、好きな方法を使おう

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0339/review/3140046/hamayanhamayan/C++14

集合として等しいものがあれば消すという方針で考える。
i番目の面が消されるのはi番目より前で同じ面が存在するときである。
あとは、i番目の面とj番目の面が同じであるかを判定する方法である。
　
2つの面が同じであるかを判定するには、ソートして比較すればいい。
同じ集合であるが、順番が違うときに判定が面倒になる。
2つの面を作る頂点集合をソートしてやると、異なる順番であっても同じ列になる。
予めソートしておき、0,1,2番目が等しいか判定する。

int N, V[1010][3];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        rep(j, 0, 3) cin >> V[i][j];
        sort(V[i], V[i] + 3);
    }

    int ans = 0;
    rep(i, 0, N) {
        int isErase = 0;
        rep(j, 0, i) {
            int same = 1;
            rep(k, 0, 3) if (V[i][k] != V[j][k]) same = 0;
            if (same) isErase = 1;
        }
        if (isErase) ans++;
    }
    cout << ans << endl;
}