1 2 3 4 5 ↓ 2 5 1 4 3 \/ \/ \/ \/ 3 +4 +3 +1 = 11
並び替えた後の数列を、偶数番目と奇数番目にわけると、どちらかが中央値以上、どちらかが中央値以下に分けられる。
5 4 2 1 3
そこで、中央値で区切ってみると、端以外は「中央値との差分」×2、端は×1の合計となる。
5 4 2/ \2 1/ \1 -------------------3 /1 2\ /2 0\ 2 1 3
なので、1回しかカウントされない端に、中央値に近い2数を持ってくれば、それが最大となる。
$N$ が奇数の時は中央値に近い2数が2通り考えられるので、両方試す。
import sys n = int(input()) aaa = [int(line) for line in sys.stdin.readlines()] aaa.sort() if n % 2 == 0: m1, m2 = aaa[n // 2 - 1], aaa[n // 2] mid = sum(abs(a - m1) for a in aaa) ans = mid * 2 - (m2 - m1) else: m1, m2, m3 = aaa[n // 2 - 1], aaa[n // 2], aaa[n // 2 + 1] mid = sum(abs(a - m2) for a in aaa) ans = mid * 2 - min(m2 - m1, m3 - m2) print(ans)
N=6 1 2 3 4 5 6 S1 o o o S2 o o o S3 o o o S4 o o o
'o
'はどれも2つ)まず、適当に大きな $N$ を考えて、$S_1$ をたとえば$\{1,2,3,4\}$の4つの要素からなるとする。すると、
よって、作る集合の数は5つでないといけないと分かる。
次に各集合の要素数を考える。たとえば上で「1を含むもう1つの集合」の要素数が5だったりすると、今度はその集合をメインに同じことを考えると、作る集合の数は6にならないといけなくなり、矛盾する。よって、集合の要素数は全て同じ。
一般化すると、
この形で表せない $N$ は不可能とわかる。
そこまでわかれば、割り振り方を実験してみる。$N$ ではなく $k$ を基準にして考えてみる。
k=4 1 2 3 4 5 6 7 8 9 10 S1 o o o o S2 o あと3つ S3 o あと3つ S4 o あと3つ S5 o あと3つ
これを見ると、$S_2~S_5$ で残された各あと3つの決め方は、$k=3$ の時と全く同じ方法が使えることに気付く。
1 2 3 4 5 6 7 ... S1 o o o o S2 o o o o S3 o o あと2つ S4 o o あと2つ S5 o o あと2つ
さらに $k=3$ の決め方は $k=2$ に分解できる。
1 2 3 4 5 6 7 8 9 10 S1 o o o o S2 o o o o S3 o o o o S4 o o o o S5 o o o o
よって、$N=k(k+1)/2$ で表せさえすれば、再帰的に割り振り方が存在すると言える。
具体的に各集合の数字を書き出してみると、
N = 15 1 2 3 4 5 | o-----------o 1 6 7 8 9 | o o--------o 2 6 10 11 12 | | o o-----o 3 7 10 13 14 | | | o o--o 4 8 11 13 15 | | | | o o 5 9 12 14 15 | o o o o o
なので $(k+1) \times k$ の配列に順に埋めていけばいい。
def check(n): i = 1 while n > 0: n -= i if n == 0: return i i += 1 return False def solve(n): k = check(n) if k == False: print('No') return buf = [[k] + [0] * k for _ in range(k + 1)] t = k u = 1 for i in range(k): buf[i][i + 1:i + t + 1] = list(range(u, u + t)) for j in range(t): buf[i + j + 1][i + 1] = u + j u += t t -= 1 print('Yes') print(k + 1) print('\n'.join(' '.join(map(str, b)) for b in buf)) n = int(input()) solve(n)