CODEFESTIVAL2016Final_F Road of the King
考察
SCCしたくなるけれどしたところでどうするのって感じに。
組み合わせを考えるときは、グラフは合わない気がしてるが(使う問題あるのかな)
なので全探索とかを考えるべき。(まあ、DP)
愚直にやると300^300
状態数もかなりの数になりそう。
考えるべき状態を減らすことを考える。
状態を区別するときに必要な情報とは
- 孤立点の数(孤立点の組み合わせは考えなくてもよい)
- 強連結成分の組み合わせ
- 移動の回数
という感じだろうが、組み合わせ強連結成分については条件を達成する際には必ず最初の強連結成分とつながらなくてはいけない、それ以外の強連結成分については状態を問わない、ということから
- 孤立点の数
- 最初の強連結成分の大きさ
- 移動の回数
ということで
dp[n][a][b] := n回目の移動でa個の孤立点で最初の強連結成分の大きさがbの時の組み合わせ
となる。
状態遷移は最初の強連結成分にいるかどうかでわけ
最初の強連結成分にいるときは
- 最初の強連結成分内での移動(動かないことも含む)
- 孤立点への移動
最初の強連結成分にいないときは
- 最初の強連結成分へ移動
- 孤立点への移動
- そうでない残りの点への移動(動かないことも含む)
という感じで。
