106

久々にしっかり考える時間ができたので嬉しくなって解いてしまった。

disjoint subset pairの数は

n
ΣnCk * S(k, 2)
k=2

で求まる。SはStirling Number of the Second Kind。n個の数からk個選び、そのk個を二つの組に分ける方法の数。そのまま。解法には直接関係ない。

次に答え。比較する必要があるのは同じ数の集合のみ。この問題の場合、4,6,8,10,12個の要素を取ってきたときに、何個くらい比較する必要があるかを調べ、その和を求めればいい。大小関係を比較する必要がないのは[1, 2, 5]と[2, 3, 6]のように、二つの配列中で位置が同じ要素同士の大小関係が常に等しいとき。逆に言えば、それ以外のものをカウントしてあげればいい。

そして、12個からn個取ってきたときは、[1 .. n]という配列を二つに分けたときに、そのうち何個比較する必要があったか求める。求まった数に12Cnを掛ける。その和を求めて終了。とりあえず最後に2で割る必要があるような作り方になってしまったけども。