誰が誰にいくら？割り勘の精算を最小回数で終わらせる計算の仕組み

5人でホームパーティをした。食材のまとめ買いはAさん、飲み物はBさん、ケーキはCさんが立て替えた。この状態で「立て替えた人にその都度返す」をやると、送金は支払い1件につき人数分ずつ増えます。後で挙げる実例だと、支払い5件を1件ずつ精算して延べ18回。同じ相手どうしの貸し借りを打ち消し合わせても、5人がつくる10組すべてのペアに金額が残って10回です。

ところが、実際に必要な送金は4回だけです。往復している分は、そもそも動かさなくていいお金だからです。この記事では、その4回をどう導くのかを、SplitPayが内部で走らせている計算の中身まで開いて説明します。旅行のように日をまたぐ場面の記録の取り方や段取りは旅行の割り勘・立て替え精算ガイドにまとめてあり、ここでは計算そのものを扱います。

精算の計算で最初にやるのは、「誰が誰にいくら貸している」という関係を全部忘れることです。代わりに人ごとに持つのは、次の1つの数字だけ。

残高 ＝ 実際に払った額 − 自分が負担すべき額

プラスなら受け取る側（払いすぎている）、マイナスなら払う側（払い足りない）。負担すべき額は、支払い1件ごとに「金額 ÷ 対象人数」を対象者に振り分けて足し上げれば出ます。

この残高には、必ず成り立つ性質があります。全員分を足すと必ず0になることです。1件の支払いは、払った人にプラスの金額を、対象者にマイナスの金額を、同じ総額だけ配る操作にすぎないからです。逆に言えば、合計が0にならなければ入力のどこかが間違っている。そのまま検算に使えます。

残高が出れば、あとは送金の組み合わせを作るだけ。手順はこれだけです。

• マイナスの人（払う側）を、マイナスが大きい順に並べる
• プラスの人（受け取る側）を、プラスが大きい順に並べる
• 両方の先頭を突き合わせ、絶対値が小さいほうの金額を送金1件にする
• 残高が0になった人は列から抜け、残っている人は次の相手へ進む

実例に当てはめます。払う側はDさん（−6,600円）Eさん（−3,300円）Cさん（−1,400円）の順、受け取る側はAさん（＋8,900円）Bさん（＋2,400円）の順です。まずDさんがAさんへ6,600円を送るとDさんが抜け、Aさんの残りは2,300円。次にEさんがその2,300円を埋めるとAさんが抜け、Eさんには1,000円の借りが残ります。それをBさんへ送るとEさんも抜けて、Bさんの残りは1,400円。最後にCさんの1,400円がぴったり収まって全員0です。

1人の貸しが複数人の借りで埋まることも、1人の借りが2人に分かれることもありますが、手順は同じです。この「先を考えず、目の前で一番大きいところ同士を当て続ける」やり方を貪欲法（グリーディ法）と呼びます。SplitPayの精算もこの手順です。

正直に書くと、貪欲法が出す回数は理論上の最小とは限りません。5人の残高が＋4,000／＋3,000／＋2,000／−4,000／−5,000円だったとします。大きい順に当てると送金は4回ですが、−4,000円の人を＋4,000円の人にまっすぐつなぎ、残った−5,000円を＋3,000円と＋2,000円に分ければ3回で済みます。ぴったり打ち消し合うグループを見つけられれば減らせるわけです。

では常に最小を探せばいいかというと、そう単純ではありません。「合計がちょうど0になる部分集合」を洗い出す問題（部分和問題）を含むため、人数が増えると調べる組み合わせが爆発的に増えます。計算機科学ではこれをNP困難、つまり現実的な時間で厳密に解く方法が知られていない種類の難しさ、と分類します。

ちなみに上のホームパーティの残高には、打ち消し合うグループが1つもありません。だからあの4回は本当の最小です。割り勘の人数はふつう数人から数十人で、その範囲なら貪欲法の結果は最小と一致することが多く、ずれても1〜2回。厳密さを待たせるより、送金先がすぐ確定するほうを採っています。