競プロ
CODE FESTIVAL 2017 Elimination Tournament Round 3 (Parallel) - AtCoder: E を解き、F を解説 AC した。
- E: https://atcoder.jp/contests/cf17-tournament-round3-open/editorial/1946
- F: ネタバレ→サイクルに含まれる頂点集合を全探索すればよさそうというのはわかったが肝心の方法がわからなかった。そのサイクルを 1 点にまとめたらグラフは木になり、逆にそういう木が与えられたとき元のなもりグラフを復元する方法はちょうど (余計な次数)!/Π(各頂点の余計な次数)! 通りなので、DP で高速化できる程度に簡単な式になる。←ネタバレ
なもりグラフ -> サイクル + 森 の分解をやる関数をライブラリにした。
