おいしい好みの順番

• (問題: q320)
• (サービス終了したし、もう時効だと思う)

概要

• 好みの順番の順序付け集合(グラフの有向辺)が与えられる。が、一部、順序付けに矛盾が生じている。順序付けを出来るようにするために取り除く必要がある要素の数を最小化せよ。

• 用意された入力データをgraphvizで表示すると、次のようになる。

  • 
  • この中で、矢印が循環しているのは、CJ間である。したがって、辺CJか辺JCを取り除くのが正解である。

解法

• 本問はつまるところ、有向辺の集合を DAGにするために 取り除く辺を最小化せよということである。
• これはfeedback arc setと呼ばれる有名問題である。

疑問

• 用意された入力データはV=12だが、(CodeIQ感謝祭で聞いた話)実際にはV=100で出題する予定だったらしい。しかし、feedbac arc setはNP-hardであることが知られており、巡回セールスマン問題に類似した動的計画法を使ったとしてもV=20がせいぜい限界である(yukicoder)。
• トポロジカルソートを試みてソートできなかった辺を無視する解法はsub-optimalになると思うので…結局どういう解法を想定されていたのかわからないというorz
• なお、以前yukicoderで実証実験を試みましたが失敗しています。その折は大変ご迷惑おかけしましたToT

追伸

• DAGになっている頂点を取り出すだけなら簡単です https://qiita.com/cielavenir/items/58abf001a23632d04b69