読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

AOJ 2439 Hakone

AOJ 動的計画法

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2439

解法

先に'-'を取り除いておく。

1位から順に上から頂点を並べれば、適当な条件を満たすマッチングの数え上げの問題になる。
f:id:pekempey:20151207164120p:plain

これはDPで解ける。

dp[i][j][k]:=i番目の頂点まで見ていて、左側にあるj個の頂点が未割り当てで、かつ右側にあるk個の頂点が未割り当てであるような割り当て方の総数

i番目の頂点がDのとき
(1) 右にあるi番目の頂点を、左側にある未割当の頂点と結ぶ
f:id:pekempey:20151207163816p:plain
選び方はj通り。左側の未割当領域は1増えて1減るので変化なし。

dp[i+1][j][k]+=dp[i][j][k]*j

(2) 右にあるi番目の頂点を左側にある未割当の頂点と結び、左にあるi番目の頂点を右側にある未割当の頂点と結ぶ
f:id:pekempey:20151207163821p:plain
選び方はjk通り。左側の未割当領域は1減り、右側の未割当領域も1減る。

dp[i+1][j-1][k-1]+=dp[i][j][k]*j*k

i番目の頂点がUのとき
(1) 割り当てない
f:id:pekempey:20151207163825p:plain
選び方は1通り。左側の未割当領域は1増え、右側の未割当領域も1増える。

dp[i+1][j+1][k+1]+=dp[i][j][k]

(2) 左にあるi番目の頂点を右側にある未割当の頂点と結ぶ
f:id:pekempey:20151207163829p:plain
選び方はk通り。左側の未割当領域は変化せず、右側の未割当領域も1増えて1減るので変化なし。

dp[i+1][j][k]+=dp[i][j][k]*k

AOJ2439 Hakone O(n3)

よく考えると\(j=k\)が分かるので\(O(n^2)\)でも解ける。

AOJ2439 Hakone O(n2)

ひとこと

今年の6月頃に解こうと思って諦めた問題。解けるようになって成長を感じる。