ACM-ICPC JAG Summer Camp 2010, Day 4
オンライン参加できるらしいので参加。10問中5問解けた。暫定3位(→USAGI Codeが真にぱないことになって結果は4位でした)。昨日のも3位だったらしい。
A
グラフにして連結成分を1つの頂点にまとめてDAGにしてからDP
DPは、ある頂点 v について、頂点 v とそれよりも上(何と言えばいいのかわからないけど木でいうと先祖みたいな感じ)の部分において、指 v が畳まれてる場合の数を a[v]、立ってる場合の数を b[v] とする。すると入次数0の頂点では a = b = 1 で、それ以外の部分では a[v] = 1,
で計算できる。(u は v への辺があるような頂点)
B
探索するだけ
C
最初見たときに双対グラフの最小全域木とか無理ゲーだと思ったけど、普通に最大全域木するだけだった。
D
やるだけ
E
問題文が読めない
F
状態遷移が書けたら余裕だけど幾何無理
G
幾何無理
H
和としてありうる範囲を持ちながら順番にやっていく。問題文読めなくてWAしまくった。
I
読んでない
J
わからない