SRM405 500 : AllCycleLengths

DP

諦めそうになった。

問題概要

  • 有向グラフが与えらます。
  • ある頂点を出発しk(k>0)回のステップで同じ頂点に戻れるならばk番目の文字は'1'、そうでなければ'0'となる文字列を求めて下さい。
  • ただし文字列は無限に長くなってしまうので循環する部分を()でくくって下さい。
  • 注意すべきは 

    A traveler starts from some city,
    つまり、各街から出発して一周するのを全ての街に対して行ったもののORを取らなければなりません。

解法

  • dp[頂点][なんステップ目か] = たどり着けるか
    でDPでをします。これを各頂点から行うため、頂点数だけ繰り返します。
  • なんステップまで見るかをどこまで見ればいいのかよく分からなかったのでとりあいず10000くらいやった（最悪でも30*30*30くらいかかりそうだと思ったけど詳しい話は知らない）
  •  dpで各頂点からのkステップサイクルがわかるので全てのORを取る感じに文字列を生成する。
  • その後、()のくくりを判定する。
  • (1) でループするかどうか、 (01)  でループするかどうか (001) でループするかどうか… というのを頂点数の回数だけチェックする。
  • (101)とか(001001)というループは存在しないことはいろいろ考えたりすると直感的に感じ取れる。
ソースコード

感想

各頂点の論理和をとるのを、各頂点のサイクルのMAXだと思っていて死にそうになった。

普通に解法に至るまで時間かかりすぎだし心折れそう。

そしてまだ５回しか消化していないという絶望。

垢消し不可避なんじゃこれ