競技プログラミング総 ..
774:デフォルトの名無しさん
22/12/16 20:10:17.03 R8AxMjl90.net
各区間を頂点として、蟻本の解法の中で構築してるnextを辺としたグラフを考えると、なもりグラフになっててサイクルをちょうど一つだけ含む
答えはこのグラフ上のパスで表せる
サイクルに含まれない頂点を含む解を考えると、パスの始点と終点を一つ進めたものも有効な解であることが示せるので、
全ての頂点がサイクルに含まれるようなパスだけ考えればいい
あとはサイクルの上でしゃくとり法みたいなことやればできそう
で合ってるかな……?
次ページ続きを表示1を表示最新レス表示スレッドの検索類似スレ一覧話題のニュースおまかせリスト▼オプションを表示暇つぶし2ch
314日前に更新/229 KB
担当:undef