トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328) G問題メモ

トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328)

G - Cut and Reorder

問題

長さ $N$ の数列を、以下の操作を好きに繰り返して $A_1,...,A_N$ から $B_1,...,B_N$ にする
操作1: 数列を好きな位置で切り刻んで好きな順で並べなおす。1箇所切り刻むのにコスト $C$
操作2: 好きな $i,k$ を選んで、$A_i$ に $k$ を加算する。コスト $|k|$
最小コストを求めよ
$1 \le N \le 22$
$1 \le A_i,B_i,C \le 10^{15}$
実行制限時間 2.8秒
メモリ制限 512MB

解法

オーダーに $2^N$ が含まれるbitDP解法なら、$N=22$ よりもうちょっと少なく設定されるだろうから別の解法かな？と変なメタ読みしたが、普通にbitDPだった。いつもと違うメモリ制限も、想定解法が $O(N2^N)$ に対して $O(N^2 2^N)$ を落とすためらしい。

$DP[S]$ を以下で定義する。

$S=\{S_1,S_2,...,S_n\}$ として、$A_1,...,A_n$ を、$B_{S1},B_{S2},...,B_{Sn}$ にするのにかかる最小コスト

配るDPで、$DP[S]$ からの遷移を考える。

$A_1,...,A_n$ は決定しているので、次の $A_{n+1}$ から連続する、操作1の結果のブロック1単位の切り出し方・移動先を全て試す。

S={2,3,6,7,8,9}

     1  2  3  4  5  6  7  8  9
A    o  o  o  o  o  o  -  -  -       o:決定済み  -:未決定

B    -  o  o  -  -  o  o  o  o

長さ1のブロック $A_7$ は、$B_1,B_4,B_5$ に移せる
長さ2のブロック $[A_7,A_8]$ は、$[B_4,B_5]$ に移せる
長さ3のブロック $[A_7,A_9]$ は、この $S$ ではどこにも移せない

1ブロックの切り出しにつきコスト $C$ かかり、移した先では操作2によって各要素の差の絶対値だけのコストがかかる。

$pre[k,l_a,l_b] = $ 長さ $k$ のブロックで、それぞれ $A_{la}$ と $B_{lb}$ が左端であるもの同士を、操作2だけで合わせるコスト

は $O(N^3)$ で事前計算でき、これを使うと遷移は（切り出し方・移動先）1箇所につき $O(1)$ となる。

$S$ をbitで表現して小さい方から計算していき、$DP[\{1,...,N\}]$ が答えとなる。

計算量の考え方

1つの $S$ に対する（切り出し方・移動先）の総数を考えると、一見、ブロックの長さ $O(N)$、位置合わせ $O(N)$ の $O(N^2)$ に見える。
これだと、$S$ は $2^N$ 通りあるので $O(N^2 2^N)$ となり少し厳しい。

だが実際は、$S$ が大きくなる毎にブロック長の上限は狭まっていくし、長いブロックは位置合わせの回数も少なく済む。

公式Editorialによると、ブロックの長さに着目することで、長さ $k$ のブロックが試されるような $S$ は $2^{N-k}$、またそこからの位置合わせも $N-k+1$ 箇所だけ試せばよいので、

$\displaystyle \sum_{k=1}^{N}2^{N-k}(N-k+1)$ → $O(N 2^N)$

となるらしい。

公式のサンプルコードは $S$ の方から遷移先の $l,r$ を探索しているが、以下の自分のコードは、$|S|$ を基準にまず遷移の長さ $k$ を決めて、それを1つずつずらしている。
そのため少し遷移に無駄があって、どちらかというと $O(N^2 2^N)$ を定数倍削減している感じだが、通った。
遷移回数も、$3 \times 10^8$ ほどある。

Python3

import os
import sys

import numpy as np


def solve(inp):
    n, c = inp[:2]
    aaa = inp[2:2 + n]
    bbb = inp[2 + n:]

    pre = np.zeros((n + 1, n, n), np.int64)  # 幅 i、Aj, Bk から始まる区間を（それ以上分割せず）合わせるコスト
    for w in range(1, n + 1):
        for la in range(n - w + 1):
            for lb in range(n - w + 1):
                pre[w, la, lb] = pre[w - 1, la, lb] + abs(aaa[la + w - 1] - bbb[lb + w - 1])

    pop_counts = np.zeros(1 << n, np.int64)
    bit_lengths = np.zeros(1 << n, np.int64)
    for i in range(1, 1 << n):
        pop_counts[i] = pop_counts[i >> 1] + (i & 1)
        bit_lengths[i] = bit_lengths[i >> 1] + 1

    INF = 1 << 60
    MASK = (1 << n) - 1
    dp = np.full(1 << n, INF, np.int64)
    dp[0] = 0
    for used in range(1 << n):
        la = pop_counts[used]
        for w in range(1, n - la + 1):
            next_use = (1 << w) - 1
            lb = 0
            while next_use <= MASK:
                alt = used & next_use
                if alt == 0:
                    dp[used | next_use] = min(dp[used | next_use], dp[used] + pre[w, la, lb] + c)
                    next_use <<= 1
                    lb += 1
                else:
                    shift = bit_lengths[alt] - lb
                    next_use <<= shift
                    lb += shift

    return dp[MASK] - c


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

目次

トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328) G問題メモ

G - Cut and Reorder

問題

解法

計算量の考え方