グラフ
問題 Editorial 問題 n人の人とプレゼントがn個ある。それぞれの人の各プレゼントのスコアvalueが与えられる。 今、人iはプレゼントiに割り当てられている。 ここから、何人かでプレゼントを交換したとき、新たな各人のスコアの総和がそれをする前より増加す…
http://apps.topcoder.com/stat?c=problem_statement&pm=10782&rd=14245 解答 この中の時間を基準に考えたら、時間の分岐が木になることがわかった。分岐がタイムトラベルポイントで、葉が訪れる街。 その木を左右に分割して探索していく。 この解法はO(n^5)…
不等式の場合、それは順序関係で、 順序関係で有向グラフにするという考え方はありだ。 循環があるかの判定(dfs/bfsでおｋ)で矛盾があるかが判定できる 矛盾がない場合それはDAGということなので、DAGとして色々考えられる グラフにしよう
http://apps.topcoder.com/stat?c=problem_statement&pm=11805&rd=14731 追記: (コメント/Editorialより) 想定解(とこの解答)は間違っているらしい Editorial読んでたのに、そのことに気づかない程度の英語力！ 問題 N(1 i番目の兵士は砦0から砦iへ向かいた…
DAGの最小パス被覆 パス被覆(path cover)とは、あるグラフのパスの集合であって、そのグラフの全ての点がそのパスに含まれているものをいう。 最小パス被覆とは、パス被覆の中で、パスの数が最小のものをいう。 DAGの最小パス被覆は二部グラフの最大マッチン…
頂点被覆(vertex cover)とは、あるグラフの点のサブセットであって、全ての辺がその点に接しているものをいう。 最小点被覆とは、点被覆の大きさをできるだけ少なくするもので、一般の場合では(決定問題に"グラフCに大きさk以下の頂点被覆があるか"として変…
http://apps.topcoder.com/stat?c=problem_statement&pm=10516&rd=13900 問題 重み付き有向グラフ(V 今、点0に蟻が居る。 蟻は1秒間にstepsPerSecond( 最大timeLimit( 蟻は最終的に点1に行きたい。 ここで、蟻が通った辺の重みの合計を最大化したい。 もし点…
Problem Statement for SalesmansDilemma 問題 重み付き(負の重みもある)有向グラフのある点からある点へ向かい、その途中で通った辺の重みの総和を最小化したい。 ただし到達できない場合は"IMPOSSIBLE"を返し、無限に小さくなる時は"ENDLESS PROFIT"を返せ…
C: 敵対的引用 - 天下一プログラマーコンテスト2012 予選A | AtCoder 問題 有向グラフA(V ある一ノードpとbool配列x[N](N pから出発してi番目(i x[i]がtrueならAを進むことができ、 x[i]がfalseならBを進むことができる。 この時、到達可能なノードの数を答…
