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$ も入るので、通常はこちらの要素数が大きくなりそうな気がする。

「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 の要素数になる。

集合 $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がそれなりの数、出る。'=', '<' に関しては証明済だし、コーナーケースの考慮漏れにしては数が多い。

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

基本的に、要素のかぶりが少ないと、◣が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$ で作成が可能であることがわかる。

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

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

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

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