Information Science
寝て起きて冷静になって考えてみたら,昨日の最後の方は大嘘ばっか書いてますよよよ? トーナメントグラフ上での必要条件 参加総数を N とし,N に対するトーナメントグラフが与えられているとする.このとき, 「参加者 A が優勝できるようなトーナメントが…
bottom-up な DP の構成で,最悪の場合列挙する数が指数になってしまうのだけれど,これを何とか圧縮する方向を模索. 特に今,人が参加する部分トーナメントにおいて,A を含むどんな参加者の組み合わせにおいても A がこの部分トーナメントを勝ちぬけられ…
って,寝て起きて冷静に考えてみれば,勝敗表の制約の下で任意の人が優勝できる部分トーナメントを列挙してるわけだから最悪指数に決まってるじゃないか.何やってるんだ……恥ずかしいにゃー,もぅ. permutation を combination で表しておいて,最後に top-…
さっきソファーに突っ伏して仮眠して起きたら,解法っぽいものを思いついた.アルゴリズムが正しいかどうかは知らん. http://www.kmonos.net/wlog/53.php#_1604050908 前提として,人数は2のべきと仮定します. まず,表記を導入します. (A, B, C, D) とい…