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

わからない