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,...,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,...,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)
