−目次

AtCoder Regular Contest 187 A,B,C問題メモ
- A - Add and Swap
  - 問題文
  - 制約
  - 解法
- B - Sum of CC
  - 問題文
  - 制約
  - 解法
- C - 1 Loop Bubble Sort
  - 問題文
  - 制約
  - 解法

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

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$ が連結、両者同士は非連結、みたいになることはない）

ある境界位置 $i$ と境界値 $p$ について、「 $i$ 以前の $A_j$ が全て $p$ 以上」かつ「 $i+1$ 以降の $A_j$ が全て $p$ 未満」の場合、そこで非連結となる。

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

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

$B$ の（-1 は除き、固定された値のみでの）前からの累積最小値を $P_i$ 、後ろからの累積最大値を $Q_i$ とする。
$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 は、「ちょうど」となる割り当て方をしないと、重複が発生する。

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

Python3

（よく考えたら特に必要ないが）DPで実装している。

$\mathrm{DP}[i,j]:=i$ までの -1 の埋め方で、前半最小値が $j$ となるものの個数

境界決めたら前半・後半の “-1” の個数だけで計算できると気付いたのは後になってからだった。

        
          
          
              
              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$ にタッチ交代して、これは最大値なので末尾まで運ばれる。
運ばれなかった要素は、全て1ずつ左にシフトする。

という流れになっている。
上記の流れを、「 $(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}$ を計算し、総和を求めよ

DP

以下のDPで “-1” の埋め方を先頭から決めていきたくなるが、これだと状態数だけで $O(N^3)$ となる。

$\mathrm{DP_{TLE}}[i,j,k]:=P'_i$ まで決めて、暫定累積最大値が $j$ で、最大値の更新回数が $k$ となるような順列の個数
- $j$ は、新たに置く数が累積最大値を更新するかの場合分けに必須。
- 最後に、 $k$ ごとに $2^{k-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)

            

        
      