目次
AtCoder Regular Contest 187 A,B,C問題メモ
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$ は行かないでしょ、で投げると通る。
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 のいずれでも数えられてしまう。
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)$ で求められる。