AtCoder diverta 2019 Programming Contest 2 C - Successive Subtraction

irisruneです。他言語に慣れているとpythonの変数名にキャメルケースを使おうとするたびに警告を出されるのはもやもやします。

B問題より簡単という噂を聞きましたが全然そんなことはなかったです。見た目以上に考えることが多く、ACするのに5回かかりました。

import sys
import collections as col
import bisect
import numpy as np


def main():
    n = int(input())
    aarray = [int(e) for e in input().split()]
    aarray.sort()
    record = []
    endpoint = max(1, bisect.bisect(aarray, 0))
    aqueue = col.deque(aarray)
    while len(aqueue) > endpoint + 1:
        amax = aqueue.pop()
        amin = aqueue.popleft()
        record.append((amin, amax))
        aqueue.appendleft(amin - amax)
    amax = aqueue.pop()
    while len(aqueue) > 0:
        amin = aqueue.popleft()
        record.append((amax, amin))
        amax -= amin
    print(amax)
    for r in record:
        print(r[0], r[1])


main()

$x'-(y'-z')=(x'-y')+z'$ という性質に気付くかどうかが3割くらいだと思います。アルゴリズムが組めるかが4割くらい、コーナーケースの考慮と実装が3割くらいじゃないでしょうか。

上記の性質を使うことで、 $y'=A_i\leq0,z'=A_j\gt0$ となるように操作を行えば解くことができます。…と言いたいところですが、すべての $i$ について $A_i\gt0$ となる場合を考える必要があります。なぜかといえば、 $y'=A_i$ となる $A_i$ が最低1つは必要となるためです。