問題一覧 > 通常問題

No.3029 オイラー標数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 63
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
0 ProblemId : 11907 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-21 21:56:49

問題文

三つの正整数からなるクエリ $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もしくは右上の雲マークをクリックしてアカウントを作成してください。