Tenka1 Programmer Contest C,D

Tenka1 Programmer Contest

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通り考えられるので、両方試す。

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$ の配列に順に埋めていけばいい。

E - Equilateral