mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ TopCoder 問題 TopCoder Statistics - Problem Statement 解法 直前 K 個 の頂点の次数の偶奇がわかっていれば, dp に持っていけそうです。dp[now][restEdge][atLeast][flag] というように状態を与えます。 now 番目の頂点を見ていて, 残り貼る辺の数は restEdge で, now より前の頂点として, now-K+atLeast から先の頂点のみに辺を貼ることを考えます。また, 直前 K 個および自分の頂点までの次数の偶奇が flag で表される時の, valid なグラフの数, です。atLeast はいらない子な気がするか… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F02%2F17%2F162447" title="SRM 532 div1 med: DengklekBuildingRoads - mayoko’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-02-17 16:24:47 rich https://mayokoex.hatenablog.com/entry/2016/02/17/162447 1.0 100%