問題

https://atcoder.jp/contests/agc007/tasks/agc007_b

考え方

$x = 1, x = 2*n-1$ の場合は中央値になりえないので必ず NO になる。そうでない場合、例えば $N=4, x=2$ の場合は可能かどうかというと可能である。 $O(N!)$ で実験すると容易に分かる。

上の段の中央値になる場合の条件について考えていこう。

1列目	2列目	3列目
-	`2`	-
`*`	`*`	`*`

まず上の段で 2 になる場合は、必ず下の段(簡略のためにソート後としておく)の真ん中の値は 2 になる。そうでない場合は上の段の中央値になりえない。また少なくとも 1 つは 2 以下の数になっていて、少なくとも 1 つは 2 以上の数になっている。

このように構築すると上の段の真ん中の値は 2 になって、上の段の真ん中左の値は 2 以下の数になる。上の段の真ん中右の値は 2 以上の数になっている。よって最終的には 2 が一番上の数になる。

つまり、構築する数列を $\{a_N\}$ とし、一番下の段の中央の index を $k$ とすると $a_k = x, a_{k-1} = x-1, a_{k+1} = x+1$ が必要条件である。十分条件ではない(一番上の数が $x$ だからといって $a_k = x, a_{k-1} = x-1, a_{k+1} = x+1$ が満たされるわけではない。一番下の関係ないマスは任意に埋めていくだけでOK。