AtCoder Regular Contest 213 (Div. 1) A問題メモ

AtCoder Regular Contest 213 (Div. 1)

A - Swapping Game

問題文

$(1,2, \dots ,L)$ の順列が $N$ 個あります。$i$ 個目の順列は $P_i$ であり、$P_i$ の $j$ 番目の要素は $P_{i,j}$ です。
はじめ、あなたは $A = (1,2, \dots ,L)$ を持っており、所持金は $0$ 円です。これから、$i = 1,2, \dots ,N$ の順に以下の操作を行います。
- $A$ の隣接 $2$ 項の swap を $0$ 回または $1$ 回行う。
- その後、$A = P_i$ となっていれば $C_i$ 円を獲得する。

最終的なあなたの所持金としてありえる金額の最大値を求めて下さい。

制約

$1 \leq N \leq 3 \times 10^4$
$1 \leq L \leq 9$
$0 \leq C_i \leq 10^4$
$P_i$ は $(1,2, \dots, L)$ の順列
入力はすべて整数

解法

グラフとか考えて遠回りしてしまった。

以下のようなDPをしたい。

$\mathrm{DP}[i]:=i$ 回目の操作で $P_i$ に揃えたとして、それまでに獲得できる最大金額
- 便宜的に、初期状態を $P_0=(1,2,...,L)$、$\mathrm{DP}[0]=0$ とする。

遷移を考えると、$0 \le j \lt i$ なる $j$ ごとに、$i$ に遷移できるかが異なる。
「$P_j→P_i$ にするために必要な最小 swap 回数」が $i-j$ を上回っていたら、$j$ からは遷移できない。

遷移可能な $j$ のみでの $\mathrm{DP}[j]$ の最大値を $m_i$ として、$\mathrm{DP}[i]=m_i+C_i$ となる。
または、どの $j$ からも遷移できない場合もある。（$-\infty$ とでもしておく）

 i   Ci  P
 0       1 2 3 ───┐ P0→P3 の最小swapは2回。間に合う。
 1  200  2 1 3 ──┐│ P1→P3 の最小swapは1回。間に合う。
 2  400  3 1 2 ─┐││ P2→P3 の最小swapは2回。間に合わない。
[3] 300  2 3 1 ←┴┴┘
 4  100  3 2 1          DP[3] = max(DP[0],DP[1]) + C3 となる。

だが、この遷移で全ての $(j,i)$ を総当たりしてたらそれだけで $O(N^2)$ かかりTLEとなる。
かといって、$i$ と $i+1$ では順列が全然異なるため、1個前の計算結果を有効利用することもできない。

ここで、順列長 $L$ が小さいことが活きてくる。

「$P_j→P_i$ にするために必要な最小 swap 回数」は、以下のように求められる。

$P_j$ を $(1,2,...,L)$ にマッピングする（$P_{j,k}→k$ への置換マップを作る）
その置換マップを使って $P_i$ を置換する。
置換した $P_i$ の転倒数を求める。

よって、swap 回数の上限は、長さ $L$ の順列の転倒数の最大値 $\dfrac{L(L-1)}{2}$ となることがわかる。
$L=9$ の場合でも $36$ である。

つまり、$i-j \ge 36$ の場合は必ず遷移可能。
愚直に swap 回数を求めるのは、1つの $i$ につき最大 $35$ 個まででよいことがわかる。

       P
 ：
i-37   1 2 3 4 5 6 7 8 9
i-36   1 2 3 4 5 6 7 8 9____↑必ず遷移可能____
i-35   3 1 5 7 9 6 2 8 4    ↓愚直に調べる
 ：
i-1    8 9 7 6 5 4 3 2 1 
[i]    9 8 7 6 5 4 3 2 1

swapの必要回数（転倒数）を求めるのは、計算量上はFenwickTree等を使って $O(L \log{L})$ だが、 $L$ が小さい場合は単に $O(L^2)$ かけた方がおそらく速い。（FenwickTreeは配列生成コストなどあるので）

以上で、$N \times \dfrac{L(L-1)}{2} \times L^2 \simeq O(NL^4)$ で求められ、間に合う。

Python3

def get_pos(n, ppp):
    pos = [0] * n
    for i in range(n):
        pos[ppp[i]] = i
    return pos


def get_inversion(n, pos, ppp2):
    res = 0
    for i in range(1, n):
        for j in range(i):
            if pos[ppp2[i]] < pos[ppp2[j]]:
                res += 1
    return res


def solve(n, l, ppps):
    NINF = -1 << 60
    ccc = [0]
    ppps2 = [list(range(l))]
    for c, *ppp in ppps:
        ccc.append(c)
        ppps2.append([p - 1 for p in ppp])
    dp = [NINF] * (n + 1)
    dp[0] = 0
    before36 = NINF
    for i in range(1, n + 1):
        c = ccc[i]
        ppp = ppps2[i]
        pos = get_pos(l, ppp)
        best = before36
        for j in range(max(0, i - 36), i):
            if dp[j] == NINF:
                continue
            inv = get_inversion(l, pos, ppps2[j])
            if inv <= i - j:
                best = max(best, dp[j])
        if best > NINF:
            dp[i] = best + c
        if i >= 36:
            before36 = max(before36, dp[i - 36])
    ans = max(dp)
    return ans


n, l = list(map(int, input().split()))
ppps = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, l, ppps)
print(ans)

目次

AtCoder Regular Contest 213 (Div. 1) A問題メモ

A - Swapping Game

問題文

制約

解法