ぺたふぁん温泉旅行部: 精算の効率化
はじめに
こんにちは．ぺたふぁん（存在しないクラン）のねりうめです．
先日，ぺたふぁんの皆様と温泉旅行に行きました．
まるで小中学校の修学旅行のような雰囲気で，とても楽しかったです．
参加者の皆様，ありがとうございました！
ぺたふぁんの皆様が幼稚というわけではない
さて，大勢で旅行をすると必ず付きまとう問題として，精算が挙げられます．宿の予約，交通費，食費など，旅行中のあちこちで立て替えが発生します．旅行の〆に面倒な思いをしながら面倒な精算をしたことがある方，多いのではないでしょうか．
実際，今回のぺたふぁん旅行でも精算はそこそこ面倒でした．
Discordに精算チャンネルを用意し，そこに書き込み，最終的に集計，精算を行うことにしたのですが，いかんせん件数が多く……
最終日の朝に急いでスプシを作って精算を行うこととなりました．
実際に支払い額を計算しても面倒は終わらず……
旅行の参加者が10名，全体に対する立て替えと個人間の立て替えが存在し，愚直に受け渡しを行うと金銭授受回数がとんでもないことに……わかんなくなっちゃう……
というわけで，本記事では，金銭授受回数を少なくするような精算のやり方について考察します．プリコネ要素はありますがプリコネの話はありません．
金銭授受回数の上限
では，なるべく授受回数を減らすような精算を行った場合，最大で何回の金銭授受が必要となるでしょうか？
例として，このような状況を考えます．矢印は立て替えを，数字はその量を表しています．つまり，
きしくんはチエルに5を立て替えている
きしくんはユニに8を立て替えている
チエルはユニに6を立て替えている
クロエはユニに9を立て替えている
状況です．
ここから精算を行うには，何回の金銭授受が必要でしょうか？もちろん，この4つの立て替えの逆操作を行う(つまり4回の金銭授受)ことで精算を完了できます．もっと少なくすることはできるでしょうか？
「きしくんからチエルへの立て替え」は，「きしくんからユニへの立て替え」と「ユニからチエルへの立て替え」と置き換えることができますね．
「AからBへの立て替え」と「BからAへの立て替え」は相殺できるので，結果として
このような立て替え関係に整理することができました．
支払い者や立て替え件数が増えても同様の操作を行い，1人対他全員の立て替え関係を作ることで，参加人数をnとするとき，高々n-1回の立て替え操作で精算を行えます．
では，立て替え操作をn-1回より少なくすることは可能でしょうか？
なるべく減らしたい
条件によっては可能です．
例えば，1回も立て替えをしていない場合，もちろん0回の操作で元に戻ります．
以下のような例を考えてみましょう．
支払いグループに由来する場合
参加者が5人，立て替えは4件です．
しかし，上2人と下3人の間で立て替えは発生していません．
これを整理すると，先程の議論より
結果として，参加者5人に対し，n-1より少ない3回の金銭授受で精算をすることができます．
今回の結果は，精算を2人と3人の2グループに分けて行うことができました．ここで注意したいこととして，それぞれのグループ内でn-1回の精算が発生しています．
つまり，参加者を直接の支払関係が存在しないグループに分割したとき，それぞれのグループ内で高々n-1回の金銭授受で精算を行えます．
最初の例は4人かつ支払いのグループが1つの場合，といえます．
支払い額に由来する例
このような例を考えてみましょう．
3人グループ，立て替え2件のためn-1回で精算できます．
しかし，この場合はもっと回数を減らせますね．
付け替えを行ったところ相殺され，さらに金銭授受回数を減らすことができました．
つまり，グループ内で誰に集約するかによって，さらに回数を減らせる可能性があるということです．
実装
ここまでの議論をもとに実装を行いましょう．
誰と誰が同じグループに属するかは，Disjoint Set(いわゆるUnion-Find)で判定できます．
全体のグループ分けが済んだら，各グループ内での最小授受回数を調べます．
それぞれのグループに対し，誰に集約したとき何回になるかを総当りで求めます．これをすべてのグループに対し行い，各グループにおける最小値を足し合わせることで，最小回数を求めることができます．
実装例(長い)
「参加者」シートに参加者の名前「精算メモ」に内容を記入し実行すると，「結果出力」に支払いリストが出力されます．
以下はコードの実装例です．ほとんどGitHub Copilotに書いてもらいました．
学割使って無料で利用しています．最高！！
// 参加者リストを読み込む
function readParticipantList() {
var sheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName('参加者');
var lastRow = sheet.getLastRow();
var range = sheet.getRange(4, 2, lastRow - 3);
var participants = range.getValues().flat(); // 1次元配列に変換
return participants;
}
// フローデータを読み込む
function readFlows() {
var sheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName('精算メモ');
var lastRow = sheet.getLastRow();
var range = sheet.getRange(3, 2, lastRow - 2, 3);
var flows = range.getValues();
// flowデータは，[支払った人, 受け取った人, 金額]の形式で格納されている
// 受け取った人が"全員"の場合は，自分以外の参加者に対し1人金額円支払ったことになる
// つまり，参加者が[A,B,C,D]で,[A,全員,1000]の場合は，[A,B,1000],[A,C,1000],[A,D,1000]として扱う
var new_flows = [];
for (var i = 0; i < flows.length; i++) {
var from = flows[i][0];
var to = flows[i][1];
var amount = flows[i][2];
if (to === "全員") {
var participants = readParticipantList();
for (var j = 0; j < participants.length; j++) {
if (participants[j] !== from) {
new_flows.push([from, participants[j], amount]);
}
}
} else {
new_flows.push([from, to, amount]);
}
}
return new_flows;
}
// Union-Find木の初期化
function initUnionFindTree(n) {
var tree = [];
for (var i = 0; i < n; i++) {
tree.push(i);
}
return tree;
}
// Union-Find木の根を求める
function findRoot(tree, x) {
if (tree[x] === x) {
return x;
} else {
tree[x] = findRoot(tree, tree[x]);
return tree[x];
}
}
// Union-Find木の併合
function unite(tree, x, y) {
var rootX = findRoot(tree, x);
var rootY = findRoot(tree, y);
tree[rootX] = rootY;
}
function calcpayment(flows, participants, parent, n) {
// 支払額を求める
var payment = [];
//それぞれのクエリについて処理を行う
for (var i = 0; i < flows.length; i++) {
var from = flows[i][0];
var to = flows[i][1];
var amount = flows[i][2];
var fromIndex = participants.indexOf(from);
var toIndex = participants.indexOf(to);
// fromとtoが同じ参加者の場合は，支払いが不要
if (fromIndex === toIndex) {
continue;
}
//代表根を求める，これらの代表根は同じである
var Root = parent;
// from->toを，from->RootとRoot->toに分解する
// from->Rootの支払い
payment.push([from, participants[Root], amount]);
// Root->toの支払い
payment.push([participants[Root], to, amount]);
}
// 逆向きの支払いを相殺する
var arr = new Array(n);
for (var i = 0; i < n; i++) {
arr[i] = new Array(n).fill(0);
}
for (var i = 0; i < payment.length; i++) {
var from = participants.indexOf(payment[i][0]);
var to = participants.indexOf(payment[i][1]);
var amount = payment[i][2];
arr[from][to] += amount;
arr[to][from] -= amount;
}
// 結果を格納
var result = [];
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
if (arr[i][j] < 0) {
result.push([participants[i], participants[j], Math.abs(arr[i][j])]);
}
}
}
return result;
}
function main() {
var participants = readParticipantList();
// デバッグ: 参加者リストを表示
Logger.log(participants);
var flows = readFlows();
// デバッグ: フローデータを表示
for (var i = 0; i < flows.length; i++) {
Logger.log(flows[i]);
}
var n = participants.length;
var tree = initUnionFindTree(n);
// union処理
// flows[i] = [from, to, amount]において，fromとtoを併合する
for (var i = 0; i < flows.length; i++) {
var from = flows[i][0];
var to = flows[i][1];
var fromIndex = participants.indexOf(from);
var toIndex = participants.indexOf(to);
unite(tree, fromIndex, toIndex);
}
//デバッグ: Union-Find木の状態を表示
//参加者それぞれにおいて，自分の根を表示
for (var i = 0; i < n; i++) {
Logger.log(participants[i] + " : " + findRoot(tree, i));
}
// 全体がいくつのグループに分かれているかを求める
var group = [];
for (var i = 0; i < n; i++) {
var root = findRoot(tree, i);
if (!group.includes(root)) {
group.push(root);
}
}
Logger.log("グループ数: " + group.length);
// それぞれのグループの参加者をリストアップ
var groupList = [];
for (var i = 0; i < group.length; i++) {
var member = [];
for (var j = 0; j < n; j++) {
if (findRoot(tree, j) === group[i]) {
member.push(participants[j]);
}
}
groupList.push(member);
}
// デバッグ: グループのリストを表示
for (var i = 0; i < groupList.length; i++) {
Logger.log(groupList[i]);
}
// groupごとに，対応するflowを切り出す
var groupFlows = [];
for (var i = 0; i < groupList.length; i++) {
var member = groupList[i];
var temp = [];
for (var j = 0; j < flows.length; j++) {
if (member.includes(flows[j][0]) && member.includes(flows[j][1])) {
temp.push(flows[j]);
}
}
groupFlows.push(temp);
}
// デバッグ: グループごとのflowを表示
for (var i = 0; i < groupFlows.length; i++) {
Logger.log("グループ" + i + "のflow");
for (var j = 0; j < groupFlows[i].length; j++) {
Logger.log(groupFlows[i][j]);
}
}
// groupごとに計算
// すべての参加者を1回ずつ代表根とし，最も支払いの手数が少ないものを採用する
var minPayment = [];
for (var i = 0; i < groupList.length; i++) {
Logger.log("グループ" + i + "の計算");
var member = groupList[i];
var m = member.length;
var min = 1000000000;
var parent = 0;
for (var j = 0; j < m; j++) {
var payment = calcpayment(groupFlows[i], member, j, m);
// デバッグ: 支払いの手数を表示
Logger.log("代表根: " + member[j]);
Logger.log("支払いの手数: " + payment.length);
if (payment.length < min) {
min = payment.length;
parent = j;
}
}
minPayment.push(calcpayment(groupFlows[i], member, parent, m));
}
// デバッグ: 最小の支払いを表示
for (var i = 0; i < minPayment.length; i++) {
for (var j = 0; j < minPayment[i].length; j++) {
Logger.log(minPayment[i][j]);
}
}
// 前回の結果をクリア
var sheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName('結果出力');
sheet.getRange('B3:D100').clearContent();
// "結果出力"シートB3:D3以下に，minPaymentの内容を出力する
for (var i = 0; i < minPayment.length; i++) {
for (var j = 0; j < minPayment[i].length; j++) {
sheet.getRange(3 + i, 2, minPayment[i].length, 3).setValues(minPayment[i]);
}
}
}おわりに
グラフをパッカーンとかしたらもっと少ない回数が出てきそうだけどよくわかりません
みなさんもPayPay等送金可能なサービスを使いましょう．
結局現金でやり取りすると面倒です．
謝辞
ぺたふぁんのみなさま
こんな話に付き合ってくれた友人各位
この記事が気に入ったらサポートをしてみませんか？