No.3029 オイラー標数
タグ : / 解いたユーザー数 64
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
問題文
三つの正整数からなるクエリ $A_q \ B_q \ C_q$ が与えられます（$q = 1, \dots, Q$）。ただし $A_q < B_q < C_q$ です。
集合 $V, E, F$ を全てはじめ空集合にしておき、クエリ $A_q \ B_q \ C_q$ に対して、次の操作を行います。
- 3つの整数 $A_q, B_q, C_q$ を $V$ に追加する。
- 3つの2元集合 $\{A_q, B_q\}, \{B_q, C_q\}, \{C_q, A_q\}$ を $E$ に追加する。
- 3元集合 $\{ A_q, B_q, C_q \}$ を $F$ に追加する。
有限集合 $X$ の要素数を $|X|$ と表すことにして、$Q$ 個のクエリを処理したあとの $V, E, F$ について $|V| - |E| + |F|$ を出力してください。
背景
幾何学では三次元の多面体について、点の数、辺の数、面の数をそれぞれ $v, e, f$ としたとき $v - e + f$ をオイラー標数と言います。これは多面体の「穴の個数」と関わりがあり、現代の位相幾何学の入口にある不変量です。
入力から作られる $V, E, F$ はそれぞれ多面体の点、辺、面（三角形）を集めたものと解釈できます。
このように、図形の点や辺、面の繋がり方だけを抽出したデータを「抽象単体複体」と言います。
入力
$Q$ $A_1 \ B_1 \ C_1$ $\vdots$ $A_Q \ B_Q \ C_Q$
$1 \leq Q \leq 10^5,$
$1 \leq A_q < B_q < C_q \leq 10^8.$
出力
最後に改行してください。
サンプル
サンプル1
入力
4 1 2 3 1 2 4 1 3 4 2 3 4
出力
2
$V = \{ 1, 2, 3, 4 \},$
$E = \{ \{1, 2 \}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\} \},$
$F = \{ \{1,2,3\}, \{ 1,2,4 \}, \{1,3,4 \}, \{2,3,4 \} \}.$
したがって、$4 - 6 + 4 = 2$ が出力されます。
この入力は四面体の各面を構成する頂点たちからなるクエリです。
サンプル2
入力
14 1 2 4 5 6 7 4 6 7 1 5 6 2 3 7 1 3 7 2 4 5 2 5 7 1 4 7 1 2 6 2 3 6 3 4 6 3 4 5 1 3 5
出力
0
これはトーラスという曲面の三角形分割を意図したクエリになっています。
この図では $1$ という頂点や $12$ という辺などが複数個存在しますが、本来は一つしかなく(貼り合わせる)、二次元平面内で図示するためにあえて別々に描画しています。
$V = \{ 1, 2, 3, 4, 5, 6, 7 \},$
$E = \{ \{4, 6\}, \{3, 7\}, \{1, 5\}, \{4, 5\}, \{5, 7\}, \{1, 3\}, \{1, 4\}, \{2, 4\}, \{2, 3\}, \{3, 6\}, \{1, 7\}, \{1, 2\}, \{4, 7\}, \{2, 7\}, \{3, 5\}, \{2, 6\}, \{2, 5\}, \{6, 7\}, \{1, 6\}, \{3, 4\}, \{5, 6\} \},$
$F = \{ \dots \}, |F| = 14.$
$7 - 21 + 14 = 0.$
サンプル3
入力
7 1 2 3 1 2 3 2 3 5 3 4 5 4 5 6 2 4 6 1 2 6
出力
0
$V = \{ 1, 2, 3, 4, 5, 6 \},$
$E = \{ \{4, 6\}, \{4, 5\}, \{3, 5\}, \{1, 3\}, \{2, 4\}, \{2, 3\}, \{1, 2\}, \{2, 6\}, \{2, 5\}, \{1, 6\}, \{3, 4\}, \{5, 6\} \}$
$F = \{ \dots \}, |F| = 6.$
$6 - 12 + 6 = 0.$
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。