AtCoder Regular Contest 171 B,C,D問題メモ

B - Chmax

問題

$(1,2,...,N)$ の順列 $P$ に対して、以下を $F(P)$ と定義する
- 数列 $B=(1,2,...,N)$ で初期化する
- $B_i$ のうち、$B_i \lt P_{Bi}$ を満たす $i$ のうち最小のものを $j$ とし、$B_j←P_{Bj}$ に置き換える
- 置換ができなくなるまで繰り返した時の $B$ を $F(P)$ とする
長さ $N$ の数列 $A=(A_1,...,A_N)$ が与えられるので、$F(P)=A$ となるような $P$ の個数を求めよ
$1 \le N \le 2 \times 10^5$
$1 \le A_i \le N$

例

文章としては複雑だけど、要は $B$ の各要素に対して $b→\max(b,P_b)$ という置換を繰り返していけばよい。

i  1 2 3 4
P  2 4 3 1  に対するF(P)の求める手順

B  1 2 3 4
            ... B[1]=1  <  P[B[1]]=2  なので、B[1]←2に置換
B  2 2 3 4
            ... B[1]=2  <  P[B[1]]=4  なので、B[1]←4に置換
B  4 2 3 4
            ... B[2]=2  <  P[B[2]]=4  なので、B[2]←4に置換
B  4 4 3 4
            ... もう置き換えられるものはないので、終了

解法

まず、B は必ず大きい値に置き換えられるので、初期状態 $B=(1,2,...,N)$ のうち、$A_i \lt B_i$ となるものがあったら無理。（0通り）

そうでない場合、$A$ にはいくつかの同じ値が含まれている。それ毎にグループ化する。

i  1 2 3 4 5 6 7 8
A  6 6 8 4 5 6 8 8

   6 6       6
       8       8 8
         4
           5

置換配列 $P$ は順列なので、異なる $i$ から同じ数字 $P_i$ に置換できない。
例えば上記では、1→6 と 2→6 という“直接の”置換を両立するような $P$ は存在しない。

置換の法則から、値の位置 $i$ によらず、ある時点の $B_i$ と $B_j$ が同じ値ならその後同じ変化をし、最終的に同じ値に行き着く、という点は重要。また、置換は値が大きくなる方向にのみ行われる。

よって、必ず 1→2→6 というように、小さい方から同じ値になるindexを辿って置換されていく必要がある。
すると、$P$ に求められる条件が決まってくる。

グループ6に着目して、あり得るPとして決まった箇所

i  1 2 3 4 5 6 7 8
P  2 6       ^        
             6以下の値

グループの中で最大の位置は、置き換えられてはいけない。
例えば、上記で $P_6=7$ だったりすると、$P_1,P_2$ も7まで置換が進んでいないとおかしいことになる。
よって、$i \ge P_i$ という制約がかかる。

同じ理由から、各グループの最大の位置 $i$ について $i=A_i$ でない場合、答えは0通りとなる。

以下、$A$ はそれを満たすとする。

グループ6と同様に、他のグループについての制約を全て適用すると、以下のようになる。

i  1 2 3 4 5 6 7 8
P  2 6 7 ^ ^ ^ 8 ^
         4 5 6   8  ←○以下の値しか入れられない、という制約

まだPに使われていない値: 1,3,4,5

まだPに使われていない値は、各グループで一番左の $i$ となる。

各グループの中で最大の位置 $I=\{4,5,6,8\}$ に、使われていない値 $R=\{1,3,4,5\}$ を、 $i \ge P_i$ となるように埋める方法の個数が、答えとなる。

$R$ の大きい方から埋められる箇所の個数を求めていけばよい。

r=5  置けるIの箇所は3箇所  →  3
r=4  置けるIの箇所は4箇所だが、1箇所は既に埋まっている  →  3
r=3  置けるIの箇所は4箇所だが、2箇所は既に埋まっている  →  2
r=1  置けるIの箇所は4箇所だが、3箇所は既に埋まっている  →  1

3*3*2*1 = 18 通り

$O(N)$ や $O(N \log{N})$ で解ける。

Python3

from bisect import bisect_left


def solve(n, aaa):
    not_changed = set()
    changed = set()
    remaining = set(range(1, n + 1))

    for i, a in enumerate(aaa, start=1):
        if i == a:
            not_changed.add(a)
        elif i > a:
            return 0
        else:
            if aaa[a - 1] != a:
                return 0
            if a in changed:
                remaining.discard(i)
            else:
                changed.add(a)

    remaining -= changed

    ans = 1
    MOD = 998244353
    not_changed = sorted(not_changed)
    m = len(not_changed)

    assert m == len(remaining)

    for i, a in enumerate(sorted(remaining, reverse=True)):
        k = bisect_left(not_changed, a)
        ans *= m - i - k
        ans %= MOD

    return ans


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

C - Swap on Tree

問題

$N$ 頂点の木があり、最初、頂点 $i$ にコマ $i$ が置かれている
以下の操作を0回以上、好きな回数おこなえる
- 辺を1つ選び、両端に置かれているコマを入れ替える
- その後、選んだ辺を削除する
操作後の頂点 $1,2,...,N$ に置かれたコマを $A=(a_1,...,a_N)$ としたとき、$A$ としてあり得るものの個数を $\mod{998244353}$ で求めよ
$1 \le N \le 2 \times 10^5$

解法

操作によって木は分断され、その後2つの連結成分内のコマは入れ替わることはない。

よって、ある辺を使う場合と使わない場合では、別の $A$ となる。

①--②--③--④--⑤--⑥

③-④の辺を選ぶ場合
  ①②③頂点にあるコマの集合は、「①②③から2個と、④⑤⑥から1個」
  ④⑤⑥頂点にあるコマの集合は、「④⑤⑥から2個と、①②③から1個」

③-④の辺を選ばない場合
  ①②③頂点にあるコマの集合は、「①②③」
  ④⑤⑥頂点にあるコマの集合は、「④⑤⑥」

また、ある頂点 $v$ から出る辺について、異なる順で選んだ操作列で $A$ が同じになることはない。

雑な証明

①--②--③--④--⑤  操作列（選んだ辺の列）が決まっていて、
        ｜          その中で ③-②, ③-④, ③-⑥ がともに出てくるとする
        ⑥--⑦      （各辺を  (2)    (4)    (6)  と呼ぶことにする）

単純化のため、この3辺以外の操作を行わない場合、

(2)→(4)→(6) の順に操作  ①--③--⑥--②--⑤
                                  └--④--⑦

(6)→(4)→(2) の順に操作  ①--④--②--⑥--⑤
                                  └--③--⑦

この入れ替わり方が、辺の選び方の順（今回の場合6通り）全て異なる。
選んだ順に、頂点 ③②④⑥ にあるコマが ⑥③②④ のように、シフトする。

この3辺以外の操作も行う場合でも、連結成分にあるコマの集合で考えれば同様に考えられる。

頂点を  ③、①②、④⑤、⑥⑦グループに分ける。
それぞれG3   G2    G4    G6   とする。

最初 G3,G2,G4,G6 の頂点集合にあったコマの集合は
たとえば (2)→(4)→(6) の順に操作した場合、以下のように移動する
  G3から1頂点→G2に移る
  G2から1頂点→G4に移る
  G4から1頂点→G6に移る
  G6から1頂点→G3に移る

この移動の仕方が辺の選び順に対応し、異なる選び順では異なる $A$ となる

（省略するが本来は、以上で $A$ が異なる条件は全てであるという証明も必要。公式Editorial参照。帰納法でできるみたい）

頂点 $v$ について、「$v$ から出る辺のうち、どの辺がどの順で選ばれるか」のパターンを $P(v)$ とする。
矛盾しないように定めることができる全頂点のパターンの組 $(P(1),P(2),...,P(N))$ の個数が、求めるものとなる。
（※矛盾しない＝全ての辺 $(u,v)$ について、$P(u)$ と $P(v)$ で辺 $(u,v)$ を選ぶ/選ばないが一致している）

根を適当に決めて、以下のDPをする。

$DP[v,k]=$ 頂点 $v$ 以下の部分木に含まれる全頂点についての矛盾しないパターンの組 $(P(v),P(w),P(x),P(y),...)$ の個数
- ただし $v$ の親への辺については未考慮でよい
- 親で $v-親$ 間の辺を考慮する時に必要なため、$v$ の子頂点への辺を何個選ぶか（$k$）で場合分け

     (v)
   ／ | ＼
 (w) (x) (y)
  :   :   :

$DP[v]$ を計算するため、以下のDPをする。

$DP2[i,k]=v$ の $i$ 番目の子まで考慮して、そのうち $k$ 個を選んだ状態の暫定の $DP[v,k]$

        k:0  1  2  3
DP2[0] = [1, 0, 0, 0] と初期化する。kはvの子の数まで用意する。

子頂点を1つずつ採用/不採用を決めていく。

1つめの子の DP[w] = [5, 9, 3] だとして、

辺 v-w を選ぶ場合の係数:
  DP[w,k] で子を k 個選んでいる中の、どこに v-w 辺を挿入するか、という場合分けが増える。
  k に対して (k+1) 通りなので、
  
  t = Σ_k( DP[w,k] * (k+1) ) = 5*1 + 9*2 + 3*3 = 32
  
辺 v-w を選ばない場合の係数:
  v-w 辺を選ばない場合には、k での場合分けは不要。単純に w 以下の決め方となる。
  
  s = sum(DP[w]) = 17


DP2[0] から DP[1] の遷移は、↓選ばない場合 s 倍、↘選ぶ場合 t 倍となる。

DP2[0] = [1,  0,  0, 0]
  ↓
DP2[1] = [17, 32, 0, 0]

他の子についても同様に遷移していき、最終的に $DP2[vの子の数]$ が得られる。

ここに、各 $k$ につき子の選び順 $k!$ をかけたものが、$DP[v]$ となる。

全体を $O(N^2)$ で計算できる。

二乗の木DPは、各頂点に付き「部分木の頂点数」分の配列を持ってマージしていっても $O(N^2)$ で収まるという理論だが、この問題では、各頂点に付き「子の頂点数」分の配列しか不要だし、マージも子ごとに独立に計算できるので、ランダムなケースでの平均計算量はより少なく済む。

1つの根が $N-1$ 個の子を持つようなヒトデグラフなど、特殊な場合の最悪計算量として $O(N^2)$ かかる感じ。

Python3

def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


n = int(input())
MOD = 998244353
facts, finvs = precompute_factorials(n, MOD)
links = [set() for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)

q = [0]
status = [0] * n
dp = [[] for _ in range(n)]
while q:
    u = q[-1]
    if status[u] == 0:
        status[u] = 1
        for v in links[u]:
            links[v].remove(u)
            q.append(v)
    else:
        q.pop()
        ch_cnt = len(links[u])
        dp_u = [0] * (ch_cnt + 1)
        dp_u[0] = 1
        for i, v in enumerate(links[u]):
            dp_v = dp[v]
            s = sum(dp_v) % MOD
            t = 0
            for j, val in enumerate(dp_v):
                t += (j + 1) * val
            t %= MOD
            dp_u[ch_cnt] *= s
            for j in range(i, -1, -1):
                dp_u[j + 1] += dp_u[j] * t
                dp_u[j] *= s
                dp_u[j + 1] %= MOD
                dp_u[j] %= MOD
        for i in range(ch_cnt + 1):
            dp_u[i] *= facts[i]
            dp_u[i] %= MOD
        dp[u] = dp_u

ans = sum(dp[0]) % MOD
print(ans)

D - Rolling Hash

問題

非負整数列 $X=(x_1,...,x_n)$ に対して、以下を $hash(X)$ とする
- $hash(X) = (x_1 B^{n-1} + x_2 B^{n-2} + ... + x_n B^0) \mod{P}$
- つまり、$B$ を基数、割ってあまりを取る数を $P$ としたローリングハッシュ
$M$ 個の区間 $(L_i,R_i)$ が与えられる
次の条件を満たす、長さ $N$ の非負整数列 $A=(A_1,...,A_N)$ があるか判定せよ
- 全ての区間について、$hash((A_L,A_{L+1},...,A_R)) \neq 0$ である
$1 \le N ale 16$
$1 \le B \lt P \le 10^9$
$P$ は素数

解法

以下、添字が合わないのが気持ち悪いので、$A$ の添字を0始まりとし、ローリングハッシュも逆に（先頭が下の位になるように）計算することにする。

$hash(A) = (A_0B^0 + A_1B^1 + ... + A_{n-1}B^{n-1}) \mod{P}$

クエリ $L,R$ も、元の位置から、逆転させたこの並びの位置に対応させれば、元の問題と変わらない。

先頭からこれの累積和を取ったものを $C$ とすると、

C[-1] = 0                     （便宜的にC[-1]を0とする）
C0    = A0B^0
C1    = A0B^0 + A1B^1
C2    = A0B^0 + A1B^1 + A2B^2
 :    :
C[N-1]= A0B^0 + A1B^1 + A2B^2 + ... + A[N-1]B^(N-1)

区間 $(L,R)$ を抜き出した文字列のハッシュは、$C$ を使って表せる。

$hash(A_L～A_R) = \dfrac{C_R - C_{L-1}}{B^{L}}$

$P$ が素数で $\dfrac{1}{B^{L}} = B^{-L} \not\equiv 0 \mod{P}$ なので、modで考えても上の式がゼロ除算で計算できなくなることはない。

よって、これが0になる時というのは、$C_R \equiv C_{L-1} \mod{P}$ のときに限られる。

つまり、$C[-1]$ も合わせて全部で $N+1$ 個の頂点があって、「こことここは同じになってはいけない」という条件が $M$ 個与えられる、と考えられる。

これは、グラフの頂点彩色の問題に言い換えられる。

グラフ彩色#頂点彩色

$A$ にはどんな数でも置けるので、上手く調整すれば $C$ の各項は $0 \le C_i \le P-1$ の $P$ 個の値を好きに設定できる。
（言い換えると、各要素が $0 \le C_i \le P-1$ である任意の $C$ に対して、対応する $A$ が存在する）

ここで、もしグラフを塗り分けるのに $P+1$ 以上の色が必要となった場合、どうしてもどれかは被ってしまい、アウトとなる。
逆に $P$ 色以下なら、可能となる。

頂点彩色数は、bitDPで $O(N2^N)$ や $O(3^N)$ で計算できる。

彩色数を求めるアルゴリズム - Learning Algorithms

$P$ の制約はやたらでかいくせにほとんどの場合Yesで、求めるのが難しいのは $P \le 13$ の時のみという、なかなか癖のある問題。

Python3

def bruteforce(p, b, n, aaa):
    for i in range(n):
        for j in range(i + 1, n + 1):
            ccc = aaa[i:j]
            rh = 0
            for c in ccc:
                rh = (rh * b + c) % p
            if rh == 0:
                return False
    return True


def bruteforce_test():
    from itertools import product
    n = 5
    p = 5
    b = 4
    ok = 0
    ng = 0
    for aaa in product(range(1, p), repeat=n):
        if bruteforce(p, b, n, aaa):
            ok += 1
            print(aaa)
        else:
            ng += 1

    print(ok, ng)


def chromatic_number(n, links) -> int:
    """
    （頂点）彩色数を求める

    Args:
        n (int): 頂点数
        links (list[int]): links[i] = i と隣接する頂点を bitset で表現したリスト

    References:
        https://kokiymgch.hatenablog.com/entry/2018/01/27/235959

    """
    n2 = 1 << n

    dp = [0] * n2
    pm = [0] * n2
    pm[0] = 1
    for i in range(1, n2):
        lsb = i & -i
        pm[i] = pm[i ^ lsb] * -1
    pm.reverse()

    dp[0] = 1
    for i in range(1, n2):
        lsb = i & -i
        j = lsb.bit_length() - 1
        dp[i] = dp[i ^ lsb] + dp[(i ^ lsb) & ~links[j]]

    for k in range(1, n):
        res = 0
        for i in range(n2):
            cur = pm[i] * dp[i]
            pm[i] = cur
            res += cur
        if res > 0:
            return k

    return n


p, b, n, m = map(int, input().split())
n += 1
n2 = 1 << n

links = [0] * n
for _ in range(m):
    l, r = map(int, input().split())
    l -= 1
    links[l] |= 1 << r
    links[r] |= 1 << l

if n <= p:
    print('Yes')
    exit()

cn = chromatic_number(n, links)
if p >= cn:
    print('Yes')
else:
    print('No')

目次

AtCoder Regular Contest 171 B,C,D問題メモ

B - Chmax

問題

例

解法

C - Swap on Tree

問題

解法

D - Rolling Hash

問題

解法