Blitz Round #25 A - Sum vs MEX

サイト: EOLYMP
コンテスト: Blitz Round #25
問題: A - Sum vs MEX

2026年10月4日

問題の概要

$1$ から $n$ の順列 $p$ のうち、すべての $i$ ( $1 \le i \le n$ ) について

\sum_{j=1}^{i} p_j \text{ が } \mathrm{MEX}(p_1, \ldots, p_i) \text{ で割り切れる}

を満たすものを 1 つ構築するか、存在しないことを判定する問題です。ここでの $\mathrm{MEX}$ は「含まれない最小の正の整数」です。

$1 \le n \le 2 \cdot 10^5$ 、テストケースの $n$ の総和は $2 \cdot 10^5$ 以下

正確な問題文は元の問題ページを見てください。

解法

$n$ が奇数のとき：存在しない

$i = n$ のとき、 $p_1, \ldots, p_n$ には $1$ から $n$ がすべて含まれるので $\mathrm{MEX} = n + 1$ 、総和は $\frac{n(n+1)}{2}$ です。

\frac{n(n+1)}{2} \div (n + 1) = \frac{n}{2}

なので、割り切れるのは $n$ が偶数のときだけです。よって $n$ が奇数なら答えは NO です。

$n$ が偶数のとき： $1$ を最後に置く

$1$ を最後に置くと、 $i < n$ では $p_1, \ldots, p_i$ に $1$ が含まれないので $\mathrm{MEX} = 1$ となり、条件は常に満たされます。

$i = n$ のときは上で見たとおり、 $n$ が偶数なら割り切れます。

したがって、たとえば $p = (2, 3, \ldots, n, 1)$ が条件を満たします。

解答コード

Python

for _ in range(int(input())):
    N = int(input())
    if N & 1:
        print("NO")
    else:
        ans = list(range(2, N + 1)) + [1]
        print("YES")
        print(*ans)