Codeforces Global Round 6 D. Decreasing Debts

問題概要

$n$ 人の人がいて、「人 $a_{i}$ が人 $b_{i}$ に $d_{i}$ 円借りた」という貸し借り履歴が $m$ 個与えられる。それらの貸し借り履歴を合計した、人 $a$ が人 $b$ に借りている金額を $d(a, b)$ と表す。

この貸し借りの状態を、次のような規則で操作することができる。

操作規則1：であるような人について、を減らし、を増やす。
- ただし $0 \le z \le \min(d(a, b), d(c, d))$ である $z$ を選ぶ必要がある。つまり $d(\cdot, \cdot) \lt 0$ になるような操作は許されない。
操作規則2：人 $a$ について、 $d(a, a)$ を $0$ にする。

この操作を繰り返して、全ての人のペア $(a, b)$ に対しての $d(a, b)$ の総和を最小にしたい。そのような操作後の状態としてあり得るものを1つ求めよ。

制約

$1 \le n \le 10^{5}$
それぞれの貸し借り履歴について、 $0 \le d_{i} \le 10^{9}$

解法

それぞれの人 $i$ について、誰か（自分自身含む）から借りている金額の合計を $X_{i} = \sum_{x} d(i, x)$ とします。同様に誰かに貸している金額の合計を $Y_{i} = \sum_{x} d(x, i)$ とします。

このとき借りている金額をプラス、貸している金額をマイナスとしたときの合計を $s_{i} = X_{i} - Y_{i}$ とします。これはいわばその人の「収支合計」です。問題で示されている規則で移動を行ったとき、各人について収支合計 $s_{i}$ の値は変わりません。

また問題で最小化すべき値を $D$ とすると、 $D = \sum_{i} X_{i} = \sum_{i} Y_{i}$ が成立します。つまり $\sum_{i}(X_{i} + Y_{i})$ を最小化することで $D$ も最小化することができます。

そのため理想的な状態は、全ての $i$ について

$s_{i} \gt 0$ であるような $i$ については、 $X_{i} = s_{i}$ かつ $Y_{i} = 0$ である。
$s_{i} \lt 0$ であるような $i$ については、 $X_{i} = 0$ かつ $Y_{i} = |s_{i}|$ である。
$s_{i} = 0$ であるような $i$ については、 $X_{i} = Y_{i} = 0$ である。

が成り立っている状態です。そして実は、この状態を必ず達成することが可能です。

理想的な状態を言い換えると、「誰かから正の金額を借りていて、かつ誰かに正の金額を貸している」という状態の人が存在しない、ということです。そのような貸し借り関係を1つずつ解消していくことを考えます。

人 $i$ について $d(a, i) \gt 0$ かつ $d(i, b) \gt 0$ であるようなペア $(a, b)$ が存在するとします。 $a = i$ または $i = b$ であれば操作規則2で解消できるので、そうではないとします。このときの関係は以下のようになっています。（ただし $a = b \ne i$ というパターンも存在します）

f:id:betrue12:20191221161145p:plain

このとき操作規則1に従い、 $z = \min(d(a, i), d(i, b))$ として $d(a, i), d(i, b)$ を $z$ 減らし $d(a, b), d(i, i)$ を $z$ 増やします。このとき $d(i, i)$ は操作規則2で消去できるので、関係は以下のように変更されます。（もし $a = b$ なら $d(a, b)$ も消去されます）

f:id:betrue12:20191221161152p:plain

この操作手順によって、 $i$ については $X_{i}, Y_{i}$ がともに $z$ 減少します。そして $a, b$ について、 $X, Y$ の値が増加することはありません。

つまりこの操作手順について、

上記で書いたような $(i, a, b)$ の組が存在する限り、操作を行うことで $\sum_{i}(X_{i} + Y_{i})$ を減少させることができる。
$\sum_{i}(X_{i} + Y_{i})$ が減少する操作を無限回数行うことはできないので、この操作は有限回で終了するはずである。
つまり有限回の操作によって $(i, a, b)$ の組として取れるものが存在しなくなり、それはつまり「理想的な状態」になっている。

という議論が成り立ち、必ず有限回の操作で理想的な状態が達成できることが示されました。

あとはこれをシミュレーションしても良いのですが…もっと簡単な解法があります。一度理想的な状態にしてしまった後は、その状態から操作規則1を繰り返すことで任意の理想的な状態に移行することができます。

これを理解するため、以下のように図示してみます。 $d(a, x) = V$ という状態を、「債務者 $a$ が現金を $V$ 円借りていて、金貸し $x$ が $a$ に1円を取り立てできる権利（債権）を $V$ 個持っている」とイメージします。

f:id:betrue12:20191221154911p:plain

この図において操作規則1を適用することは、金貸しの間で債権を交換するという操作に相当します。任意の回数交換を行えるので、それぞれの金貸しが持っている債権の総数が変わらない限り任意の状態を実現できるということになります。

そうと分かれば出力する答えとしては作りやすいものを1通り作ってしまえば良いです。これは例えば以下のように構成することができます。

各人について $s_{i}$ を計算し、正である人リストと負である人リストを作る。
リストに人が残っている限り以下を繰り返す。
1. 正である人 $p$ と負である人 $m$ を1人ずつとる。
2. $z = \min(s_{p}, |s_{m}|)$ として $d(p, m) = z$ という組を答えに追加する。
3. $s_{p}$ と $|s_{m}|$ をともに $z$ 減らし、 $0$ になった人をリストから除外する。