AtCoder Regular Contest++ 220 A,B,C,D問題メモ
- A - Sum of Reciprocals of Squares
  - 問題文
  - 制約
  - 解法
- B - Incomplete Shuffle
  - 問題文
  - 制約
  - 解法
- C - Range Increment
  - 問題文
  - 制約
  - 解法
- D - Long Trail
  - 問題文
  - 制約
  - 解法
  - 参考

AtCoder Regular Contest++ 220 A,B,C,D問題メモ

AtCoder Regular Contest++ 220

A - Sum of Reciprocals of Squares

問題文

正整数 $N$ が与えられます。
以下の条件を全て満たす正整数列 $A=(A_1,A_2,\ldots,A_N)$ が存在するか判定し、存在する場合は一つ求めてください。
- $1\le A_i\le 10^6$
- $\displaystyle \sum_{i=1}^N \frac1{A_i^2}=1$

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 500$
$1\le N\le 10^5$
全てのテストケースにおける $N$ の総和は $10^5$ 以下
入力される値は全て整数

解法

「$\frac{1}{A_i}$ の和が $1$ になる」ものは過去に関連問題があった気がするけど（参考:エジプト式分数）、今回は $\frac{1}{A_i^2}$ の和を $1$ にしろという問題。

$N=k$ の時の答えが $(a_1,...,a_k)$ だったとして、 1つの要素を取り除き、代わりにその2倍の値を $4$ 個入れても、総和は1に保たれる。

N=7
( 2     2     2     4      4      4      4  )
 1/4 + 1/4 + 1/4 + 1/16 + 1/16 + 1/16 + 1/16 = 1

N=10
( 2     2     4      4      4      4      4      4      4      4  )
 1/4 + 1/4 + 1/16 + 1/16 + 1/16 + 1/16 + 1/16 + 1/16 + 1/16 + 1/16 = 1

つまり、$N=k$ が可能なら $N=k+3$ も構築できる。$N \mod{3}$ で考えればよい。

$N \equiv 1 \mod{3}$ の時は $N=1$ からスタートすれば自明だが、 $N \equiv 0,2 \mod{3}$ の時は、小さいところでは解が見つからない。

$A_i \in (2,3,6)$ のみを使う場合を全探索するなどすると、$N=6,8$ で答えが見つかることがわかる。

これらは、$\frac{1}{4}=\frac{1}{9}+\frac{1}{9}+\frac{1}{36}$ という変換を使う必要があり、 $N=1$ の答えから「1つ取り出して $m$ 倍の値を $m^2$ 個入れる」という操作の繰り返しでは見つけることはできない。

Python3

後から考えたら上の解法の方が絶対短く解けるのだが、なんか気づけなかった。

以下のコードは、少しまどろっこしいことをしている。

「1つ取り出して、代わりに2倍の値 $4$ 個」と同様に、 3倍の値を $9$ 個、4倍の値を $16$ 個、、、加えることでも構築でき、$k+8,k+15,...$ も可能となる。

よって、$i=2,3,...$ について $i^2-1$ のアイテムを何個でも選んでよいナップサックを解き、 $N-1$ が作れたら復元し、$k=1$ の時からシミュレーションしていく。

from fractions import Fraction
from itertools import combinations_with_replacement

from heapq import heappop, heappush


def naive(n):
    for ppp in combinations_with_replacement((2, 3, 6), r=n):
        t = 0
        for a in ppp:
            f = Fraction(1, a * a)
            t += f
        # print(t)
        if t == 1:
            return ppp
    return None


def solve(n):
    if n == 1:
        return [1]

    if n < 15 and n != 7:
        return naive(n)

    goal = 1 << n
    mask = (1 << (n + 1)) - 1
    can = 0b10
    dp = [0, can]
    for i in range(2, n):
        w = i * i - 1
        if w >= n:
            return None
        for _ in range(n // w):
            can |= can << w
            can &= mask
        dp.append(can)
        if goal & can:
            break

    facts = []
    b = goal
    for k in range(len(dp) - 1, 1, -1):
        w = k * k - 1
        while (b >> w) & dp[k]:
            b >>= w
            facts.append(k)
    ans = [1]
    for f in facts:
        a = heappop(ans)
        for _ in range(f * f):
            heappush(ans, a * f)
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    ans = solve(n)
    if ans is None:
        print('No')
    else:
        print('Yes')
        print(*ans)

B - Incomplete Shuffle

問題文

正整数 $N$ と長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N)$ が与えられます。
あなたは $A$ に対して $N-1$ 回の操作を行います。$i$ 回目 $(1\le i\le N-1)$ の操作は以下の通りです：
- $i \lt j \le N$ を満たす整数 $j$ を選び、$A_i$ と $A_j$ の値を入れ替える。
$N-1$ 回の操作を終えた後に $A_k=B_k$ を満たす $k$ $(1\le k\le N)$ の個数の最大値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 10^5$
$2\le N\le 3\times 10^5$
$1\le A_i,B_i\le N$
全てのテストケースにおける $N$ の総和は $3\times 10^5$ 以下
入力される値は全て整数

解法

swapによって“順列”を別の順列にマッチさせる問題はよくあるが、今回は“任意の整数列”なので、「$A$ と $B$ が多重集合として一致するとは限らない」「$A,B$ ともに同じ要素が含まれうるので、どれとどれを合わせに行くかの自由度がある」という点で、扱いが難しい。

サンプルの観察

サンプル1の2番目のケースに注目する。多重集合が一致しているのに、$N=5$ に対して答えは $2$ と小さい。

i  1 2 3 4 5
A  1 2 3 4 5
B  5 4 3 2 1

実際に先頭から貪欲に合わせにいくと、先頭2つを揃えた段階で早々と $A$ と $B$ は一致してしまう。だが、$i=3$ 以降でも“必ず”操作をしなければならないので、既に揃っているものはわざわざ崩さざるを得ず、最終的に $i=3$ 以降は $A_i=B_i$ とすることができない。

A  5 4 3 2 1    i=2 まで、Ai=Bi となるように貪欲に揃えた結果
B  5 4 3 2 1      (1と5, 2と4 をswap)

A  5 4 2 3 1    i=3 以降では、既に揃っているのに、操作はしなければならない。
B  5 4 3 2 1

一般に、順列をswapによってソートする操作を考える際は、「順列のサイクル分解」を考えることが多い。
今回、上例は $(1,5),(2,4),(3)$ という3サイクルに分解されるが、各サイクルから1要素ずつ、揃えられない要素が生じているように見える。

サイクル毎の考察

「$A_i$ を、最終的に $A_{P_i}$ に持っていきたい」ことを表す順列を $P=(P_1,...,P_N)$ とする。 $P$ は、$A_i=B_{P_i}$ となる $i$ の個数を最大化したものを想定する。

$P$ のサイクル分解を $(C_1,...,C_k)$、$C_i=\{v_{i,1},v_{i,2},...\}$ とする。

$v \in C_i$ について $A_v=B_{P_v}$ となる個数を、そのサイクルの「一致数」と呼ぶことにする。
全ての $v \in C_i$ に対して $A_v=B_{P_v}$ となることを、そのサイクルが「完全一致」であると呼ぶことにする。

各サイクルは、先頭から順に合わせにいくと、$|C_i|-1$ 回の操作によって全てが希望位置に揃う。しかしその後、既に希望位置にいる最後の要素（サイクル内で最大の $v$）に対しても swapが強制されると、希望位置から外れてしまう。

つまり、各サイクルに付き最大（$|C_i|-1$）個の要素しか希望位置に揃えられないということになる。
この時、あらかじめ決めておけば、揃えられない要素は必ずしもサイクル内の最後の要素である必要は無い。

例外は $P$ 全体が1つのサイクルを成す場合であり、この場合は全てを希望位置に揃えることが可能である。

ここまでの考察をまとめると、所与の $P$ に対して、以下のように答えを求めることができる。

$P$ をサイクル分解したとき、全体が1つのサイクルをなす場合
- 答えはサイクルの一致数
そうでない場合、各サイクルに対する以下の合計
- サイクルが完全一致の場合、一致数$-1$
- サイクルが完全一致でない場合、一致数

$P$ が複数サイクルからなる場合、完全一致サイクル1つにつき答えが $-1$ される。
だからといって作成可能な完全一致サイクルを敢えて組み替えて完全一致でなくす必要は無い。組み替えた時点で、既にそのサイクルの一致数は元から $-1$ 以上減っているので得しないためである。
$P$ は、全体の一致数を最大化するように決めてよい。

ただ、一致数最大ならどんな $P$ でも良いかというと、それも違う。
正しい答えが求まらないのは、「上手くすれば1つにまとめられる完全一致サイクル」が、「2つ以上の完全一致サイクル」に分かれているときであり、無駄に $-1$ されてしまう。これは、複数の完全一致サイクルに、同じ値が含まれる場合に発生する。

×                 ○
A  1  2  1  2 ..   A  1  2  1  2 ..   ×は2つのサイクルに分かれているが、
B  2  1  2  1 ..   B  2  1  2  1 ..   ○のように1つのサイクルにすることが可能。
P  2  1  4  3 ..   P  2  3  4  1 ..   完全一致サイクルはなるべく少なくする必要がある。

それを回避しつつ最大の一致数を求めるには、以下のような方法が考えられる。

以下のグラフを構築する。
- $A_i,B_i$ として出てくる要素の「値」を頂点番号としたグラフを考える。
- 各 $i$ に対し $A_i→B_i$ に有向辺を張る。

弱連結成分（辺の向きを無視した連結成分）毎に、
- 全ての頂点について、入次数＝出次数なら、1つの完全一致サイクルが構成可能である。
- そうでない場合、一致数は $\sum_{v \in C_i}\min(vの入次数,出次数)$ となる。

値が同じものは必ず同じサイクルになることが保証され、正しく答えが求まる。

Python3

from collections import defaultdict
from atcoder.dsu import DSU


def solve(n, aaa, bbb):
    uft = DSU(n)
    in_out_count = defaultdict(lambda: [0, 0])
    for i in range(n):
        a = aaa[i] - 1
        b = bbb[i] - 1
        in_out_count[a][1] += 1
        in_out_count[b][0] += 1
        uft.merge(a, b)

    ans = 0
    for grp in uft.groups():
        if grp[0] not in in_out_count:
            continue
        grp = set(grp)
        is_euler = True
        tmp = 0
        for a in grp:
            ic, oc = in_out_count[a]
            if ic != oc:
                is_euler = False
            tmp += min(ic, oc)
        if is_euler and tmp < n:
            tmp -= 1
        ans += tmp

    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    bbb = list(map(int, input().split()))
    ans = solve(n, aaa, bbb)
    print(ans)

C - Range Increment

問題文

整数 $N,M,K$ と長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。$A$ の各要素は $0$ 以上 $M$ 未満であることが保証されます。
あなたは整数列 $A$ に対して以下の操作を $0$ 回以上 $K$ 回以下行うことができます：
- $1\le l\le r\le N$ を満たす整数の組 $(l,r)$ を選び、$k=l,l+1,\ldots,r$ に対し $A_k$ を $(A_k+1) \bmod M$ で置き換える。
辞書順最小となる操作後の $A$ を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 3\times 10^5$
$1\le N\le 3\times 10^5$
$2\le M\le 10^9$
$1\le K\le 10^{15}$
$0\le A_i \lt M$
全てのテストケースにおける $N$ の総和は $3\times 10^5$ 以下
入力される値は全て整数

解法

DP定義

辞書順最小なので、$i$ を $0$ にするためなら、（$i-1$ までを最適化した上で）残っている回数を好きなだけ注ぎ込んでよい。

先頭から $i$ 毎に、以下のいずれかを決定していくことになる。他の選択肢（中途半端に操作する等）は辞書順最小になり得ない。

$A_i$ を $0$ にできるならする
残回数が足りず $A_i$ を $0$ にできないなら操作せず $A_i$ のままにする

区間に操作できるというのは、以下のように言い換えることができる。

$A_{i-1}$ に加算した回数までは、コスト $0$ で $A_i$ にも加算できる

だが、最適な操作回数は一意に決まるわけではなく、後の要素によって左右される。

具体例

M=10   操作回数Kは豊富にあるとして、全ての要素を0にするコストを考える

i  A    {Aiへの操作回数: 総操作回数}

1  2    { 8:8 }         8回操作すると0にできる

2  8    { 2:8, 12:12 }  以下の選択肢が発生する。
                        2:8  ... 直前に操作した8回の内2回をコスト0で使い8→10にする
                       12:12 ... 直前の8回をフルで使いさらに4回追加し8→20にする

ここで、次が例えば $A_3=3$ だとし、$0$ にするために7回操作する場合の総操作回数を考えると、

2:8 からの遷移の場合、コスト0で2回、追加で5回必要になるので、総回数は 8+5=13
12:12 からの遷移の場合、$i=2$ に操作した12回のうち7回をコスト0で使えるので、総回数はそのまま12
- →12:12 からの遷移の方が安い。

一方、$A_3=7$ だとし、$0$ にするために3回操作する場合の総操作回数を考えると、

2:8 からの遷移の場合、コスト0で2回、追加で1回必要になるので、総回数は 8+1=9
12:12 からの遷移の場合、$i=2$ に操作した12回のうち3回をコスト0で使えるので、総回数はそのまま12
- →2:8 からの遷移の方が安い。

$A_i$ を $0$ にするのに「$A_{i-1}$ への操作を利用してコスト $0$ で済ます」のか、「$A_{i+1}$ 以降のためにさらに操作回数を積み増す」のか、結果的にどちらが総回数が少なく済むかは単純に決めることは難しく、それぞれの場合を調べる必要がある。

よって以下のDPが考えられる。

$\mathrm{DP}[i,j]:=A_i$ までを辞書順最小にして、$A_i$ に加算した回数が $j$ 回の時の、総操作回数

ただし、このDPは $O(N^2)$ かかってしまう。これを工夫する。

DPの高速化

まず、$j$ の取り得る値は、

回数が足りず、$A_i$ には操作しないことにした場合
- $j=0$ のみ
操作して $0$ にした場合
- $M-A_i,2M-A_i,3M-A_i,...$
- どこまで続くかは、$A$ の並びによるが、最悪 $O(N)$。

なので、「$P_i:=A_i$ に加算した回数 $\mod{M}$」を新たに記録して、DPを以下のように置き換える。

$\mathrm{DP}[i,j]:=A_i$ までを辞書順最小にして、$A_i$ に加算した回数が $P_i+jM$ 回の時の、総操作回数
- $j$ は0-indexed。$j$ の最大値は $i$ により異なる

これにより $j$ の値が $0～$ の連番となり考えやすくなる。

更新は、

(a) $A_i=0$ または $A_i+P_{i-1} \ge M$ の場合

$A_i$ を $0$ にできる。$i-1$ の操作を利用してコスト $0$ で済ませることが常に可能。
積み増す場合は、$d=-(A_i+P_{i-1}) \mod{M}$

   j        0        1             2         3
DP[i-1]  [ ⓪       ①            ②   ]
           ↓↘     ↓     ↘     ↓     ↘
DP[i]    [ ⓪  min(⓪+d,①)  min(①+d,②)  ②+d ]    ※②+d>K の場合、末尾要素は除外

(b) $A_i \gt 0$ かつ $A_i+P_{i-1} \lt M$ かつ、条件 (c) に当てはまらない場合
- $A_i$ を $0$ にできるが、$j=0$ からはコスト $0$ で済ませることはできず、必ず積み増す必要がある
- 積み増すコストは(a)と同じ $d=-(A_i+P_{i-1}) \mod{M}$
- ```
   j            0             1         2
DP[i-1]  [     ⓪            ①        ②   ]
               ↓     ↙     ↓     ↙ ↓
DP[i]    [ min(⓪+d,①)  min(①+d,②)  ②+d ]    ※②+d>K の場合、末尾要素は除外
```
(c) $A_i \gt 0$ かつ $A_i+P_{i-1} \lt M$ かつ、$\mathrm{DP}[i-1]$ における $j$ の最大値が $0$ かつ $\mathrm{DP}[i-1,0]+d \gt K$ の場合
- $A_i$ を $0$ にすることはできない
- DP配列は変化せず

$P_i$ は、(a)(b)の場合は $P_i=-A_i \mod{M}$、(c)の場合は $P_i=0$ となる。

DP定義上は $j=2$ から $j=0$ などへもコスト0で遷移できるが、1つ下の $j$ にしか遷移しないと考えてよい。
コストが変わらないならなるべく多く操作しておいた方が、$i+1$ 以降の要素もコスト0にしやすく上位互換のためである。

更新方法がかなり規則的で、以下のように捉えることで効率の良い状態管理方法が見える。（細部は詰める必要があるが、大まかな言い換えとして）

グリッドを右か下に移動する
$i$ 回目の移動で右に移動するのはコスト $d_i$ かかる。下移動は常にコスト0
$i$ 回の移動後に、右から $j$ 列目にいるためのコストは？

これは、明らかに、$j$ ごとに「それまでのコスト $d_1,d_2,...,d_i$ で小さい方から $j$ 個の和」とするのが最適である。

よって元のDPも、以下の情報で管理できる。

$t_{\max}$: $\mathrm{DP}[i,j_{\max}]$
$S$: 現在有効な $d$ の値を管理する SortedList。値の追加と、最小値・最大値のpopができれば良い
- $j_{\max}=|S|$ に相当する。

(a) の場合、

$t_{\max}+=d$
$S$ に $d$ を追加
$t_{\max} \gt K$ となった場合、$S$ から最大値をpop、$t_{\max}$ から減算

(b) の場合、

$t_{\max}+=d$
$S$ に $d$ を追加
$S$ から最小値をpop
$t_{\max} \gt K$ となった場合、$S$ から最大値をpop、$t_{\max}$ から減算

(c) の判定は、$d$ の $S$ への追加前の状態で

$|S|=0$ かつ $t_{\max}+d \gt K$

これで、SortedListの参照・追加・削除を $O(\log{N})$ として、計算量は $O(N \log{N})$ となる。

SortedListは、工夫次第で優先度付きキューなど、より軽いデータ構造を使うことも可能なはず。

Python3

from sortedcontainers import SortedList


def solve(n, m, k, aaa):
    ans = []
    diff = SortedList()
    a0 = 0
    total = 0  # k を超えない中で最大の操作回数
    prev = 0  # 直前の要素を何回インクリメントしたか mod m
    for a in aaa:
        d = (m * 2 - (a + prev)) % m
        if d == 0:
            ans.append(0)
            continue
        if a + prev < m and len(diff) == 0 and a0 + d > k:
            ans.append(a)
            prev = 0
            continue
        total += d
        diff.add(d)
        if a > 0 and a + prev < m:
            a0 += diff.pop(0)
        if len(diff) > 0 and total > k:
            total -= diff.pop()
        ans.append(0)
        prev = (m - a) % m
    return ans


if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        n, m, k = map(int, input().split())
        aaa = list(map(int, input().split()))
        ans = solve(n, m, k, aaa)
        print(*ans)

D - Long Trail

問題文

正整数 $N$ が与えられます。
$G$ を頂点 $1,2,\ldots,N$ からなる $N$ 頂点 $\displaystyle \frac{N(N-1)}2$ 辺の完全無向グラフとします。
以下の条件を全て満たす $G$ 上の trail $(v_1,v_2,\ldots,v_k)$ を一つ求めてください。
- $1 \leq i \leq k-2$ を満たす整数 $i$ 全てについて、$|v_i - v_{i+2}| = 1$
- $\displaystyle \frac{(N-2)^2}2 \le k$
ただし、制約下でそのような trail が必ず存在することが証明できます。

trail とは、頂点の通過列 $(v_1,...,v_k)$ であって、同じ辺を（逆方向でも）2度以上経由しないものを指す。

制約

$1\le T\le 50$
$3\le N\le 1000$
全てのテストケースにおける $N$ の総和は $1000$ 以下
入力される値は全て整数

解法

B～Dが同じ配点だったが、パッと方針が見えなかったB,Cと比べ、 Dはとりあえず「どういう条件のものを構築すればいいか」は見えた。ただ、どのような $N$ でも長さの最低値を保証する方法、またそれを機械的に構築する方法を実装するのに、試行錯誤の時間がかかってしまい間に合わず。まぁ、「時間をかければ解けることが見えてる」ものに注力するのは悪くなかった、はず。

構築対象の言い換え

経由する頂点の列が、1個飛ばしでちょうど差分が $1$ になっていないといけない、という変わった条件。

グリッドで表現してみると、よい性質が見えてくる。

   1 2 3 4 5 6
1 ＼○            ○の位置は、(1,2)の辺を表す。
2 ×＼            仮に、この辺から開始することを想定してみる。
3 ××＼
4 ×××＼
5 ××××＼
6 ×××××＼

   1 2 3 4 5 6
1 ＼①②○        1→2の順に通ってしまうと、v3にv1との差が1となる頂点を置けない。
2 ×＼③④
3 ××＼○        2→1の順に通ったとすると、2→1→3→2→4→... は確定する。
4 ×××＼        これを右のグリッドで表現すると①②③④の順に辺を使うことになり、
5 ××××＼      さらに次に使えるのは○の2つであることがわかる。
6 ×××××＼

ここから「$N \times N$ グリッドの右上三角形内を、同じマスを使わずに、ジグザグに、なるべく長く移動する経路を見つければよい」と想像が付く。
実際、このようなグリッドにおけるパスは「同じ列にあるマス、または同じ行にあるマスへの移動を縦横交互に繰り返す」ことで表現され、今回は2つ前との頂点番号の差分制約があるため移動距離が $1$ に限られる、ということからこれが正しいと確認できる。

構築アルゴリズム

$N$ 偶数

$N$ が偶数の時は、比較的無駄なく敷き詰められる。

   1 2 3 4 5 6 7 8 910
1 ＼→↓→↓→↓→↓
2 ×＼→↑→↑→↑→↓
3 ××＼      ↓←↓←
4 ×××＼  ↓←↑←
5 ××××＼□□□□□
6 ×××××＼□□□□
7 ××××××＼□□□
:

$1,2$ 行を使って右に行き、$3,4$ 行を使って左に帰ると、$(5,6)$ からは $N-4$ の場合に帰着できる。

$N=4,6$ で、左上スタートの場合が解ければよい。
$N=4$ は対角線の右上すぐをジグザグに下ればよく、$N=6$ もそれを少し膨らませた形で構築できる。

長さが足りているか確認する。
$N \ge 8$ について、$N-4$ から増やした上4行では $N$ に関わらず固定値6マスだけ空きマスができる。 $N$ を4増やすことで新たに許容される空きマスの個数は

$\left ( \dfrac{n(n-1)}{2} - \dfrac{(n-2)^2}{2} \right ) - \left ( \dfrac{(n-4)(n-5)}{2} - \dfrac{(n-6)^2}{2} \right ) = 6$

となり、ちょうど $6$ だけ許容される空きマスが増えることが分かる。

$N$ 奇数

これが難しかった。どうしても隙間が大きくなり、$\displaystyle \frac{(N-2)^2}2 \le k$ が達成しにくい。

公式Editorialでは、「渦巻き」を作ることで場合分けの少ない方法を実現していた。
実装の手間と時間を考えると、この渦巻き型を思いついていたかったところだけど、右下や左上に4マスの空きができるのが視覚的に大きく写り、何となく長さが足りなそうで思いついたとしても切り捨ててしまっていそう。

    1 2 3 4 5 6 7 8 9
 1 ＼→↓      ↓←
 2 ×＼→↓  ↓←↑←    ぐるっと1周することで、
 3 ××＼→↓□□→↑    中央に N-6 の構造が残る。
 4 ×××＼→↓□↑←
 5 ××××＼→↓→↑    再帰した問題は
 6 ×××××＼→↑      i のシフト量と j のシフト量が異なる点に注意
 7 ××××××＼
 8 ×××××××＼
 9 ××××××××＼

上と右の壁沿いに行って帰ることで、$N-8$ の場合に帰着する方法でも構築できる。
右下で折り返すときに残る $5 \times 5$ の三角形は、帰着した問題を解いた後に辿ることになる。

    1 2 3 4 5 6 7 8 910111213
 1 ＼→↓→↓→↓→↓→↓
 2 ×＼→↑→↑→↑→↑→↓
 3 ××＼      ↓←↓←  →↓
 4 ×××＼  ↓←↑←↑←↓←
 5 ××××＼□□□□→↑→↓
 6 ×××××＼□□□↑←↓←
 7 ××××××＼□□  ↑←
 8 ×××××××＼□↓→↓
 9 ××××××××＼→↑→↓
10 ×××××××××＼  ↓←
11 ××××××××××＼→↓
12 ×××××××××××＼Ｇ
13 ××××××××××××＼

よって $N=3,5,7,9$ で、左上スタート、右下ゴールの場合が解ければよい、、、はずだった。

$N=3,5$ は対角線のすぐ右上をジグザグでよく、$N=7$ の場合もまぁ素直に構築できるのだが、 $N=9$ の場合が厄介で $k \ge 25$ を達成する方法が見つからない。

右下をゴールとしない場合であれば見つかったので例外処理し、 $N=17$ の場合を解くことで、全てを網羅できた。

こちらも長さを確認すると、外側で固定値 $12$ だけ空きマスができており、制約の式から計算しても $N$ を8増やすことで許容される空きマスの増加分は $12$ であることから、足りていることが分かる。

Python3

def solve_even(n, result, offset=0):
    if n == 2:
        result.append(1 + offset)
        return
    if n == 4:
        result.extend(a + offset for a in (1, 3, 2, 4, 3))
        return
    if n == 6:
        result.extend(a + offset for a in (1, 3, 2, 4, 1, 5, 2, 6, 3, 5, 4, 6, 5))
        return

    for i in range(3, n + 1):
        result.append((1 if i % 2 == 1 else 2) + offset)
        result.append(i + offset)
    for i in range(n - 1, 5, -1):
        result.append((3 if i % 2 == 1 else 4) + offset)
        result.append(i + offset)

    solve_even(n - 4, result, offset + 4)


def solve_odd(n, result, offset=0):
    if n == 3:
        result.extend(a + offset for a in (1, 3, 2))
        return
    if n == 5:
        result.extend(a + offset for a in (1, 3, 2, 4, 3, 5, 4))
        return
    if n == 7:
        result.extend(a + offset for a in (1, 3, 2, 4, 1, 5, 2, 6, 3, 7, 4, 6, 5, 7, 6))
        return
    if n == 17:
        for i in range(3, 17):
            result.append((1 if i % 2 == 1 else 2) + offset)
            result.append(i + offset)
        for i in range(3, 11):
            result.append(i + offset)
            result.append((17 if i % 2 == 1 else 16) + offset)
        result.extend(
            a + offset for a in (11, 15, 10, 14, 9, 15, 8, 14, 7, 13, 8, 12, 7, 11, 6, 12, 5, 13, 6, 14, 5, 15))
        for i in range(14, 5, -1):
            result.append((4 if i % 2 == 0 else 3) + offset)
            result.append((i + offset))
        result.extend(a + offset for a in (5, 7, 6, 8, 5, 9, 6, 10, 7, 9))
        for i in range(8, 14):
            result.append(i + offset)
            result.append(i + 2 + offset)
        result.extend(a + offset for a in (12, 16, 13, 17, 14, 16, 15, 17, 16))
        return

    for i in range(3, n):
        result.append((1 if i % 2 == 1 else 2) + offset)
        result.append(i + offset)
    for i in range(3, n - 6):
        result.append(i + offset)
        result.append((n if i % 2 == 1 else n - 1) + offset)
    result.append(n - 6 + offset)
    for i in range(n - 7, 4, -1):
        result.append((n - 2 if i % 2 == 0 else n - 3) + offset)
        result.append((i + offset))
    result.append(n - 2 + offset)
    for i in range(n - 3, 5, -1):
        result.append((4 if i % 2 == 0 else 3) + offset)
        result.append(i + offset)
    solve_odd(n - 8, result, offset=offset + 4)
    result.extend(n - a + offset for a in (3, 4, 2, 5, 1, 4, 0, 3, 1, 2, 0, 1))


def solve(n):
    if n % 2 == 0:
        ans = [2]
        solve_even(n, ans)
        return ans

    if n == 9:
        return [2, 1, 3, 2, 4, 1, 5, 2, 6, 1, 7, 2, 8, 3, 7, 4, 6, 5, 7, 6, 8, 5, 9, 4, 8]

    ans = [2]
    solve_odd(n, ans)
    return ans


def check():
    for n in range(3, 30):
        ans = solve(n)
        lo_limit = ((n - 2) ** 2 + 1) // 2

        if len(ans) < lo_limit:
            print(f'NG Length {n=} {lo_limit=} {len(ans)=}')

        used = set()
        k = len(ans)
        for i in range(k - 1):
            u = ans[i]
            v = ans[i + 1]
            if u > v:
                u, v = v, u
            if u == v:
                print(f'NG self-edge {n=} {i=} {ans=}')
            if (u, v) in used:
                print(f'NG duplicate-usage {n=} {u=} {v=} {ans=}')
            used.add((u, v))
        for i in range(k - 2):
            if abs(ans[i] - ans[i + 2]) != 1:
                print(f'NG diff is not 1 {n=} {i=} {ans[i]=} {ans[i+2]=} {ans=}')
    print('FINISH')


# check()

t = int(input())
for _ in range(t):
    n = int(input())
    ans = solve(n)
    print(len(ans))
    print(*ans)

参考

こういう「グリッド上のジグザグ移動の最長パス問題」って、いかにも既往研究がありそうと思ったんだけど、見つからなかった。なんて検索すれば出てきやすいのだろう。

maspy氏の解説を参考にすると、「行・列がともに偶数のマス」を特殊マスと呼ぶことにすると、このようなジグザグ移動では「特殊マスは、必ず4回ごとに1回踏む」ことになるという性質がある。（まぁ、mod2 で考えると、(偶,偶)→(偶,奇)→(奇,奇)→(奇,偶)→(偶,偶) という移動をすることになるので明らかではある）

解説 - AtCoder Regular Contest++ 220

よって、「全ての特殊マスを踏み、その前後で3マスの非特殊マスを踏む」経路を構築できれば、それが最長であるということができる。

この法則を思いついていれば、$N$ 奇数の時「特殊マスを全部通っていれば十分」という確信が持て、「どの順で特殊マスを通るか」という、よりシンプルな問題と捉えて考察時間を削減できていたかもしれない。

奇数の場合は最長が実現できているが、偶数の場合は、解法で示した構築方法では踏まない特殊マスができる。特殊マスを（偶,偶）から（奇,奇）や（偶,奇）に変更しても性質は変わらないが、どれであっても全ての特殊マスを踏むことはできない。この問題に関しては長さが足りているから良いのだが、最長経路の証明は偶数の方が難しいようだった。

目次

AtCoder Regular Contest++ 220 A,B,C,D問題メモ

A - Sum of Reciprocals of Squares

問題文

制約

解法

B - Incomplete Shuffle

問題文

制約

解法

サンプルの観察

サイクル毎の考察

C - Range Increment

問題文

制約

解法

DP定義

DPの高速化

D - Long Trail

問題文

制約

解法

構築対象の言い換え

構築アルゴリズム

$N$ 偶数

$N$ 奇数

参考