Tenka1 Programmer Contest C,D

C - Align

問題

  • $N$ 個の整数 $A_1,A_2,\ldots,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,\ldots,N\}$ の部分集合の組み合わせ $(S_1,S_2,\ldots,S_k)$ を考える
  • 以下の条件を満たすものが存在するか判定し、 存在する場合はひとつ構成せよ
    • $1,2,\ldots,N$ のうちどの整数も、$S_1,S_2,\ldots,S_k$ のうちちょうど2つに含まれる
    • $S_1,S_2,\ldots,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

問題

解法



programming_algorithm/contest_history/atcoder/2018/1027_tenka1_2018.txt · 最終更新: 2018/10/29 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0