AtCoder Regular Contest 204 (Div. 1) A,B,C,D 問題メモ

AtCoder Regular Contest 204 (Div. 1)

A - Use Udon Coupon

問題文

正整数 $N, L, R$ と長さ $N$ の正整数列 $A = (A_{1}, A_{2}, \dots, A_{N}), B = (B_{1}, B_{2}, \dots, B_{N})$ が与えられます。
整数 $C$ を $0$ で初期化します。その後、以下の行動 $1, 2$ のうちいずれかを選んで行う、ということを $2N$ 回繰り返します。
- 行動 $1$ :
  - $i$ 回目の行動 $1$ では、$C$ を $\max(0, C - A_{i})$ に置き換える。
  - 行動 $1$ は、計 $N$ 回おこなう。
- 行動 $2$ :
  - $i$ 回目の行動 $2$ では、$C$ に $B_i$ を加算する。
  - $i$ 回目の行動 $2$ は、それまでの行動 $1$ の回数が $i$ 回以上の時のみおこなえる。
  - 行動 $2$ は、計 $N$ 回おこなう。

$2N$ 回の操作の方法であって、最終的な $C$ が $L$ 以上 $R$ 以下であるようなものの場合の数を $998244353$ で割ったあまりを求めてください。

制約

$1\leq N\leq 5000$
$1\leq L \leq R \leq \sum B$
$1\leq A_{i}\leq 5000$
$1\leq B_{i}\leq 5000$
入力は全て整数

解法

仮に行動 $1$ で、最小値を0で切らずにそのまま $C←C-A_i$ としていた場合の $C$ を $C'$ と表す。
$2N$ 回後の最終的な $C'$ の値は $T = \mathrm{sum}(B)-\mathrm{sum}(A)$ で一定である。

実際の $C$ は、ここから「途中で経由した $C'$ の最小値」だけ底上げされる、と考えられる。

                       T___
C' 0                  /   ^
    ＼         /\   ／    |実際のC
      ＼/＼   /  ＼/      |
           \／____________v

つまり、問題の条件は「途中で経由する $C'$ の最小値が $T-R$ 以上 $T-L$ 以下」となるような操作列の数、と言い換えられる。

操作順を経路数になぞらえる。
操作の制約が「行動2の回数が行動1の回数を超えてはいけない」ということで、通れるマスに制約がある以下のような図となる。

Ｓ×××××    ↓: 行動1
□□××××    →: 行動2
□□□×××
□□□□××
□□□□□×
□□□□□Ｇ

このマス目の1つ1つにつき、そこへ到達時点の $C'$ の値「$K_{i,j} =$（$j$ までの $B$ の和）-（$i$までの $A$ の和）」は、操作順に依らず固定である。

つまり、条件に当てはまる操作列は、「以下のような図で、“１”のマスを1回以上通り、“２”のマスは通らないで、ＳからＧまで行く経路数」と言い換えられる。

Ｓ×××××    ↓: 行動1
００××××    →: 行動2
１００×××
１０００××    ０:                        T-L <  K_ij
２１１００×    １:         T-R <= K_ij <= T-L
２２１００Ｇ    ２: K_ij <  T-R

“１”を1回以上通ってない/通った、の2通りを持つ経路数DPで $O(N^2)$ で求められる。

Python3

from itertools import accumulate


def solve(n, l, r, aaa, bbb):
    acc_a = [0] + list(accumulate(aaa))
    acc_b = [0] + list(accumulate(bbb))
    total = acc_b[-1] - acc_a[-1]
    min_l = total - r
    min_r = total - l
    is_ok = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        for j in range(i + 1):
            if min_r < acc_b[j] - acc_a[i]:
                is_ok[i][j] = 0
            elif min_l <= acc_b[j] - acc_a[i] <= min_r:
                is_ok[i][j] = 1
            else:
                is_ok[i][j] = 2
    # print(is_ok)
    dp0 = [[0] * (n + 1) for _ in range(n + 1)]
    dp1 = [[0] * (n + 1) for _ in range(n + 1)]
    if min_r < 0:
        dp0[0][0] = 1
    elif min_l <= 0 <= min_r:
        dp1[0][0] = 1
    else:
        return 0

    MOD = 998244353
    for i in range(1, n + 1):
        for j in range(i + 1):
            if is_ok[i][j] == 0:
                if i > 0:
                    dp0[i][j] += dp0[i - 1][j]
                    dp1[i][j] += dp1[i - 1][j]
                if j > 0:
                    dp0[i][j] += dp0[i][j - 1]
                    dp1[i][j] += dp1[i][j - 1]
                dp0[i][j] %= MOD
                dp1[i][j] %= MOD
            elif is_ok[i][j] == 1:
                if i > 0:
                    dp1[i][j] += dp0[i - 1][j]
                    dp1[i][j] += dp1[i - 1][j]
                if j > 0:
                    dp1[i][j] += dp0[i][j - 1]
                    dp1[i][j] += dp1[i][j - 1]
                dp1[i][j] %= MOD
    return dp1[n][n]


n, l, r = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
ans = solve(n, l, r, aaa, bbb)
print(ans)

B - Sort Permutation

問題文

正整数 $N, K$ と、$(1, 2, \dots, NK)$ の順列 $P = (P_{1}, P_{2}, \dots, P_{NK})$ が与えられます。
Alice は以下の操作を繰り返し、$P$ を昇順ソートします。
- $1$ 以上 $NK$ 以下の整数 $i, j(i\neq j)$ を選び、$P_{i}$ と $P_{j}$ を入れ替える。
- このとき、$|i - j|$ が $N$ の倍数なら、Alice は $1$ ポイントもらえる。

Alice は最小の操作回数で $P$ を昇順ソートし、その上でもらえるポイントの和を最大化する行動をします。
Alice が得るポイントの和を出力してください。

制約

$1\leq N\leq 500$
$1\leq K\leq 10$
$(P_{1}, P_{2}, \dots , P_{NK})$ は $(1, 2, \dots, NK)$ の順列
入力は全て整数

解法

まず、順列を任意位置swapによりソートするのにかかる最小操作回数は、サイクルを考えることで求められる。

$i→P_i$ に辺を張ったグラフ（置換グラフ）を考えると、連結成分はいくつかのサイクルに分かれる。
サイクル毎に独立に、サイズ $L$ のサイクルは $L-1$ 回で構成要素を正しい位置に並び替えられる。

この時、「同じサイクル内にある2要素をswapする」ことさえ守れば、操作順は特に関係ない。

「位置 $i,j$ にある $P_i,P_j$ をswapする」という操作は、サイクル上では「頂点 $i,j$ から伸びる辺の先を交換する（$i→P_j$ と $j→P_i$ にする）」と見なせる。以降、「$(i,j)$ のswap」というと、この操作を指すとする。

$(i,j)$ が最初から別のサイクルにあったら、$(i,j)$ をswapする操作はできない。

では、同じサイクルにあったら必ず操作できるのか？というと、否。
もともとが同じサイクルにある $(i,j)$ でも、同サイクル内の他のペアを先に操作したことでサイクルが再構成され、 $(i,j)$ に操作をするときには別のサイクルに分かれてしまっている、という場合は、やはり操作できない。
（かといって $(i,j)$ を先に操作すると、今度はまた別のペアができなくなる）

サイクル毎に独立に考える。サイクル順に頂点番号を並べて、$\mod{N}$ に置き換える。

0→9→8→21→15→22→19→16→17→11
^--------------------------------'
↓mod N (N=4の場合)

0→1→0→1→3→2→3→0→1→3
^--------------------------'

「$\mod{N}$ が同じ値同士をswap」したら1ポイント得られる。
ある2つを swap すると、サイクルは以下のように再構成される。

0→1→0→[1]→3→2→3→0→[1]→3
^------------------------------'    [1]同士をswap
↓
           ,-------------------v
0→1→0→[1]  3→2→3→0→[1]  3
^             ^------------'   |
`------------------------------'

つまり、「ペアに挟まれた頂点」が全て、右側の頂点と合わせて別のサイクルになる。

この操作で別のサイクルになったペアは操作できなくなる。
逆に同じサイクルになったペアはまだ操作できるので、結局、操作可能な条件は「swapするペアが交差してはいけない」というように言い換えられる。

      x  y  z     z  x  y        xとyをどちらも操作することはできない。
0→1→0→1→3→2→3→0→1→3     xとzなど、包含の関係はOK

また、以下のように同じ数字が3回以上出てくる場合、同じ箇所を重複して使うのはOKである。今回は $(0,2),(2,7)$ のように使用する中で互いに近いもの同士をペアにする形に限定して考える（後のDPで考えやすくなるため）。

[0]→1→[0]→1→3→2→3→[0]→1→3    真ん中の[0]を2回使って2ペア取ってよい
 `------' `---------------'

以上の条件で、各サイクルで「交差しないで取れる最大ペア数」を求めたい。

サイクルはループしているが、適当な頂点で切り開いて考えてよい。
交差するペアはどこで切り開いても交差しているし、交わらない or 包含関係のペアはどこで切り開いても交差しないので。

適当な頂点で切り開いた、$\mod{N}$ されたサイクル順の列を、$B=(B_1,...,B_L)$ とする。$L$ をサイクル長とする。

区間DPをおこなう。

$\mathrm{DP}[l,r]:=B[l,r)$ の範囲で、交差しないで取れる最大ペア数

だが、素直な区間DPでは、状態数 $O(L^2)$、遷移 $O(L)$ の、全体 $O(L^3)$ の計算量となる。 $L = NK = 5000$ になり得るので、普通にやるとTLEとなってしまう。

ここで、$K \le 10$ という制約が効いてくる。
「$P$ において、$\mod{N}$ が同じ数字は高々 $K$ 回しか登場しない」ので、つまり、$B_l$ と同じ値になる $B_j$（$j \neq l$）は $9$ 個以下しか無い。

$\mathrm{DP}[l,r]$ を求める場合を考える。

① $l$ を含むペアを使わない
② $l$ を含むペアを使う
- ②a) $l$ の相方は、$r-1$
- ②b) $l$ の相方は、$l \lt j \lt r-1$ の範囲にある $j$

①の場合、$\mathrm{DP}[l+1,r]$ と等しくなる。

②a) の場合は、$B_l=B_{r-1}$ であることが条件となる。$\mathrm{DP}[l+1,r-1]+1$ となる。

②b) の場合、$l$ とのペア候補は高々 $K-1$ 個である。
$l$ の相方を $j$ とする場合、$j$ 自体は両方の区間に被って使えるため、$\mathrm{DP}[l,j+1]+\mathrm{DP}[j,r]$ となる。

... l           j             r-1 ...
    0     0     0   0     0    ?
   [             ]
               [                ]

必ずしも $l$ のすぐ右の同じ値を相方とした方がよい、とは限らない点に注意。

... l       j       k
    0 1 2 3 0 3 2 1 0 ...    lは、j と相方としようとすると3つのペアが犠牲になる。
      | | `---' | |          j でポイントを得ることは諦めて、k とペアにした方がよい。
      | `-------' |
      `-----------'

これらを試した中での最大値が $\mathrm{DP}[l,r]$ となる。これは全体 $O((NK)^2K)$ で求められる。

なぜか途中まで、勘違いして $|i-j|$ が $N$ の倍数でなく $K$ の倍数になるものを求めようとしてた。
注意してても自然と思い込んじゃってるんだよな。おそろしや。

Python3

def get_cycle(n, ppp):
    used = [False] * n
    for i in range(n):
        if used[i]:
            continue
        s = i
        i = ppp[i]
        tmp = [s]
        used[s] = True
        while i != s:
            tmp.append(i)
            used[i] = True
            i = ppp[i]
        yield tmp


def solve(n, k, ppp):
    ppp = [p - 1 for p in ppp]
    ans = 0
    for grp in get_cycle(n * k, ppp):
        m = len(grp)
        grp = [p % n for p in grp]
        last_i = {}
        next_same = [n * k] * m
        for i in range(m):
            p = grp[i]
            if p in last_i:
                next_same[last_i[p]] = i
            last_i[p] = i
        dp = [[0] * (m + 1) for _ in range(m)]
        for w in range(2, m + 1):
            for l in range(m - w + 1):
                r = l + w
                tmp = dp[l + 1][r]
                if grp[l] == grp[r - 1]:
                    tmp = max(tmp, dp[l + 1][r - 1] + 1)
                mid = next_same[l]
                while mid < r - 1:
                    tmp = max(tmp, dp[l][mid + 1] + dp[mid][r])
                    mid = next_same[mid]
                dp[l][r] = tmp
        ans += dp[0][m]
    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
ans = solve(n, k, ppp)
print(ans)

C - Maximize Sum of Mex

問題文

正整数 $N$ と $(1, 2, \dots , N)$ の順列 $P = (P_{1}, P_{2}, \dots, P_{N})$が与えられます。
$Q$ 個のクエリを処理してください。各クエリでは非負整数 $A_{0}, A_{1}, A_{2}$ が与えられるので以下の問題の答えを出力してください。なお、$A_{0} + A_{1} + A_{2} = N$ であることが保証されます。
- 長さ $N$ の数列 $B$ であって、以下の条件をすべて満たす数列を good な数列とします。
  - $B_{i} = 0$ が成り立つ $1$ 以上 $N$ 以下の整数 $i$ はちょうど $A_{0}$ 個
  - $B_{i} = 1$ が成り立つ $1$ 以上 $N$ 以下の整数 $i$ はちょうど $A_{1}$ 個
  - $B_{i} = 2$ が成り立つ $1$ 以上 $N$ 以下の整数 $i$ はちょうど $A_{2}$ 個
- 長さ $N$ の数列 $B$ に対して、スコアを以下のように定義します。
  - $\displaystyle\sum_{i = 1}^{N}\mathrm{MEX}(B_{i}, B_{P_{i}})$
  - ただし、$\mathrm{MEX}(x, y)$ は $x$ でも $y$ でもない最小の非負整数であると定義します。
- good な数列全てに対するスコアの最大値を求めてください。

制約

$1\leq N\leq 3\times 10^{5}$
$(P_{1}, P_{2}, \dots , P_{N})$ は $(1, 2, \dots , N)$ の順列
$1\leq Q\leq 3\times 10^{5}$
$0\leq A_{i}$
それぞれのクエリに対して $A_{0} + A_{1} + A_{2} = N$
入力は全て整数

解法

Bに続きサイクルの問題。

極論、場合分けを泥臭くおこなっていけば難しいアルゴリズムは不要なのだが、それなりに上手く場合分けを減らす方法を見つけないと実装・バグ取り地獄に陥る（陥った）。

$P$ を置換グラフに変換し、辺で結ばれた2頂点の $B_i$ の関係性により、得点が得られる。
$\{0,1\}$ の組で $2$ 点得られ、$\{0,0\},\{0,2\}$ の組で $1$ 点、他は $0$ 点となる。

..--⓪--①--⓪--⓪--②--①--..
      2   2   1   1   0

この得点は、0に由来するものと1に由来するものに分けて考えられる。

$0$ は、基本的に1つにつき両側で $2$ 点得られるが、$0$ 同士を隣接させると効果がダブってしまい損する。
$1$ は、両側が $0$ の場所に置いたら $2$ 点、片側が $0$ の場所に置いたら $1$ 点得られる。
- ※ $0$ で既に得ている得点から追加で得られる点

もし以下のことが言えれば、「まず $0$ を配置し、次に $1$ を配置する」という順での考察ができ、場合分けにおいて「$0$ と $1$ の残数を同時に考慮する」という煩雑さがなくなって嬉しい。

仮説: 最大得点を達成する $0$ の配置は $A_1$ の値によらず、$A_0$ の値によってのみ決まる

これは正しく、貪欲法に近い $0$ の配置手順が存在する。

ひとまず「$0$ → $1$ の順に配置して得点を最大化する」という手順を踏もうとすると、以下のような手順が考えられる。

$0$ を置いていく。
- なるべく隣接させないように置いていく。
  - 特に、$1$ での得点を最大化するため、なるべく1つおきになるように配置する。
- 最初から $2A_0$ 点をもらっておき、隣接させて置いたらそのような箇所1箇所につき、$1$ 点失う。
  - 単独頂点に置くのは1隣接と見なす。
- 配置後、以下のように変数を定義する。
  - $p_2$: 両側に $0$ がある、$0$ を置いていない箇所数
  - $p_1$: 片側のみ $0$ がある、$0$ を置いていない箇所数
  - $y$: $0$ の隣接箇所数
$1$ を置いていく。
- $p_2→p_1$ の優先順位で置いていく。
- $p_2,p_1$ を埋めて余った分は得点に寄与することはない。

得点を増やすためには、

$0$ の配置において、$y$ は-1で寄与するためなるべく減らしたい
$1$ の配置において、$p_2$ は多い方がよい。
- $2A_0=2p_2+p_1+2y$ という関係式が成り立つ
- $y$ が同じ中では $2p_2+p_1$ は一定値
  - $p_2$ が1増えて $p_1$ が2減ると、$1$ の配置時に得られる得点は、最大1上がる
- $y$ が1増えると、$p_2$ が少なくとも $1$ 増えていないと、絶対に得にならない

ある2つの $0$ の配置方法 $f,g$ にて、以下がともに言えれば、$A_1$ の値に依らず $f$ の最終得点は常に $g$ 以上になるといえる。

$y_f \le y_g$
$p_{2,f} - y_f \ge p_{2,g} - y_g$

ここで、以下のような優先順位で $0$ を埋めていくことを考える。
やや天下り的ではあるが、効率よく $y$ を減らし $p_2$ を増やす配置を考えると割と自然に辿り着けるはず。

(A) 偶数長サイクルをちょうど敷き詰める
(B) それ以外でサイクルに隣接しないように置く
(C) (B)で余った一方に置く
(D) 単独頂点に置く
(E) その他

まず、(A) 偶数長サイクル（長さ $2m$）にちょうど $m$ 個の $0$ を1個置きに配置するのが強い。
$y$ を増やさず、$p_2$ を $m$ 個増やせ、最大効率である。

⓪--○--⓪  ○--○--○
｜      ｜  ｜    ／
○--⓪--○  ○--○      ○  ○

次は、(B) 偶数長（長さ $2m$）または奇数長サイクル（$2m-1$）に、$m-1$ 個以下の $0$ を配置できる。
$x$ 個置いたとすると、$y$ を増やさず、$p_2$ を $x-1$ 個、$p_1$ を $2$ 個増やせる。$p_2$ を作る効率が(A)よりわずかに劣る。

⓪--○--⓪  ○--⓪--○
｜      ｜  ｜    ／
○--⓪--○  ⓪--○      ○  ○

これ以上の $0$ を配置しようとすると、どうしても隣接が発生する。

(C) 長さ3以上の奇数長サイクルで (B) を最大までおこなうと、未配置が2個連続している箇所が残る。
この一方を $0$ にすることで、$y$ を1増やし、$p_2$ を1個増やし、$p_1$ は2減る。

⓪--○--⓪  ○--⓪--⓪ ←ここ
｜      ｜  ｜    ／
○--⓪--○  ⓪--○      ○  ○

(D) 単独頂点は、$y$ を1増やすのみ。

⓪--○--⓪  ○--⓪--⓪
｜      ｜  ｜    ／
○--⓪--○  ⓪--○      ⓪  ⓪

(E) ここまで来ると、もう「1つおき」の隙間を潰すしかない。1つにつき $y$ が2増え、$p_2$ が1減る。

以上の優先順位において、 $y$ は (A)(B)→(C)(D)→(E) の順に $0$ 1個あたりの発生数が多くなり、最小化されている。

また、どの優先順位においても、$0$ 1個あたりの $p_2-y$ の効率は上位 ≧ 下位であり、逆転することはない。

言い換えると、もし(B)や(C)に配置できるスペースが余っているのに(D)や(E)に配置されている⓪が存在するなら、移し替えて損しない。
（(A)への配置はまとまった個数が必要となるが、同じように、必要数の(B)以下の⓪があったら移し替えて損しない）

よって、上記の優先順位で配置することで、最大得点を達成する $0$ の配置の1つが得られる。

$1$ の配置で得られる得点は $p_2,p_1$ の個数のみから求められるため、ほぼ「$0$ の配置をどうするか」だけ考えればよいことがわかった。

配置

優先順位に従って $A_0$ 個の $0$ を配置するアルゴリズムを考える。

まず、(A) だけで完結できるなら、その方がよい。
つまり、偶数長サイクルの長さの多重集合 $(2m_1,2m_2,...,)$ の部分和で $2A_0$ を作れたら嬉しい。

部分和はナップサック問題のように考えられ、以下のDPで前計算できる。

$\mathrm{DP}[i,j]:=i$ 番目のサイクルまで考慮して、サイクル長の和が $j$ である組合せを作れるか（bool）

これは愚直にやると $O(N^2)$ かかってしまうが、同じ長さのサイクルは遷移をまとめることである程度高速化でき、「スライド最小値」や「2冪にまとめる」などの方法で、$O(N \sqrt{N})$ または $O(N \sqrt{N} \log{N})$ で求められる。（全アイテムのサイクル長の総和は $N$ 以下なので、異なる長さのサイクルは $O(\sqrt{N})$ 種類に限られる）

ちょうど $2A_0$ になる部分和を作れなかった場合でも、とりあえず (A) の方法で配置できる最大数までは (A) で配置する。
その後、(B)の配置を考えるにあたり、以下に分岐する。

偶数長サイクルが残っている場合
偶数長サイクルが残っていない場合

偶数長サイクルが残っている場合、残っているサイクルは必ず未配置の $0$ を全て配置できるだけの長さを持つ（サイクル長＞未配置の0の2倍）。でないと「(A) の方法で配置できる最大数までは (A) で配置」という前提に矛盾する。
よってその1サイクルに(B)の方法で配置して必ず $0$ を使い切り、(C)以降に配置することはない。

残っていない場合は奇数長サイクルに配置していく。この場合は必ずしも1サイクルで完結するとは限らないが、なるべく長さの大きいサイクルから使用するのが良い。
同じ個数の $0$ を「でかい少数のサイクルに配置」「細かい多数のサイクルに配置」では、前者の方が $p_2$ を大きくできる。

サイクル長を大きい順にソートし、各サイクルに隣接無しで置ける $0$ の最大数の累積和をとっておくことで、各クエリにおいて、未配置の $0$ を (B) の方法で配置するのに必要なサイクル数が特定できる。そこから作れる $p_2$ と $p_1$ の個数が計算できる。

それでも $0$ が残る場合は (C)(D)(E) に配置していくが、これらは複雑ではないため割愛。

これで得られた $(p_2, p_1, y)$ から、総スコアを計算できる。
(A)での偶数長サイクルにちょうど配置できる0の個数と、(B)での奇数長サイクルの累積和の前計算さえあれば、各クエリは条件分岐のみの $O(1)$ で答えられる。

Python3

from bisect import bisect
from collections import defaultdict
from itertools import accumulate


def get_cycle(n, ppp):
    used = [False] * n
    for i in range(n):
        if used[i]:
            continue
        s = i
        i = ppp[i]
        tmp = [s]
        used[s] = True
        while i != s:
            tmp.append(i)
            used[i] = True
            i = ppp[i]
        yield tmp


def solve(n, ppp, q, queries):
    ppp = [p - 1 for p in ppp]
    size_count = defaultdict(int)
    for cycle in get_cycle(n, ppp):
        size_count[len(cycle)] += 1

    odd_cycles = []
    even_partial_sums = {0}
    iso_total_v = 0
    odd_total_c = 0
    odd_total_v = 0
    even_total_c = 0
    even_total_v = 0
    for s, c in size_count.items():
        if s % 2 == 0:
            even_total_c += c
            even_total_v += s * c
            b = (c + 1).bit_length() - 1
            for i in range(b):
                weight = (1 << i) * (s // 2)
                even_partial_sums.update({c + weight for c in even_partial_sums})
            r = c - (1 << b) + 1
            if r > 0:
                weight = r * (s // 2)
                even_partial_sums.update({c + weight for c in even_partial_sums})
        else:
            if s == 1:
                iso_total_v += c
            else:
                odd_total_c += c
                odd_total_v += s * c
                odd_cycles.extend([s // 2] * c)

    even_cycles = [0] * (n + 1)
    for c in even_partial_sums:
        even_cycles[c] = c
    for i in range(n):
        even_cycles[i + 1] = max(even_cycles[i + 1], even_cycles[i])

    odd_cycles.sort(reverse=True)
    odd_cycle_no_adjacent_max = sum(odd_cycles)
    odd_cycle_count = [0] * (n + 1)
    acc = 0
    for c in odd_cycles:
        odd_cycle_count[acc + 1] += 1
        acc += c
    for i in range(n):
        odd_cycle_count[i + 1] += odd_cycle_count[i]

    def put_zero(x):
        tmp = x * 2
        if even_cycles[x] == x:
            return tmp, x, 0
        if even_cycles[x] < even_cycles[-1]:
            return tmp, x - 1, 2
        p2 = even_cycles[x]
        x -= even_cycles[x]
        if x <= odd_cycle_no_adjacent_max:
            occ = odd_cycle_count[x]
            return tmp, p2 + x - occ, occ * 2
        p2 += odd_cycle_no_adjacent_max - odd_cycle_count[-1]
        p1 = odd_cycle_count[-1] * 2
        x -= odd_cycle_no_adjacent_max
        if x <= odd_cycle_count[-1]:
            return tmp - x, p2 + x, p1 - x * 2
        tmp -= odd_cycle_count[-1]
        p2 += odd_cycle_count[-1]
        p1 -= odd_cycle_count[-1] * 2
        x -= odd_cycle_count[-1]
        if x <= iso_total_v:
            return tmp - x, p2, p1
        tmp -= iso_total_v
        x -= iso_total_v
        return tmp - x * 2, p2 - x, p1

    ans = []
    for x, y, z in queries:
        score, p2, p1 = put_zero(x)
        score += min(p2, y) * 2
        y -= min(y, p2)
        score += min(p1, y)
        ans.append(score)

    return ans


n = int(input())
ppp = list(map(int, input().split()))
q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, ppp, q, queries)
print('\n'.join(map(str, ans)))

D - Favorite Interval

問題文

整数 $N, L, R$ が与えられます。これらの整数について、以下が成り立ちます。
- $2 \leq N$
- $0\leq L \lt R \leq N$
- $(L, R)\neq (0, N)$

長さ $N$ の数列 $A = (A_{0}, A_{1}, \dots , A_{N - 1})$ を $A = (0, 1, \dots, N - 1)$ と初期化します。
$(R - L, R - L + 1, \dots , N - 1)$ の順列 $P = (P_{0}, P_{1}, \dots, P_{N - (R - L) - 1})$ をひとつ選び、$i = 0, 1, \dots N - (R - L) - 1$ の順に以下の操作を行います。
- $P_{i}$ を $|A|$ で割ったあまりを $a$ とし、$A_{a}$ を $A$ から削除する(要素の削除後、数列 $A$ の添え字は $0$ から振り直されるものとする)

最終的に $A = (L, L + 1, \dots , R - 1)$ となるような $P$ が存在するか判定し、存在するならばそのような $P$ をひとつ出力してください。

制約

$2\leq N\leq 2\times 10^{5}$
$0\leq L \lt R\leq N$
$(L, R) \neq (0, N)$
入力は全て整数

解法

問題設定がややこしい。

(例) N=16  L=5  R=11

初期のA          (0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)
残すべきA                  (5,6,7,8,9,10)

順列の元となるP              (6,7,8,9,10,11,12,13,14,15)

例えば P1=12 として操作すると...
        i         0,1,2,3,4,5,6,7,8,9,10,11,   12,13,14
操作後のA        (0,1,2,3,4,5,6,7,8,9,10,11,   13,14,15)

次に P2=14 として操作すると...
        i         0,1,2,3,4,5,6,7,8,9,10,11,   12,13
操作後のA        (0,1,2,3,4,5,6,7,8,9,10,11,   13,14   )

次に P3=15 として操作すると、15 % (現時点のAの長さ:14) = 1 なので...
        i         0,  1,2,3,4,5,6,7,8, 9,10,   11,12
操作後のA        (0,  2,3,4,5,6,7,8,9,10,11,   13,14   )

これを繰り返して、残すべき $A$ のみを残せるような手順を構築すればよい。

実験

$w=R-L$ とする。$w$ は最終的な $A$ の長さとなる。また、順列 $P$ は $w～N-1$ の順列となり、$0～w-1$ の $w$ 個の数が含まれないことになる。

ひとまず取っかかりを見つけるため、愚直解法で実験する。
$N,w$ が同じなら、$L,R$ によらず $P$ の順列候補は同じなので、「$(N,w)$ を決めて $P$ を全探索してシミュレートし、残った $A$ が $(L,L+1,...,R-1)$ になっていたら $(L,R)$ を可能として記録する」と、一度に複数の $(L,R)$ について試せる。

以下のような結果となる。

  N  w     可能な(L,R)の組とパターン数
(11, 6)  # (0,6)=1,  (1,7)=3,  (2,8)=2
(12, 6)  # (0,6)=1,  (1,7)=4,  (2,8)=9,  (3,9)=1
(13, 6)  # (0,6)=1,  (1,7)=5,  (2,8)=19, (3,9)=13,                      (7,13)=1
(14, 6)  # (0,6)=65, (1,7)=104,(2,8)=90, (3,9)=62, (4,10)=9,            (7,13)=6, (8,14)=1
(15, 6)  # (0,6)=615,(1,7)=586,(2,8)=494,(3,9)=278,(4,10)=119,(5,11)=4, (7,13)=42,(8,14)=15,(9,15)=26

$N$ が小さいうちは $L$ が大きくなると途中でダメになっているが、 $N=13$ 以降、$L=7$ から唐突に再び可能となっている。
他の $N,w$ でも実験した結果、どうやら $L \ge w+1$ から再び可能となるらしいことが推測できる。

よって、2つに分けて考えてみる。

$w+1 \le L$ の場合

$w+1 \le L$ という条件は、「残すべき $A$」より左側に、$P$ の一部が存在していることを意味する。（下例では $6,7$）

初期のA          (0,1,2,3,4,5,6,7,8,9,10,11,12,13)
残すべきA                        (8,9,10,11,12,13)

順列の元となるP              (6,7,8,9,10,11,12,13)
                              ~~~

$R=N$ の場合、初手で最小の $6$ を選び、続けて $13,12,11,10,...,7$ としていくと、 $6$ 以外は常に残っている $A$ の先頭が削除されていき、残すべき $A$ の形になる。

$R \lt N$ の場合、

初期のA          (0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)
残すべきA                        (8,9,10,11,12,13)

順列の元となるP              (6,7,8,9,10,11,12,13,14,15)

最初に $(15,14)$ のように $N-1$ から $R$ までの要素を末尾から消しておくと、$R=N$ の場合に帰着できる。

$w+1 \gt L$ の場合

とにかく「値」と「index」がズレていくため状態の把握が難しいのだが、以下のように「$A$ を固定し、$P$ をずらしていく」と考えると多少は考えやすくなるかも。
「この $A_i$ を消すにはどの $P_j$ に操作すれば良いか」を、常に合わせていく感じ。

残っているA   0  1  2  3  4 [5  6  7  8  9 10]11 12 13 14 15    [括弧]は残すべき列
残っているP                     6  7  8  9 10 11 12 13 14 15
                                              ~~
             Pで11を選ぶと、Aからは「残っているA」に対応する11が消される。
             その後、Pの11より後ろにある各要素が1つスライドする。
             末尾から押し出された要素は先頭に移動する。
             
残っているA   0  1  2  3  4 [5  6  7  8  9 10]__ 12 13 14 15
残っているP  15                 6  7  8  9 10       12 13 14
                                                       ~~
             次にPで13を選ぶとAからは14が消される。
             Pで13より後ろにある要素は1つスライドする。
             先頭に移動済みの要素は1つスライドする。
             
残っているA   0  1  2  3  4 [5  6  7  8  9 10]__ 12 13 __ 15
残っているP  14 15              6  7  8  9 10       12
             ~~
             Pで14を選ぶとAからは0が消される。
             Pで14より後ろにある要素は1つスライドする。
             先頭に移動済みの要素は1つスライドする。
             （両方に当てはまる15は2つスライドする）
             スライドする際は、既に消されている要素の位置は飛ばす。

残っているA  __  1  2  3  4 [5  6  7  8  9 10]__ 12 13 __ 15
残っているP           15           6  7  8  9    10       12
                      ~~

残っているA  __  1  2 __  4 [5  6  7  8  9 10]__ 12 13 __ 15
残っているP     12                    6  7  8     9 10
                                                 ~~

残っているA  __  1  2 __  4 [5  6  7  8  9 10]__ __ 13 __ 15
残っているP        12                 6  7  8             10
                   ~~

残っているA  __  1 __ __  4 [5  6  7  8  9 10]__ __ 13 __ 15
残っているP     10                       6  7        8
                ~~

残っているA  __ __ __ __  4 [5  6  7  8  9 10]__ __ 13 __ 15
残っているP                                 6        7     8
                                                    ~~

残っているA  __ __ __ __  4 [5  6  7  8  9 10]__ __ __ __ 15
残っているP               8                 6
                         ~~

残っているA  __ __ __ __ __ [5  6  7  8  9 10]__ __ __ __ 15
残っているP                                                6
                                                          ~~

残っているA  __ __ __ __ __ [5  6  7  8  9 10]__ __ __ __ __  できた！

ここで、$w+1 \gt L$ より、初期の $P$ の最小値（例では $6$）は、「残すべき $A$」の区間内である。
少なくともこれをスライドさせ区間右端から出さないと、$6$ 自身を選ぶことができない。
スライドさせる距離は、「区間より左にある消すべき要素数」と一致する。

残っているA   0  1  2  3  4 [5  6  7  8  9 10]11 12 13 14 15
残っているP                     6  7  8  9 10 11 12 13 14 15
                               ~~                             ←最小値は残すべき区間の中
途中経過のP   ~~~~~~~~~~~~~      ------------> 6
                ↑ここの要素を全て消すことで  ↑ここまで押し出してこれる

「残すべき区間より左/右にある消すべき要素」を、単に「左側の要素/右側の要素」と呼ぶことにする。
上記では、$(0,1,2,3,4)$ が左側、$(11,12,13,14,15)$ が右側の要素となる。
「左側の要素数」「右側の要素数」を、それぞれ $x,y$ とする。

初期状態では、左側に $P$ は存在しないので消すことができない。
右側（の中のなるべく左）を消して後続要素をスライドさせ、ループさせ先頭に持ってくることでのみ、左側に $P$ の要素を持ってこられる。

まず、$x \lt y$ の時は、先ほどの「$w+1 \le L$ の場合」と似た感じで可能。

$N-(x+1)$（右端から $x+1$ 番目にある要素）を選択する。
$N-1,N-2,...,N-x$ を順に選択する。

これで左側の要素は全て消され、右側のみが残る形となるので、末尾から消していけば完成となる。

残っているA   0  1  2  3 [4  5  6  7  8  9 10]11 12 13 14 15 16
残っているP                        7  8  9 10 11 12 13 14 15 16

x=4 のため、右から5番目の 12 を選択。
次に、16,15,14,13 を選ぶ。
これらは順次先頭に送られ、A の 0,1,2,3 をそれぞれ消すとともに、各Pを右にスライドさせていく。

残っているA  __ __ __ __ [4  5  6  7  8  9 10]11 __ 13 14 15 16
残っているP                                    7     8  9 10 11

その後、11から順に消していけばよい。

では $x \ge y$ の場合は？

一度には $x$ を消しきれないまでも、複数回に分けて似たようなことをできる。

残っているA   0  1  2  3  4 [5  6  7  8  9 10]11 12 13 14 15
残っているP                     6  7  8  9 10 11 12 13 14 15

$(11,15,14,13,12)$ のように、右側の要素 $11～15$ のうち、

左端 $11$ をまず消す
次いで逆順に $15～12$ を消していく

とすることで、「右側の要素を $1$ 個、左側の要素を $y-1$ 個消す」ことができる。
この結果、$N←N-y, x←x-(y-1), y←y-1$ とした問題に帰着できる。

上例から (11,15,14,13,12) と操作した後の状態は↓と実質的に一緒

残っているA   0 [1  2  3  4  5  6] 7  8  9 10
残っているP                     6  7  8  9 10

これを繰り返し $x \lt y$ になったら、前述の方法で完成できる。

この手順で消し切れる $x,y$ の関係性は、$x \le 1+2+...+(y-1) = \dfrac{y(y-1)}{2}$ であることとなる。
よって、この判定を最初におこない、可能なら上記の方法で構築すればよい。

逆に $x \gt \dfrac{y(y-1)}{2}$ だと、どうしても左が消しきれずに残る。

証明は公式Editorial 参照

Python3

def solve(n, l, r):
    w = r - l
    r = n - r
    ans = []
    if w + 1 <= l:
        ans.extend(range(n - 1, n - (r + 1), -1))
        ans.append(w)
        ans.extend(range(n - (r + 1), w, -1))
        return ans
    if l > r * (r - 1) // 2:
        return None
    while l + 1 > r:
        ans.append(n - r)
        ans.extend(range(n - 1, n - r, -1))
        l -= r - 1
        n -= r
        r -= 1
    ans.append(n - (l + 1))
    ans.extend(range(n - 1, n - (l + 1), -1))
    ans.extend(range(n - (l + 2), w - 1, -1))
    return ans


def simulate(n, l, r, ans):
    aaa = list(range(n))
    for a in ans:
        aaa.pop(a % len(aaa))
    correct = aaa == list(range(l, r))
    print(aaa, correct)


n, l, r = map(int, input().split())
ans = solve(n, l, r)
if ans is None:
    print('No')
else:
    print('Yes')
    print(*ans)
    # simulate(n, l, r, ans)

目次

AtCoder Regular Contest 204 (Div. 1) A,B,C,D 問題メモ

A - Use Udon Coupon

問題文

制約

解法

B - Sort Permutation

問題文

制約

解法

C - Maximize Sum of Mex

問題文

制約

解法

配置

D - Favorite Interval

問題文

制約

解法

実験

$w+1 \le L$ の場合

$w+1 \gt L$ の場合