AtCoder Regular Contest 187 A,B,C問題メモ

AtCoder Regular Contest 187

A - Add and Swap

• 整数 $N,K$ 及び長さ $N$ の数列 $A=(A_1,\ldots,A_N)$ が与えられます．
• $A$ に対し以下の操作を $500000$ 回以下行うことで $A$ を広義単調増加にできるか判定し，可能な場合は実際に操作手順（選択した $i$ の列）を一つ示してください．
  • $1$ 以上 $N-1$ 以下の整数 $i$ を選ぶ．$A_i$ を $A_{i+1}+K$ で，$A_{i+1}$ を $A_i$ で同時に置き換える．

• 入力される数値は全て整数
• $2 \leq N \leq 50$
• $1\leq K \leq 50$
• $1\leq A_i\leq 50$

$N=2$ の時は自明なので省略。$N \ge 3$ とする。
$N \ge 3$ のとき、必ず構築できる。

$A_i,A_{i+1}$ に対して行う操作を「操作 $i$」とする。

2回連続で操作 $i$ をすることは、$A_i,A_{i+1}$ に $K$ ずつ加算するのと同じ意味になる。

$i=2,3,...,N-1$ の順に「$A_{i-1} \le A_i$ となるまで操作 $i$ を繰り返す」ことで、最後の2つ以外は広義単調増加にできる。

最後の2つが、

• ①そのままで $A_{N-1} \le A_N$ ならよし
• ②$N-1$ に1回操作して $A_{N-1} \le A_N$ になるならよし
  • $A_{N-2} \le A_{N-1}$ になるまで偶数回の操作 $N-1$ を追加で行う

そうで無い場合というのは、大小関係を整理すると $0 \lt A_{N-1} - A_N \lt K$ の場合に発生する。
この状態は、何回操作 $N-1$ をしても $A_{N-1} \le A_N$ になることはない。

逆に言うと、$A_{N-1} - A_N \ge K$ の状態にすると②に持ち込める。
これは、偶数回の操作 $N-2$ を十分な数を行うと、 いずれの大小関係も変化させないまま、確実に達成できる。

K=5

前から操作して、最後の2つ以外広義単調増加になった状態
... 11 12 15 11

N-2 に対し偶数回操作する。この状況下ではどの隣接2要素の大小関係も変化しない。
（たとえば100回操作後）
... 11 262 265 11

そうすると、N-1 に1回操作すると確実に A[N-1] <= A[N] となるので、
... 11 262 16 265

あとは、A[N-2] <= A[N-1] となるまで偶数回の追加操作をすれば、完成。
... 11 262 266 515

操作回数は厳密に見積もれていないが、 まぁ $O(N \max(N,A_{\max}))$ くらいで、さすがに $500000$ は行かないでしょ、で投げると通る。

Python3

def check(n, k, aaa, ans):
    for i in ans:
        aaa[i - 1], aaa[i] = aaa[i] + k, aaa[i - 1]
    for i in range(n - 1):
        if aaa[i] > aaa[i + 1]:
            return False, aaa
    return True, aaa


def solve(n, k, aaa):
    if n == 2:
        if aaa[0] <= aaa[1]:
            return []
        elif aaa[1] + k <= aaa[0]:
            return [1]
        else:
            return None

    ans = []
    for i in range(1, n - 1):
        while aaa[i - 1] > aaa[i]:
            aaa[i], aaa[i + 1] = aaa[i + 1] + k, aaa[i]
            ans.append(i + 1)
    if aaa[-2] > aaa[-1]:
        if aaa[-1] + k <= aaa[-2]:
            while aaa[-3] > aaa[-2] or aaa[-2] > aaa[-1]:
                aaa[-2], aaa[-1] = aaa[-1] + k, aaa[-2]
                ans.append(n - 1)
        else:
            for i in range(50):
                aaa[-3], aaa[-2] = aaa[-2] + k, aaa[-3]
                ans.append(n - 2)
            while aaa[-3] > aaa[-2] or aaa[-2] > aaa[-1]:
                aaa[-2], aaa[-1] = aaa[-1] + k, aaa[-2]
                ans.append(n - 1)

    return ans


n, k = map(int, input().split())
aaa = list(map(int, input().split()))

ans = solve(n, k, aaa)
if ans is None:
    print('No')
else:
    print('Yes')
    print(len(ans))
    print(*ans)

B - Sum of CC

• 長さ $N$ の数列 $A=(A_1,\ldots,A_N)$ に対し，$f(A)$ を以下で定義します．
  • 頂点に $1$ から $N$ の番号がついた $N$ 頂点 $0$ 辺のグラフを用意する．
  • $1\leq i \lt j\leq N$ を満たす全ての整数組 $(i,j)$ に対し，$A_i\leq A_j$ ならば頂点 $i$ と頂点 $j$ を双方向に結ぶ辺を張る．
  • 最終的に得られるグラフの連結成分数を $f(A)$ と定める．

• 長さ $N$ の数列 $B=(B_1,\ldots,B_N)$ が与えられます． $B$ の各要素は $-1$ または $1$ 以上 $M$ 以下の整数です．
• $B$ の要素のうち，$-1$ を全て $1$ 以上 $M$ 以下の整数に置き換えて得られる数列 $B'$ は，$B$ に含まれる $-1$ の個数を $q$ とすると $M^q$ 通りあります．
• 考えられる $B'$ 全てに対する $f(B')$ の総和を $998244353$ で割ったあまりを求めてください．

• 入力される数値は全て整数
• $2 \leq N \leq 2000$
• $1\leq M\leq 2000$
• $B_i$ は $-1$ または $1$ 以上 $M$ 以下の整数

ある2要素間に辺が張られる場合、その間にある全ての頂点は連結になる。

i   k         j
5 o o ... o o 9
`-------------'

Ak < 5   の場合: k-j に辺が張られる
5<=Ak<=9 の場合: i-k, k-j ともに辺が張られる
9 < Ak   の場合: i-k に辺が張られる

なので、連結成分が2つに分かれる場合、区間でばっさり分かれる。（$i=1,3$ が連結、$i=2,4$ が連結、両者同士は非連結、みたいになることはない）

ある境界位置 $j$ と境界値 $k$ について、「$j$ より前の $A_i$ が全て $k$ 以上」かつ「$j$ 以降の $A_i$ が全て $k$ 未満」の場合、そこで非連結となる。

8 7-9 | 4-6 5 | 2 1-3
`---'   `---'   `---'

主客転倒して、「$i$ 毎に、$i$ と $i+1$ が非連結となる“-1”の埋め方の個数を数える」ことにする。

固定された値のみで、前からの累積最小値を $P_i$、後ろからの累積最大値を $Q_i$ とする。

$i=1～N-1$ のそれぞれで境界を固定する。$1～i$ の区間を前半、$i+1～N$ の区間を後半とする。

• $P_{i} \le Q_{i+1}$ なら、そこで非連結とすることは不可能。
• それ以外の場合、前半最小値を $p=Q_{i+1}+1,Q_{i+1}+2,...,P_{i}$ のそれぞれに固定して、パターン数を求める。
  • 前半最小値がちょうど $p$ となるのは、前半の“-1”の個数を $k$ として、
    • $p \lt P_{i}$ のとき、$(M-p+1)^k-(M-p)^k$
    • $p = P_{i}$ のとき、$(M-p+1)^k$
  • 後半最大値が $p$ 未満となるのは、後半の“-1”の個数を $l$ として、$(p-1)^l$
  • これらを掛け合わせた数が、$(i, p)$ 固定時の答えへの寄与。

$O(NM)$ で求められる。

※前半最小値 p は、「ちょうど」となる割り当て方をしないと、重複が発生する。

-1 7 -1 | -1 4 2 -1     p としては、5,6,7 があり得るが、
                        ただ単に「前半の-1をp以上に置き換える」
                        「後半の-1をp未満に置き換える」だけだと、
 8 7 9  |  3 4 2 1      左の置き換えは p=5,6,7 のいずれでも数えられてしまう。

Python3

def solve(n, m, aaa):
    MOD = 998244353

    bwd_max = [1]
    bwd_cnt = [0]
    for i in range(n - 1, -1, -1):
        if aaa[i] == -1:
            bwd_cnt.append(bwd_cnt[-1] + 1)
            bwd_max.append(bwd_max[-1])
        else:
            bwd_cnt.append(bwd_cnt[-1])
            bwd_max.append(max(bwd_max[-1], aaa[i]))
    bwd_max.reverse()
    bwd_cnt.reverse()

    if aaa[0] == -1:
        dp = [1] * (m + 2)  # i 以上の値しか使っていない数列の個数
        dp[0] = dp[-1] = 0
    else:
        dp = [0] * (m + 2)  # i 以上の値しか使っていない数列の個数
        dp[aaa[0]] = 1
    ans = pow(m, bwd_cnt[0], MOD)
    for i in range(1, n):
        a = aaa[i]
        ndp = [0] * (m + 2)
        if a == -1:
            for j in range(1, m + 1):
                # 条件を崩さずにおける数の個数
                r = m - j + 1
                ndp[j] += dp[j] * r
                ndp[j + 1] -= dp[j] * r
                # 新たに条件を崩す場合、j 以下の数に全て足し込む。
                # それ以降の -1 を j 未満で置換する数だけ、連結成分は増える
                ndp[1] += dp[j]
                ndp[j] -= dp[j]
                if j > bwd_max[i]:
                    ans += pow(j - 1, bwd_cnt[i], MOD) * dp[j]
                    ans %= MOD
            ndp[1] %= MOD
            for j in range(2, m + 1):
                ndp[j] += ndp[j - 1]
                ndp[j] %= MOD
        else:
            for j in range(1, m + 1):
                if j <= a:
                    ndp[j] += dp[j]
                else:
                    ndp[a] += dp[j]
                    if j > bwd_max[i]:
                        ans += pow(j - 1, bwd_cnt[i], MOD) * dp[j]
                        ans %= MOD
        dp = ndp

    return ans


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

C - 1 Loop Bubble Sort

• $(1,\ldots,N)$ の順列 $P=(P_1,\ldots,P_N)$ に対して，以下の操作を一度行うことにより得られる順列を $P'=(P'_1,\ldots,P'_N)$ とします．
  • $i=1,2,\ldots,N-1$ の順に，$P_i \gt P_{i+1}$ ならば $P_i$ と $P_{i+1}$ を入れ替える．

• 長さ $N$ の数列 $Q=(Q_1,\ldots,Q_N)$ が与えられます．
  • $Q_i$ は $-1$ または $1$ 以上 $N$ 以下の整数 です．
• 以下の条件を満たすような $(1,\ldots,N)$ の順列 $P$ の個数を $998244353$ で割ったあまりを求めてください．
  • $P$ から上記の操作で $P'$ を得たとき，全ての $i$ について $Q_i\neq -1 \implies Q_i=P'_i$

• 入力される数値は全て整数
• $2 \leq N \leq 5000$
• $Q_i$ は $-1$ または $1$ 以上 $N$ 以下の整数
• $Q$ に $1,2,\ldots,N$ が含まれる個数はそれぞれ $1$ 個以下

「$Q$ と合致するような $P'$ が作られるような $P$」の個数を求める。ややこしい。

$Q_i\neq -1 \implies Q_i=P'_i$ となることを、「$P'$ は $Q$ と合致する」と呼ぶことにする。

$P$ から $P'$ の作られ方を観察すると、以下のような感じになる。

i  1  2  3  4  5  6  7
P  4  1  2  6  3  7  5
    ×
   1  4  2  6  3  7  5
       ×
   1  2  4  6  3  7  5
             ×
   1  2  4  3  6  7  5
                   ×
P' 1  2  4  3  6  5  7

• $P_1$ は、それより大きい数が出てくるまで、右に運ばれる。
  • 上例では、$4$ は、自身より大きい $i=4$ の $6$ が出てくる手前まで、右に運ばれる。
• $6$ にタッチ交代すると、$6$ も自身より大きい数 $7$ の手前まで右に運ばれる。
• $7$ にタッチ交代して、これは最大値なので末尾まで運ばれる。

という流れになっている。
上記の流れを、「$(4,6,7)$ が運ばれた」と呼ぶことにする。
運ばれる要素は単調増加となる。

途中で $N$ が出てきたら、そいつは必ず末尾まで運ばれる。
よって、$P'_{N}$ はかならず $N$ である。
$Q_N$ が“-1”でも $N$ でもなかったり、$N$ が末尾以外に登場したりすれば、$0$ 通り。

また、異なる $P$ から同じ $P'$ が作られうる。
たとえば以下のような $P$ からも上例と同じ $P'$ になる。

   2  1  6  4  3  7  5
   1  2  4  6  3  7  5
   7  1  2  4  3  6  5

これは、$P'$ に出てくる、先頭から累積最大値を更新する要素について、

P' 1  2  4  3  6  5  7
   ^  ^  ^     ^     ^

「末尾 $7$ は固定で、他のどの要素の組が“運ばれた”とするか」で、$P'$ と合わせて一意に決まるようになる。

                          運ばれる要素
P  4  1  2  6  3  7  5    (4,6,7)
   `----->  `-->  `-->
P  2  1  7  4  3  6  5    (2,7)
   `-->  `----------->
P  1  2  4  6  3  7  5    (1,2,4,6,7)
   `> `> `> `-->  `-->
P  7  1  2  4  3  6  5    (7)
   `----------------->

つまり、最大値を更新する回数が $k$ 回となるような $P'$ は、元になる $P$ が $2^{k-1}$ 個あることになる。

よって、次の問題に言い換えられる。

• $Q_N=N$ とする（“-1” の場合でも埋めておく）
• $Q$ と合致するような全ての順列に対し、先頭からの累積最大値を更新する回数を $k$ として $2^{k-1}$ を計算し、総和を求めよ

一見、“-1”の埋め方を先頭から決めていくのに「累積最大値の更新回数」を添え字に持たないといけなさそうに思うが、 「最大値を更新する毎に2倍」という遷移はこれまでに何回更新したかに依らないので、実は状態をまとめられる。

• $\mathrm{DP}[i,j]:=P'_i$ まで決めて、暫定累積最大値が $j$ となるような順列における、$2^{k-1}$ の総和
  • $k$ は先頭からの累積最大値の更新回数

遷移は、もらうDPで考える。
$Q$ に“-1”以外で出てくる値を「固定値」、出てこない値を「非固定値」とする。

■ Qi = a（固定値）のとき

・最大値を更新する場合
    DP[i-1, k] のうち、k が a 未満である箇所から遷移できる。
    累積最大値更新回数が1増えるので一律に 2 をかける。
    
    DP[i, a] = ΣDP[i-1, k] * 2    （k = 1 ～ a-1）
 
 
・最大値を更新しない場合
    既に累積最大値が a より大きい箇所から遷移できる。
    状態数は特に変わらない。

    DP[i, j] = DP[i-1, j]           (j = a+1 ～ N)


■ Qi = -1 のとき
  
  各 j につき、以下のように遷移する。
  
・P'i に j を置き、最大値を更新する場合
    j が非固定値の場合のみ、この遷移をおこなえる。
    
    DP[i, j] = ΣDP[i-1, k] * 2    （k = 1 ～ j-1）
    

・P'i に j 未満の数を置き、累積最大値 j を継続する場合
    f: Qi より前にある -1 の個数（j が非固定値の場合はさらに - 1）
    g: j 未満の非固定値の個数
    
    Qi より前にある -1 は、全て j 未満の非固定値で埋める必要がある。
    （j も非固定値の場合、そのうちの1つは j に使う必要がある）
    f >= g の場合、j 未満の非固定値が足りなくなるので、この遷移はできない。
    
    そうで無い場合、P'i に置く j 未満の数として、g-f 個の自由度がある。
    
    DP[i, j] += DP[i-1, j] * (g-f)

$\mathrm{DP}[N,N]$ が答えとなる。

Σの部分は累積和で高速化できるので、全体 $O(N^2)$ で求められる。

Python3

from itertools import accumulate


def naive(n, aaa):
    from pprint import pprint
    from collections import defaultdict
    from itertools import permutations
    check_idx = [i for i, a in enumerate(aaa) if a != -1]
    result = defaultdict(list)
    for ppp_ in permutations(range(1, n + 1)):
        ppp = list(ppp_)
        for i in range(n - 1):
            if ppp[i] > ppp[i + 1]:
                ppp[i], ppp[i + 1] = ppp[i + 1], ppp[i]
        ok = True
        for i in check_idx:
            if ppp[i] != aaa[i]:
                ok = False
                break
        if ok:
            result[tuple(ppp)].append(ppp_)
    pprint(result)
    ans = sum(len(r) for r in result.values())
    print(ans)


def solve(n, aaa):
    MOD = 998244353

    # N は P'で必ず末尾に来る
    if aaa[-1] != -1 and aaa[-1] != n:
        return 0
    if n in aaa[:-1]:
        return 0
    aaa[-1] = n

    aaa = [max(a - 1, -1) for a in aaa]

    is_fixed = [0] * n
    for a in aaa:
        if a != -1:
            is_fixed[a] = 1

    dp = [0] * n
    free_count = 0
    if aaa[0] == -1:
        free_count += 1
        for i in range(n):
            if is_fixed[i] == 0:
                dp[i] = 1
    else:
        dp[aaa[0]] = 1

    acc_fixed = list(accumulate(is_fixed))
    for i in range(1, n):
        a = aaa[i]
        ndp = [0] * n
        acc = list(accumulate(dp))
        if a == -1:
            free_count += 1
            for j in range(i, n):
                # i に j を置いて、最大値を更新する
                if not is_fixed[j]:
                    ndp[j] += acc[j - 1] * 2
                # 最大値はこれより前に置いた j のまま、それ未満の数を置く。自由度は i までの埋める箇所数 - j 以下の固定されてない要素数
                # i の位置を累積最大値 j にできるか判定。「j 以下で固定されてない要素数」より「埋める箇所数」の方が多ければ無理
                f = free_count - 1 - int(not is_fixed[j])
                g = j - acc_fixed[j - 1]
                if f < g:
                    ndp[j] += dp[j] * (g - f)
                ndp[j] %= MOD
        else:
            if a > 0:
                ndp[a] = acc[a - 1] * 2
                ndp[a] %= MOD
            for j in range(a + 1, n):
                ndp[j] = dp[j]
        dp = ndp
        # print(f'{i=} {a=} {dp=}')

    ans = dp[n - 1]
    return ans


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