対戦ゲームのチームはどう決める？

対戦ゲームのチームはどう決める？

締め切りが 2017/11/30 10:00 AM なので，その 1 分後に投稿されるように予約

設問

あなたは対戦型オンラインゲームの開発に携わっており、チームバトルにおける「マッチング」のアルゴリズム開発を任されました。

なお、マッチングとは、同一時間に同一のゲームができるようプレイヤー同士を引き合わせことで、どちらかのチームが極端に有利にならないよう、メンバーを決める必要があります。

求められるプログラムの前提条件は、以下の通りとなります。

・ 標準入力から、以下の書式の文がプレイヤーの人数分、複数行送られる
     プレイヤーのID プレイヤーのレート
・ プレイヤーのIDは、0から始まる連番の数値である
・ プレイヤーのレートは、1桁以上4桁以下の正の整数とする
・ チームバトルの候補となるプレイヤーは、4人以上20人以下とする
・ チームバトルは2人対2人の2チームによる対戦とし、メンバーの欠員は認めないものとする
・ チームに所属するメンバー全員のレートを合計したものをチームレートと呼ぶ
・ チームメンバーは、チームレートの差の絶対値が最小となるように決めること
・ チームメンバーの最適解が複数存在するケースは考慮しなくともよい。
※ 簡単のため、最適解は１つとなるように入力データが調整される
・ 選んだチームメンバーの中で、最もIDが小さいプレイヤーが所属するチームをチームAと呼び、もう一方をチームBとする
・ 標準出力に、チームAのメンバー全員のIDをIDの値が昇順となるよう、スペース区切りで出力し、次に改行した上で、同様にチームBのメンバー全員のIDを昇順で出力する

そして 以下が、入力と出力例になります。

上記の例でNo.1の場合、チームレートは 2389+1894と1363+2865 となり、その差の絶対値は 55 となります。
そしてNo. 2は、No.1 に1プレイヤーを加えたものですが、差の絶対値は 2 となります。

マッチングというのも実に奥が深いテーマで、上記のような実力差だけで選んでしまうと、実力が平均に近いプレイヤーが集中的に選ばれてしまいます。
そこで、快適に遊んでもらうために、プレイヤーの待ち時間といったものを考慮する必要があるでしょう。

また、人数が増えた場合にどう高速化するかという課題も出てきます。
もしかすると普段貴方が遊んでいるゲームの裏側では、実に大変な組合せ最適化問題をバックエンドで解いているかもしれませんね。
それでは、ぜひ挑戦してみてください！

【問題】
標準入力から、プレイヤーのIDとレート（腕前を数値化したもの）が、プレイヤーの人数分複数行送られます。
ここで、2人対2人のチームバトルを想定したとき、チーム間の実力がなるべく均衡するように、チームメンバーを決め、その結果を標準出力に返してください。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

f = function(x) {
    n = length(x)/2
    rate = x[1:n*2]
    teamRate = outer(rate, rate, "+")
    minDif = Inf
    a = combn(n, 2) # n 人から 2 人取り出す組み合わせ
    for (i in 1:ncol(a)) {
        a1 = a[1, i]
        a2 = a[2, i]
        teamRateA = teamRate[a1, a2]
        b = combn((1:n)[-a[, i]], 2) # a チーム以外の n-2 人から 2 人取り出す組み合わせ
        for (j in 1:ncol(b)) {
            b1 = b[1, j]
            b2 = b[2, j]
            teamRateB = teamRate[b1, b2]
            dif = abs(teamRateA-teamRateB)
            if (dif < minDif) {
                minDif = dif
                ID = c(a1, a2, b1, b2)-1
            }
        }
    }
    cat(sprintf("%i %i\n", ID[1], ID[2]), sprintf("%i %i\n", ID[3], ID[4]), sep="")
}
# f(scan(file("stdin", "r")))

f(c(0, 1000, 1, 2122, 2, 2389, 3, 1363, 4, 1894, 5, 2865)) # (2, 4), (3, 5)
f(c(0, 1000, 1, 2122, 2, 2389, 3, 1363, 4, 1894, 5, 2865, 6, 1761)) # (0, 1), (3, 6)
f(c(0, 1987, 1, 1521, 2, 987, 3, 1201, 4, 1055, 5, 1763, 6, 2469, 7, 2017)) # (0, 2), (3, 5)
f(c(0, 1987, 1, 1521, 2, 987, 3, 1201, 4, 1055, 5, 1763, 6, 2469, 7, 2017,
8, 2890, 9, 2345, 10, 1609, 11, 3101)) # (2, 11), (3, 8)
f(c(0, 1987, 1, 1521, 2, 987, 3, 1201, 4, 1055, 5, 1763, 6, 2469, 7, 2017,
8, 2890, 9, 2345, 10, 1609, 11, 3101,
12, 3689, 13, 876, 14, 3309, 15, 785, 16, 2678, 17, 3586, 18, 3321, 19, 2643)) # (1, 10), (9, 15)