blog主に競プロ問題の解説を載せてますこの広告は、90日以上更新していないブログに表示しています。過去問解き制限が5secな珍しい問題。ネスト深すぎなので分離すればよかったかな。問題R×Cの2次元セルがある。あるセルからは上下左右のセルにコスト1で移動できるとする。テレポーターを1組置くことができ、片方のテレポーターからもう一方へコスト0で移動できる。テレポーターのあるマスに移動したときにはテレポーターを使うかそのままそのセルにとどまるか選択できる。任意のセル間の移動コストの最大値を最小化するようにテレポーターを設置したときの、最小化された移動コストの最大値を答えよ。解法2点間距離はワーシャルフロイドで求め、テレポーターの設置場所は重複の無い全探索をすればいい。オーダーはO((RC)5)になるがR,Cが最大10で制限が5secなのでこれでも間に合う。1のコーナーケースに注意するのを忘れない。読者になるリンクTopCoderCodeforcestwitterGitHubQiitaはてなブログをはじめよう!roiti46さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。