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

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$ とでもしておく）

DP[3] への遷移を考える

 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)

B - Hamming Distance is not 1

問題文

非負整数 $q,L,R\;(q \in \{ 0,1\}, \; L \leq R)$ が与えられます。
以下のすべての条件を満たす集合 $S$ について考えます。
- $S$ は $L$ 以上 $R$ 以下の互いに相異なる整数からなる。
- $S$ の任意の相異なる2要素 $a,b$ について、$a$ と $b$ は $2$ 進表記で $2$ 桁以上異なる。
- 上の $2$ 条件を満たすもののうち、要素数が最大となる。

$q=0$ のとき、このような集合 $S$ の要素数を求めてください。
$q=1$ のとき、このような集合 $S$ を一つ構築してください。

$1$ つの入力ファイルにつき、$T$ 個のテストケースを解いてください。

制約

$1 \leq T \leq 2 \times 10^5$
$0 \leq q \leq 1$
$0 \leq L \leq R \leq 10^{18}$
全てのテストケースにおける $q(R-L)$ の総和は $5\times 10^6$ 以下
入力される値は全て整数

考察

クエリの種類を示す $q$ が制約にも入ってるのを最初見落としてた。お前、制約に効いてくることあるのかよ。
つまり、$q=0$ の時、$O(R-L)$ かける時間はなく、$O(1)$ とか $O(\log{R})$ とかで求めなさいよ、ということ。

とりあえず気づきを得るため、愚直解（$L～R$ の整数の部分集合を $2^{R-L+1}$ 通り全探索）で要素数最大の $S$ を観察してみる。以下の傾向が見つかる。

pop count の偶奇が一致する要素が多く入るっぽい。
- 偶奇が混在する場合もあるが、「小さい方からいくつかは偶数個、それ以降は奇数個」など、1つの境界で分かれてるっぽい。
だいたいの $L,R$ で、 $|S|=\lceil \frac{R-L+1}{2} \rceil$ になるっぽい。
- だが $L,R$ によってはそうとは限らない場合もある。
  - ただ、その場合でも高々 $|S|=\lceil \frac{R-L+1}{2} \rceil + 1$ っぽい。
  - このような $L,R$ は、$L$ 奇数、$R$ 偶数の時に限られるっぽい。

L=6 R=31
要素数最大のS（要素数13、ceil((R-L+1)/2) と一致）
  7 8 11 13 14 16 19 21 22 25 26 28 31
  6 9 10 12 15 17 18 20 23 24 27 29 30
2進数表記
  111 1000 1011 1101 1110 10000 10011 10101 10110 11001 11010 11100 11111  ←pop count 奇数
  110 1001 1010 1100 1111 10001 10010 10100 10111 11000 11011 11101 11110  ←pop count 偶数

L=11 R=24
要素数最大のS（要素数8、ceil((R-L+1)/2) より1多い）
  11 13 14 17 18 20 23 24
2進数表記
  1011 1101 1110 10001 10010 10100 10111 11000    ←pop count 前半奇数、後半偶数

確かに、「pop count の偶奇が一致する整数」は、2進数表記で必ず2桁以上異なることが保証される。
pop count を基準とした分け方は有効そうである。

また、偶奇が混在するものについて、それが切り替わるタイミングは 01111→10000 など、最上位ビットが切り替わるタイミングであるように見られる。

最上位ビットが切り替わるまでは、pop count の偶奇が $L$ と同じ数
最上位ビットが切り替わってからは、pop count の偶奇が $R$ と同じ数

を採用していく？としても、愚直解の観察から、そうはなっていないケースもある。

L=5, R=14
L  0101 * ×1  o
   0110 * ×2  o
   0111             * : 上記方針で採用される値
   1000 *           ×: ハミング距離が1で矛盾するペア
   1001        o    o : 正しい答え（の一例）で採用される値
   1010        o
   1011 *
   1100        o
   1101 * ×1
R  1110 * ×2

これは、「$L \le$（$R$ の最上位ビットを $0$ にした値）」かつ「$L$ と $R$ の pop count の偶奇が異なる」場合、最上位ビットのみが異なる2数が同時に採用されてしまうことによる。

この場合は、+1 はできず、$|S|=\lceil \frac{R-L+1}{2} \rceil$ となる。

$q=1$ の場合、以下のいずれかを試し、

最上位ビットが切り替わる以前で採用する値を、pop count の偶奇が $L$ と異なる数にする
最上位ビットが切り替わってから採用する値を、pop count の偶奇が $R$ と異なる数にする

多く採用できる方にすると、通る。

解法

まず、コーナーケースとして、$L=R$ の場合は $S=\{L\}$ で明らかである。以降、$L \lt R$ とする。

解きやすいように、$L$ と $R$ の最上位桁が必ず異なるように正規化する。つまり、「2進数表記で桁を上から見ていって初めて異なる桁」より上の桁を、全て互いに $0$ にする。こうしても答えは変わらない。

L  11001011101  →  L  01011101
R  11010001111  →  R  10001111
   ~~~

以下の事実に気付くと、証明付きで解法に辿り着きやすくなる。

$2n$ と $2n+1$ は、必ず bit が1箇所だけ異なる。

つまり、この2数は同時に採用できない。答えがだいたい $R-L+1$ の半分になるのはこのためである。

先ほどの「pop count の偶奇が同じ2数は、必ずハミング距離が2以上」という事実とあわせ、各 $(2n, 2n+1)$ ペアから pop count の偶奇が同じ方を採用していけば、 $\lceil \frac{R-L+1}{2} \rceil$ 個は必ず採用できることが分かる。

L  0100┐  L偶数、R奇数の場合、全ての値がペアに属し、丁度半分が採用できる。
   0101┘
   0110┐  L偶数、R偶数┬の場合、1個だけペアに属さない値が余る。
   0111┘  L奇数、R奇数┘  その値と pop count の偶奇が同じのを採用すれば、
   1000┐                  ceil((R-L+1)/2) を採用できる。
   1001┘
R  1010    L奇数、R偶数の場合のみ、ペアに属さない値が2個余り、
           これをどちらも採用できる場合、ceil((R-L+1)/2)+1 となる。

$L$ 奇数、$R$ 偶数の時、2数を同時に採用できない条件は、先述の考察の通り、以下を同時に満たすとき。

$L \le$（$R$ の最上位ビットを $0$ にした値）
$L$ と $R$ の pop count の偶奇が異なる

これで、$q=0$ の時は $O(1)$ で判定できる。

$q=1$ の時も、$(L,R)$ の偶奇が

(偶,奇) では、どちらでもよいので popcount の偶奇が同じ数を採用
(偶,偶) では、popcount の偶奇が $R$ と同じ数を採用
(奇,奇) では、popcount の偶奇が $L$ と同じ数を採用
(奇,偶) では、
- $L,R$ を同時に採用できないなら、どちらでもよいので popcount の偶奇が同じ数を採用
- 採用できるなら、最上位ビットが切り替わるまでは $L$、以降は $R$ と同じ数を採用

とすればよい。

Python3

def solve(q, l, r):
    if l == r:
        return '1'

    diff_digit = (l ^ r).bit_length()
    same_bits = l >> diff_digit << diff_digit
    l ^= same_bits
    r ^= same_bits
    switch = 1 << (diff_digit - 1)

    l_pop_parity = l.bit_count() % 2
    r_pop_parity = r.bit_count() % 2
    cannot_use_l = l <= r ^ switch and l_pop_parity != r_pop_parity

    lo_best = (switch - l - 1) // 2 + 1
    hi_best = (r - switch) // 2 + 1
    lo_second = (switch - l) - lo_best
    hi_second = (r - switch + 1) - hi_best

    if q == 0:
        if cannot_use_l:
            ans = max(lo_best + hi_second, lo_second + hi_best)
        else:
            ans = lo_best + hi_best
        return str(ans)
    else:
        ans = []
        if cannot_use_l:
            if lo_best + hi_second > lo_second + hi_best:
                r_pop_parity ^= 1
            else:
                l_pop_parity ^= 1
        for i in range(l, switch):
            if i.bit_count() % 2 == l_pop_parity:
                ans.append('1')
            else:
                ans.append('0')
        for i in range(switch, r + 1):
            if i.bit_count() % 2 == r_pop_parity:
                ans.append('1')
            else:
                ans.append('0')
        return ''.join(ans)


t = int(input())
for _ in range(t):
    q, l, r = map(int, input().split())
    ans = solve(q, l, r)
    print(ans)

目次

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

A - Swapping Game

問題文

制約

解法

B - Hamming Distance is not 1

問題文

制約

考察

解法