diverta 2019-2C

はじめに

予定していなかったが、とりあえずやってみて惨敗。Python仕様の不理解によりバグっていただけであった。
Cまで進まなかったので、反省のためCをやる。

C - Successive Subtraction

問題：数列が与えられ、その中の2個x,yを取り出して、x-yを書き込み、繰り返し最後に残る1個の最大値と操作を答えなさい。

最後の計算でx,yの差が最大であればよいため、xlast=最大値high、ylast=最小値lowになる必要がある。
負数列[m1,m2,m3・・・]、正数列[p1,p2,p3・・・]とすると以下のように表される。

high=x_{0}-m_{1}-m_{2}-m_{3}-\cdots\\
low=y_{0}-p_{1}-p_{2}-p_{3}-\cdots

x0は数列の最大値、y0は数列の最小値から持ってくればよい。なお、x0,y0の符号はどうでもよい。
後は、上記式から負数だったらhighから引き、正数だったらlowから引いて行くだけである。
操作に関してはリストに入れておく。

atcoder.py

n = int(input())
a = list(map(int,input().split()))

ans = []
a.sort()
low = a[0]
high = a[-1]
for i in a[1:-1]:
    if i>0:
        ans.append([low,i])
        low = low - i
    else:
        ans.append([high,i])
        high = high - i

ans.append([high,low])
print(high-low)
for x,y in ans:
    print('{0} {1}'.format(x,y))