kanpurin https://blog.hatena.ne.jp/kanpurin/ かんプリンの学習記録 https://kanpurin.hatenablog.com/ yukicoder 解説 競技プログラミング グラフ DP高速化 データ構造 問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要頂点の重み無し有向グラフの隣接行列が与えられる．任意の頂点から任意の頂点までちょうど本の辺を辿って行くことのができるか判定せよ．思考の流れ yukicoder No.1340 おーじ君をさがせとほぼ同じ問題だから行列累乗で終わりと思いきや制約がきつい．きつくてもゴリ押す．bitsetを用いると，64倍くらい高速になるらしい．また，回の移動でたどり着けないようなところは回の移動を行ってもたどり着けない．だからとして計算する．計算量は公式解説の計算量にがつくくらい．かなりギリギリ(現在(2021/02/21)のAC者のなかで)最遅．… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkanpurin.hatenablog.com%2Fentry%2F2021%2F02%2F21%2F205218" title="yukicoder No.1400 すごろくで世界旅行 - かんプリンの学習記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-02-21 20:52:18 rich https://kanpurin.hatenablog.com/entry/2021/02/21/205218 1.0 100%