NachiaVivias

[問題案] Rooted Tree Isomorphism Classification

2

問題名: Rooted Tree Isomorphism Classification （ "Isomorphism" はいらないかも ） 想定アルゴリズム: 小さい順に ID を振る 参考資料: https://atcoder.jp/contests/nikkei2019-2-final/tasks/nikkei2019_2_final_d # 問題概要 ## 入力 N 頂点の根付き木 ## 出力 N 個の非負整数 A[i] (< N) 頂点 i...

[問題案] Incremental Minimum Spanning Forest

6

問題ID: incremental_msf 問題名: Incremental Minimum Spanning Forest 想定アルゴリズム: link-cut tree で maximum を管理する。 参考資料: https://atcoder.jp/contests/joisc2022/tasks/joisc2022_l https://atcoder.jp/contests/pakencamp-2021-day3/tasks/pakencamp_2021_day3_g https://twitter.com/SSRS_cp/status/1508735586718613507 # 問題概要 $N$ 頂点のグラフの $M$ 個の重み付き無向辺が順に与えられる。番号が $i$ 未満の辺のみを採用した場合の最小全域森を $F_i$ とする。各辺 $k$ について、辺 $k$...

[問題案] Persistent Range Affine Range Sum

2

問題ID: persistent_range_affine_range_sum 問題名: Persistent Range Affine Range Sum 想定アルゴリズム: 遅延セグメント木の path copying 参考資料: https://37zigen.com/persistent-segment-tree/ # 問題概要 Range Affine Range Sum を永続化 + α 初期状態を X[-1] とする クエリ 0 t l...

graph のドキュメントを書いていて気づいたこと

2

### ~~biconnedted~~ biconnected components の実装 minmax,min,maxのテンプレート引数を指定していないことが原因で、 `StaticGraph` が使えません。 ### ~~biconnedted~~ biconnected components の実装 2 孤立点からなる成分は出力から検出できませんが、これは想定していますか？ input (1-indexed) ``` 3 1 1 2 ``` output ``` ## biconnected_components.articulation = [ ]...

Problem name: Tree Distance Sum (Optional) Problem ID: tree_distance_sum ## 問題文 辺重みつきの $N$ 頂点の木、長さ $N$ の数列 $A$ が与えられるので、各頂点 $v$ について $\sum_{u} A_u \text{dist}(u,v)\pmod{998 244 353}$ を求めてください。 ## 制約 - $1...

[問題案] Palindromes in Deque

3

[問題案] Palindromes in Deque target : [Double-Ended Palindromic Trees](https://arxiv.org/pdf/2210.02292.pdf) ## Problem 初期状態の文字列が与えられて、以下の 4 つの操作を処理せよ。 * $(0,c)$ : push back $c$ → suffix の回文の長さの最大を出力 * $(1,c)$ : push front $c$ →...

今のテストケースのうち small_07 ( $N=3,M=2$ ) のみで WA になるような誤りを含んだソースコードを提出しました。 : [185908](https://judge.yosupo.jp/submission/185908) ミスは、再帰をやめる条件がを「 1 列まで reduce された」にしていることで、その後では 1 行まで reduce されたことを想定して実装しています。 試したうちでは、次のケース( verifier を通しました)でも出力が誤っていました。 ``` 17 8 1 1 2 4 7...

[Undirected 版](https://judge.yosupo.jp/problem/cycle_detection_undirected)の long_cycle に相当するケースを追加したいです。 関連 : #864

[問題案] Range Chmin Range Sum

1

Problem name: Range Chmin Range Sum Problem ID: range_chmin_range_sum ## Problem 長さ $N$ の列 $A_0,A_1, \ldots A_{N-1}$ に対してクエリを処理。 - 1 $l$ $r$ $x$ : $A_i$ ← $\min(A_i,x)$ for $l\leq i\lt...

Tree Decomposition (Width 2) の M=0 は有効か？

1

problem : https://judge.yosupo.jp/problem/tree_decomposition_width_2 有効ならテストケースに入れるべきだと思います。有効なら、もしかすると K=0 の場合の出力をもっと明確にすべきかもしれません（辺が K-1 個ではないので）。