問題一覧 > 教育的問題

No.2912 0次パーシステントホモロジー

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 44
作問者 : 👑 p-adicp-adic / テスター : Moss_LocalMoss_Local
0 ProblemId : 8857 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-10 14:25:45

問題文

入力の最初に正整数 NN と非負整数 MM と、(自己ループや多重辺を持たない)NN 頂点 MM 辺の重み付き無向グラフ GG が与えられます。

以下のような問題を考えます。

入力に非負整数 RR が与えられます。

GG から重みが RR より大きい辺を削除して得られる重み付き無向グラフの連結成分の個数を求めてください。(以下、この値をこの問題に対する答えと呼ぶ)

入力に正整数 TT が与えられます。TT 個の問題に答えてください。

背景

位相的データ解析(Topological Data Analysis)という分野では重み付き無向グラフにパーシステントホモロジーという次数付きの不変量が定義され広く応用されています。次数を1つ固定するごとにパーシステントホモロジーは非負実数で添字付けられた単体的ホモロジーと呼ばれる幾何学的不変量の系列データを与え、それ自身やその双対的な不変量のなす系列データはその他の幾何学的不変量をある意味で近似する[1] Theorem 3.5, Theorem 5.1ような系列となります。

今回の問題は重みや系列の添字を整数に限った上でパーシステントホモロジーの 00 次部分を計算する問題と考えることができます。

入力

GG の頂点を NN 未満の各非負整数 nn で番号づけて頂点 nn と呼び、GG の辺を MM 未満の各非負整数 mm で番号づけて辺 mm と呼びます。

MM 未満の各非負整数 mm に対し、辺 mm の端点を頂点 imi_m と頂点 jmj_mim,jmi_m, j_mim<jmi_m < j_m を満たす NN 未満の非負整数)と置き、辺 mm の重みを wmw_m と置きます。

TT 以下の各正整数 tt に対し、tt 個目の問題に対する入力 RRRtR_t と置きます。

 

この時、入力は以下の形式で標準入力から 3+M3 + M 行で与えられます:

  • 11 行目に N,MN, M が半角空白区切りで与えられます。
  • MM 未満の各非負整数 mm に対し、2+m2 + m 行目に im,jm,wmi_m, j_m, w_m が半角空白区切りで与えられます。
  • 2+M2 + M 行目に TT が与えられます。
  • 3+M3 + M 行目に TT 以下の各正整数 tt に対する RtR_ttt の小さい順に半角空白区切りで与えられます。
NN MM
i0i_0 j0j_0 w0w_0
\vdots
iM1i_{M-1} jM1j_{M-1} wM1w_{M-1}
TT
R1R_1 \cdots RTR_T

制約

入力は以下の制約を満たします:

  • NN0N1050 \leq N \leq 10^5 を満たす整数
  • MM0Mmin{12N(N1),105}0 \leq M \leq \min \{\frac{1}{2}N(N-1),10^5\} を満たす整数
  • MM 未満の各非負整数 mm に対し、
    • imi_mjmj_m0im<jm<N0 \leq i_m < j_m < N を満たす整数
    • wmw_m1wm1051 \leq w_m \leq 10^5 を満たす整数
  • TT1T1051 \leq T \leq 10^5 を満たす整数
  • TT 以下の任意の正整数 tt に対し、RtR_t0Rt1050 \leq R_t \leq 10^5 を満たす整数

出力

TT 以下の各正整数 tt に対し、tt 行目に tt 個目の問題に対する答えを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
2 1
0 1 1
1
2
出力
1

{0,1}\{0,1\} に対応する辺の重みは 11 です。

重みが 22 より大きい辺を削除する操作では GG が変化しないので、その連結成分は 11 個です。

サンプル2
入力
2 1
0 1 2
1
1
出力
2

{0,1}\{0,1\} に対応する辺の重みは 22 です。

重みが 11 より大きい辺を削除する操作では {0,1}\{0,1\} に対応する辺が削除されるので 22 頂点の重み付き離散無向グラフが得られ、その連結成分は 22 個です。

サンプル3
入力
2 1
0 1 1
3
2 0 1
出力
1
2
1

{0,1}\{0,1\} に対応する辺の重みは 11 です。

重みが 22 より大きい辺を削除する操作では GG が変化しないので、その連結成分は 11 個です。

重みが 00 より大きい辺を削除する操作では GG から {0,1}\{0,1\} に対応する辺が削除されるので 22 頂点の重み付き離散無向グラフが得られ、その連結成分は 22 個です。

重みが 11 より大きい辺を削除する操作では GG が変化しないので、その連結成分は 11 個です。33 個目の問題で考えるべき無向グラフの定義は GG から 重みが 11 より大きい辺を削除して得られる重み付き無向グラフであって、22 個目の問題で考えた重み付き無向グラフから重みが 11 より大きい辺を削除して得られる重み付き無向グラフではないことに注意してください。

出典

  1. J.-C. Hausmann, On the Vietoris--Rips Complexes and a Cohomology Theory for Metric Spaces, Ann. of Math. Stud., 138, Prospects in topology, pp. 175--188, 1995.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。