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$ は行かないでしょ、で投げると通る。

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

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

programming_algorithm/contest_history/atcoder/2024/1117_arc187.txt · 最終更新: 2024/11/22 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0