hotpepsiの練習帳

SRM 692

23:48

https://competitiveprogramming.info/topcoder/srm/round/16747/div/1

Div1 Easy (250) HardProof

問題

• 0からN-1までのN問の命題がある
• 任意の言明x,yについて、xならばyを証明することの難易度が与えられる
• 直接または間接的に、全ての任意の二つの言明x,yについて、xならばyを証明することにする
• 最も難しい証明と最も易しい証明の差を最小化するとき、差の最小値を求める

方針

• (終了後)
• 命題0ならば[各命題]
• [各命題]ならば命題0
• の両方を満たせば、任意の命題を満たすことになる
• コストの差の上限を決め、それ以下の辺だけを使って、コストの差を二分探索
• 命題0ならば[各命題]は、ある辺nからDFSする
• [各命題]ならば命題0は、ある辺nへ入ってくる頂点へのDFS
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_692/HardProof.cpp

結果

--- 0pt 88th/196 rating 1510 -> 1467 (-43)

2-SATやSCC使っても解けるらしい。

http://togetter.com/li/985735