Tenka1 Programmer Contest C,D
C - Align
問題
- $N$ 個の整数 $A_1,A_2,...,A_N$ を好きな順に並び替える
- 隣り合う2数の差の合計の最大値を求めよ
例
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)
D - Crossing
問題
- 整数 $N$ が与えられる
- $\{1,2,...,N\}$ の部分集合の組み合わせ $(S_1,S_2,...,S_k)$ を考える
- 以下の条件を満たすものが存在するか判定し、 存在する場合はひとつ構成せよ
- $1,2,...,N$ のうちどの整数も、$S_1,S_2,...,S_k$ のうちちょうど2つに含まれる
- $S_1,S_2,...,S_k$ のどの2つの集合をとっても、それらに共通して含まれる要素はちょうど1つである
例
N=6
1 2 3 4 5 6
S1 o o o
S2 o o o
S3 o o o
S4 o o o
- どの整数も、ちょうど2つの集合に含まれる（縦に見た時に、同じ列の
'o'はどれも2つ） - どの集合も、共通要素はちょうど1つ
解法
まず、適当に大きな $N$ を考えて、$S_1$ をたとえば$\{1,2,3,4\}$の4つの要素からなるとする。すると、
- 1を含む集合はあと1つ
- 2を含む集合はあと1つ
- 3を含む集合はあと1つ
- 4を含む集合はあと1つ
- 上記4つは全て別々の集合（でないと共通要素が2つになってしまう）
- それ以外に集合は作れない（でないと$S_1$との共通要素が0になってしまう）
よって、作る集合の数は5つでないといけないと分かる。
次に各集合の要素数を考える。たとえば上で「1を含むもう1つの集合」の要素数が5だったりすると、今度はその集合をメインに同じことを考えると、作る集合の数は6にならないといけなくなり、矛盾する。よって、集合の要素数は全て同じ。
一般化すると、
- 全ての集合の要素数は同じ
- 1つの集合の要素数を $k$ とすると、作る集合の数は $k+1$ 個
- 全集合をまとめた $k(k+1)$ 個の数字に各整数は2個ずつ現れるので、$N=k(k+1)/2$
この形で表せない $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)
E - Equilateral
問題
例
解法
