Xmas Contest 2019

Xmas Contest 2019

リアルタイム参加ならず。コンテスト名に反して(?)骨のある問題が多い。

B - Set of Integers

問題

  • 整数 $N$ と、>,=,< のどれか1つの不等号 $op$ が与えられる
  • 以下の条件を満たす整数集合 $X$ を構築せよ
    • 要素数は $N$
    • 各要素は $0~10^9$ の範囲内
    • 各要素は全て相異なる
    • $X$ の「任意の2要素の和」の集合を $S$、「任意の2要素の差」の集合を $D$ とすると、$|S| op |D|$ を満たす
      • ここで、任意の2要素は同じ数字でもよい
      • 差は、正負を区別する
  • 存在しない場合はその旨を示せ
  • $1 \le N \le 2019$

解法

取っつきやすそうに見えてやたらむずい。

$D$ はある数 $a$ が入れば $-a$ も入るので、通常はこちらの要素数が大きくなりそうな気がする。

SとDの表

「100ますけいさん」で使ったような2次元の表を埋めていくことを考える。

+ 0 1 2 3    -  0  1  2  3
0 0 1 2 3    0  0 -1 -2 -3
1 1 2 3 4    1  1  0 -1 -2
2 2 3 4 5    2  2  1  0 -1
3 3 4 5 6    3  3  2  1  0

足し算は、対角線を挟んで両側は絶対同じになるので、別々の要素が入るとしたら「◣」+「\」に限られる。(◣は対角線を含まない三角行列を示す)

引き算は、対角線は絶対0になり、「◣」と「◥」は正負だけ違って対称なので、2×「◣」+1 の要素数になる。

SとDの性質

集合 $X$ の全要素に、同じ数をかけたり、同じ数を足したり引いたりしても、$|S|$ や $|D|$ は変わらない。

この性質を使って、$X$ の最小の数字を“0”に揃えることが出来る。

実際にやってみる

試しに $X$ を $\{0,1,\ldots,N-1\}$ として計算してみると、$|S|,|D|$ は一緒になる。中身を見ると、

+ 0 1 2 3    -  0  1  2  3
0 0 1 2 3    0  0 -1 -2 -3
1 1 2 3 4    1  1  0 -1 -2
2 2 3 4 5    2  2  1  0 -1
3 3 4 5 6    3  3  2  1  0

$S$ の方の「◣+\」の部分は $0~2N-2$ の整数が満遍なく敷き詰められ、$D$ の方の「◣」部分は $1~N-1$ の整数が満遍なく敷き詰められている。 よって、重複を除くと両方とも $2N-1$ 個の要素数となる。

ちょっとこれを崩して、例えば $\{0,1,\ldots,N-2,N\}$ とかにすれば、$D$ の方が大きくなる。

+ 0 1 2 4    -  0  1  2  4
0 0 1 2 4    0  0 -1 -2 -4
1 1 2 3 5    1  1  0 -1 -3  |S|=8
2 2 3 4 6    2  2  1  0 -2  |D|=9
4 4 5 6 8    4  4  3  2  0

$S$ はちょっと $X$ が密でなくなるとすぐに間が抜けてしまうのに対し、$D$ はなかなか頑健で、減りにくい。

なので、以下の解法で投げてみる($N$ が小さいときのケースは適宜考慮する)

  • '>' : 不可能(無証明)
  • '=' : 0~N-1
  • '<' : 0~N-2, N

すると、WAがそれなりの数、出る。'=', '<' に関しては証明済だし、コーナーケースの考慮漏れにしては数が多い。

やはり、'>' でも可能なケースがあるらしい。

S>Dの考察

基本的に、要素のかぶりが少ないと、◣が2倍になる $|D|$ の方が有利である。なので、なるべく $X$ は密な方がいいと考える。

$X$ の最小の要素を0に揃えたときに、最大の要素を $b$ とする。

最大値最小値で考えると、$S$ は $0~2b$ の要素、$D$ の「◣」は $1~b$ の要素が入る。 両者とも完全に隙間無く埋められる場合は、$0~N-1$ の時のように $2b+1$ で等しくなる。

増やすのはこれ以上増やしようがないので、$|S| \gt |D|$ にしたければ $|S|$ をなるべく保ったまま $|D|$ を減らすしかない。

$1~b$ まででどれか1つ、引き算によって作れない要素が存在するようにする。これを $w$ とする。必然的に $-w$ も無理になり、$|D|$ は2減る。

つまり、$S$ で作れなくなる要素を1個までに抑えることが出来れば、$|S| \gt |D|$ が達成できる。

w = b-3 として、数字の選び方の制約例

0  1  2  3  ...  b-3  b-2  b-1  b    
         x        x                  0,bは存在が確定しているので、3,b-3は使えない
   !  ?                !    ?        (1,b-2),(2,b-1)のそれぞれからどちらか1つしか使えない
                                     この条件を満たしつつ、Sで作れなくなる要素が1個以下になるようにする

$w$ は大きい方が引き算で作れる数字の組合せが減るので、大きい方から試していく。

$w=b-1$ の時、$1,b-1$ が使えなくなる→足し算表に $1,2b-1$ を作ることが不可能になる

$w=b-2$ の時、$2,b-2$ と「$1,b-1$ のいずれか」が使えなくなる。1を使うとすると、$2b-2,2b-1$ を作ることが不可能になる

$w=b-3$ の時、$3,b-3$ と「$1,b-2$ のいずれか」と「$2,b-1$ のいずれか」が使えなくなる

                       b-3 b-2 b-1
0  _  _  x  4  ...  b-4  x  _  _  b
   1                        x          1を仮置き(b-2は使用不能)
                                       この時点で、2b-3 を作ることが不可能になる
                                       (b+b-3 or b-1+b-2 しかないが、両方無理)
   1  x                     x          2を使わないと、3が作れなくなる
   1  2                     x  x       2を使うと、2b-2,2b-1が作れなくなる→破綻

1を置かない場合に関しては、対称性のため考慮しなくてよい。(全要素に $\times -1 + b$ したら同じになる)

$w=b-4$ の時

0  _  _  _  x  5  ...  b-5  x  _  _  _  b
   1                           x             1を仮置き(b-2は使用不能)
   1  2                        x  x          2を仮置きすると、2b-4,2b-3が作成不可(×)
   1  x  3                     x b-2 x       3を仮置きすると、2b-3,2b-1が作成不可(×)
   1  x  x  x                  x b-2 b-1     3を置かないと、3,4が作成不可→破綻

$w=b-5$ の時(△は $S$ で作れない数が1個決定したこと、×は2個以上出来てしまったことを示す)

0  _  _  _  _  x  6  ...  b-6  x  _  _  _  _  b
   1                              x                1を仮置き
   1  2                           x  x               2を仮置き→2b-5が作成不可(△)
   1  2  x  x                     x  x b-2b-1          2b-4,2b-1を作るためには、それぞれb-2,b-1が必須→5が作成不可(×)
   1  x  3                        x b-3 x            3を仮置き→2b-5が作成不可(△)
   1  x  3  x                     x b-3 x b-1          2b-1を作るためにはb-1が必須→5が作成不可(×)
   1  x  x  x                     x b-3b-2b-1        2,3が使用不可→3が作成不可→b-1が必須→4,5も作成不可→破綻

$w=b-6$ の時……できた!

0  _  _  _  _  _  x  7  ...  b-7  x  _  _  _  _  _  b
   1                                 x                 1を仮置き
   1  2                              x  x                2を仮置き
   1  2  x                           x  x b-3            →b-3を使用しないと2b-6,2b-5が作成不可に
   1  2  x  4                        x  x b-3 x            4を仮置き→2b-5が作成不可(△)
   1  2  x  4  x                     x  x b-3 x b-1        →2b-1を作るためにb-1が必要→達成

これで、集合 $D$ に $b-6, -(b-6)$ を入れず、かつ $S$ で作れなくなるのは $2b-5$ の1つのみであるような組合せが見つかった。

$0~b$ の間に7個の使えない数字が入っているので、$N=b+1-7$、つまり $b=N+6$ となる。

長さ制限

この考察では、中央にある程度の長さの $7~b-7$ が存在するのを前提としていた。

例えば '7' は $X$ に7が無いと作れないし、'10' は8か9がないと作れない。

しかし、中央部分が存在しないか短いと、それらが対岸(b-○側)の作れない数に該当してしまい、$S$ で作れない数が2個以上になることがある。

作り方はもうわかっているので実際に試してみればよい。すると、$N \ge 9$ で作成が可能であることがわかる。

あと1個

他の人の解答を見て、$N=8$ の時も可能なケースがあることを知る。

見ると、$D$ から4個減らし、$S$ から3個減らすことで実現していた。

どうやって見つけたらいいのか見当が付かない。

まぁ……$N \ge 9$ で可能までわかれば、8以下は全探索できる範囲ではある。

# 確認用
def check(grp, op):
    pls, mns = set(), set()
    for i in grp:
        for j in grp:
            pls.add(i + j)
            mns.add(i - j)
    lp, lm = len(pls), len(mns)
    correct = (lp < lm and op == '<') or (lp == lm and op == '=') or (lp > lm and op == '>')
    # print(lp, lm, correct)
    if correct:
        print(grp)

# 確認用
def check_table(grp):
    import numpy as np
    lst = np.array(sorted(grp))
    col_v = np.repeat(lst[:, np.newaxis], len(lst), axis=1)
    col_h = np.repeat(lst[np.newaxis, :], len(lst), axis=0)
    print(col_v + col_h)
    print(col_v - col_h)


def solve(n, op):
    if op == '=':
        print(*range(n))
        return

    if op == '<':
        if n < 3:
            print('Merry Christmas!')
        else:
            print(n, *range(n - 1))
        return

    if n < 8:
        print('Merry Christmas!')
        return
    if n == 8:
        print(0, 2, 3, 7, 10, 11, 12, 14)
        return
    b = n + 6
    ans = {0, 1, 2, 4, b - 3, b - 1, b}
    ans.update(range(7, n))
    print(*ans)


n, op = input().split()
n = int(n)
solve(n, op)

このウェブサイトはクッキーを使用しています。 Webサイトを使用することで、あなたはあなたのコンピュータにクッキーを保存することに同意します。 また、あなたはあなたが私たちのプライバシーポリシーを読んで理解したことを認めます。 同意しない場合はウェブサイトを離れてください。クッキーに関する詳細情報
programming_algorithm/contest_history/atcoder/2019/1224_xmascon19.txt · 最終更新: 2019/12/27 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0