私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「対戦ゲームのチームはどう決める？」（CodeIQ）を参照してください。
あなたは対戦型オンラインゲームの開発に携わっており、チームバトルにおける「マッチング」のアルゴリズム開発を任されました。
なお、マッチングとは、同一時間に同一のゲームができるようプレイヤー同士を引き合わせことで、どちらかのチームが極端に有利にならないよう、メンバーを決める必要があります。
求められるプログラムの前提条件は、以下の通りとなります。
標準入力から、以下の書式の文がプレイヤーの人数分、複数行送られる
プレイヤーのID プレイヤーのレート
プレイヤーのIDは、0から始まる連番の数値である
プレイヤーのレートは、1桁以上4桁以下の正の整数とする
チームバトルの候補となるプレイヤーは、4人以上20人以下とする
チームバトルは2人対2人の2チームによる対戦とし、メンバーの欠員は認めないものとする
チームに所属するメンバー全員のレートを合計したものをチームレートと呼ぶ
チームメンバーは、チームレートの差の絶対値が最小となるように決めること
チームメンバーの最適解が複数存在するケースは考慮しなくともよい。
※ 簡単のため、最適解は１つとなるように入力データが調整される
選んだチームメンバーの中で、最もIDが小さいプレイヤーが所属するチームをチームAと呼び、もう一方をチームBとする
標準出力に、チームAのメンバー全員のIDをIDの値が昇順となるよう、スペース区切りで出力し、次に改行した上で、同様にチームBのメンバー全員のIDを昇順で出力する
そして 以下が、入力と出力例になります。
No. 入力例 出力例 1 0 1000
1 2122
2 2389
3 1363
4 1894
5 2865
2 4
3 52 0 1000
1 2122
2 2389
3 1363
4 1894
5 2865
6 1761
0 1
3 6
上記の例でNo.1の場合、チームレートは 2389+1894と1363+2865 となり、その差の絶対値は 55 となります。
そしてNo. 2は、No.1 に1プレイヤーを加えたものですが、差の絶対値は 2 となります。
マッチングというのも実に奥が深いテーマで、上記のような実力差だけで選んでしまうと、実力が平均に近いプレイヤーが集中的に選ばれてしまいます。
そこで、快適に遊んでもらうために、プレイヤーの待ち時間といったものを考慮する必要があるでしょう。
また、人数が増えた場合にどう高速化するかという課題も出てきます。
もしかすると普段貴方が遊んでいるゲームの裏側では、実に大変な組合せ最適化問題をバックエンドで解いているかもしれませんね。
それでは、ぜひ挑戦してみてください！
【問題】
標準入力から、プレイヤーのIDとレート（腕前を数値化したもの）が、プレイヤーの人数分複数行送られます。
ここで、2人対2人のチームバトルを想定したとき、チーム間の実力がなるべく均衡するように、チームメンバーを決め、その結果を標準出力に返してください。
Rubyで解答しています。
#!/usr/bin/ruby
def solve(inputs)
pattern = []
for i in 0...inputs.size
for j in (i+1)...inputs.size
team = {
"rate" => inputs[i] + inputs[j],
"mem" => [i,j]
}
pattern << team
end
end
pattern = pattern.sort{|a, b| b["rate"] - a["rate"]}
min = 0xffffffff
vs = nil
for i in 1...pattern.size
next if !(pattern[i-1]["mem"] & pattern[i]["mem"]).empty?
s = pattern[i-1]["rate"] - pattern[i]["rate"]
if s < min then
min = s
vs = [pattern[i-1]["mem"], pattern[i]["mem"]]
end
end
vs.sort!
puts vs[0].join(" ")
puts vs[1].join(" ")
end
# main
inputs = []
while line = gets
line.strip!
_,n = line.split.map{|a| a.to_i}
inputs << n
end
solve(inputs)
あまり実行速度は考えていません。
考えられるチームの組み合わせを列挙します。
チームレートでその組み合わせをソートします。
ソート済みのチームの内、並んでいるもののチームレートの差を求め、その差が最小のものを選べば答えになります。
ソート済みなので、2以上離れたチームレートの差は隣り合うチームのチームレートの差より必ず大きくなるので検討する必要がありません。
なお、同じメンバが比較対象のチームに含まれる場合は無視する必要があります。
入力値を数値に分割し、配列（inputs）に保持してsolve()に渡します。
patternは考えられる全チームのパターンを保持する領域です。
5〜14行目の二重ループでチームのパターンを列挙します。チーム情報は{"rate": チームレート, "mem": [メンバ1, メンバ2]}の連想配列で保持します。
16行目でチームレートが小さい方から昇順にpatternをソートします。
minはレートの差の最小値、vsは対戦チームの組み合わせを保持する配列になります。
20〜28行目のループでチームレートの差が最小になる組み合わせを選びます。
21行目の条件はメンバに同じ人が含まれている場合、無視するためのものです（チームAが[1,2]、チームBが[1,3]のような場合は両方に1が居るのでこの対戦は成り立たない）。
23行目で2つのチームのチームレートの差を計算し、24〜27行目でチームレートの差がより小さいものが現れたらそれで候補を更新します。
ループが終わった時点のvsにチームレートの差が最小になる組み合わせが保持されます。
vsを番号が若い順になるようにソートし（30行目）、結果を印字します。
これだとO(n2)なので1000人くらいになるとキツイですが、プレーヤーが最大20人なのでこんなので良いかなと。
1000人以上でも耐えられるようなプログラムだとどうやってやるんだろう？