No.2912 0次パーシステントホモロジー
タグ : / 解いたユーザー数 44
作問者 : 👑 p-adic / テスター : Moss_Local
問題文
入力の最初に正整数 と非負整数 と、(自己ループや多重辺を持たない) 頂点 辺の重み付き無向グラフ が与えられます。
以下のような問題を考えます。
入力に非負整数 が与えられます。
から重みが より大きい辺を削除して得られる重み付き無向グラフの連結成分の個数を求めてください。(以下、この値をこの問題に対する答えと呼ぶ)
入力に正整数 が与えられます。 個の問題に答えてください。
背景
位相的データ解析(Topological Data Analysis)という分野では重み付き無向グラフにパーシステントホモロジーという次数付きの不変量が定義され広く応用されています。次数を1つ固定するごとにパーシステントホモロジーは非負実数で添字付けられた単体的ホモロジーと呼ばれる幾何学的不変量の系列データを与え、それ自身やその双対的な不変量のなす系列データはその他の幾何学的不変量をある意味で近似する[1] Theorem 3.5, Theorem 5.1ような系列となります。
今回の問題は重みや系列の添字を整数に限った上でパーシステントホモロジーの 次部分を計算する問題と考えることができます。
入力
の頂点を 未満の各非負整数 で番号づけて頂点 と呼び、 の辺を 未満の各非負整数 で番号づけて辺 と呼びます。
未満の各非負整数 に対し、辺 の端点を頂点 と頂点 ( は を満たす 未満の非負整数)と置き、辺 の重みを と置きます。
以下の各正整数 に対し、 個目の問題に対する入力 を と置きます。
この時、入力は以下の形式で標準入力から 行で与えられます:
- 行目に が半角空白区切りで与えられます。
- 未満の各非負整数 に対し、 行目に が半角空白区切りで与えられます。
- 行目に が与えられます。
- 行目に 以下の各正整数 に対する が の小さい順に半角空白区切りで与えられます。
制約
入力は以下の制約を満たします:
- は を満たす整数
- は を満たす整数
- 未満の各非負整数 に対し、
- と は を満たす整数
- は を満たす整数
- は を満たす整数
- 以下の任意の正整数 に対し、 は を満たす整数
出力
以下の各正整数 に対し、 行目に 個目の問題に対する答えを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 1 0 1 1 1 2
出力
1
に対応する辺の重みは です。
重みが より大きい辺を削除する操作では が変化しないので、その連結成分は 個です。
サンプル2
入力
2 1 0 1 2 1 1
出力
2
に対応する辺の重みは です。
重みが より大きい辺を削除する操作では に対応する辺が削除されるので 頂点の重み付き離散無向グラフが得られ、その連結成分は 個です。
サンプル3
入力
2 1 0 1 1 3 2 0 1
出力
1 2 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もしくは右上の雲マークをクリックしてアカウントを作成してください。