WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。猫のスヌークはプレゼントとして有向グラフを受け取った。graphが与えられる。graphの要素数は、彼が受け取ったグラフの頂点の数を表している。i番目の頂点からj番目の頂点へ、辺が伸びていた場合、graphのi番目の文字列のj番目の文字は'Y'となってる。辺がない場合、'N'となっている。スヌークは、このグラフにおいて、距離L(Lは巨大)の歩き方はどれほどになるのか知りたくなった。Lだけ歩くとき、その方法(道筋の辿り方)の数は、はたしてLの多項式で表せるのか?表せるのであれば"Bounded"を、表せなければ"Unbounded"を返せ。らしい考えたことi番目の頂点にスヌークがいたとして、もし道が二股に分かれていたとする。どっちの道を進んでもi番目の頂点に戻れたとする(いわゆる閉路になっている)。すると、2通りの歩き方がO(L)回だけ選択できるため、オーダーはO(2^L)となってしまう。逆にそういった頂点がなければ、多項式に収まる。ワーシャルフロイド法を変形して直接辺で繋がっていない2頂点について、到達することができれば'Y'としてグラフを更新する。