AtCoder Regular Contest 104 B,C,D,E問題メモ

AtCoder Regular Contest 104

めっちゃ久々のARC。

B - DNA Sequence

• 長さ $N$ の、ATCGのいずれかの文字からなる文字列 $S$ が与えられる
• $S$ の連続する部分文字列のうち、以下の条件を満たすものの個数を求めよ
  • 部分文字列 $T_1$ とすると、好きに並べ替えることによって以下の条件を満たす $T_2$ が作れる
  • 全ての $i=1～|T_1|$ において、
    • $T_1$ の $i$ 文字目が 'A' なら $T_2$ の $i$ 文字目は 'T'
    • $T_1$ の $i$ 文字目が 'T' なら $T_2$ の $i$ 文字目は 'A'
    • $T_1$ の $i$ 文字目が 'C' なら $T_2$ の $i$ 文字目は 'G'
    • $T_1$ の $i$ 文字目が 'G' なら $T_2$ の $i$ 文字目は 'C'
• $1 \le N \le 5000$

要は、「'A'と'T'、'C'と'G'をそれぞれ同数ずつ含む部分文字列」を数えればよい。

2つの要素が絡むとややこしいので、たとえばAとTしかないと単純化する。

$X_i$ を「$S$ を先頭から $i$ 文字目まで見て余っているAの個数」とする。不足分は負で表す。

$X_0=0$ で初期化し、Aが現れたら+1、Tが現れたら-1として更新していく。

   A T A A T T T  T
X 0 1 0 1 2 1 0 -1 -2

すると、「$X_i=X_j$ である」＝「$S_{i+1}～S_j$ はAとTを同数ずつ含む」となる。この $(i,j)$ のペアの個数を数えればよい。

これは、以下のような $Y$ を作っておいて、順番に $X_i$ を求めていく中で更新していけばよい。

• $Y[j]=$ これまでに $X_i=j$ となった回数

$i$ について $X_i$ を更新したら、その時の $Y[X_i]$ の値が「$(?,i)$ となるようなペアの個数」となるので、答えに加算する。
その後、$Y[X_i]$ に+1して更新する。

         Y
    X     -2  -1  0  1  2     ペア
始  0             1
A   1             1  1
T   0             2  1          1
A   1             2  2          1
A   2             2  2  1
T   1             2  3  1       2
T   0             3  3  1       2
T  -1          1  3  3  1
T  -2      1   1  3  3  1  _______
                           Ans. 6

今回の問題では、これを2次元で行えばよい。

計算量は、イテレートする部分は $O(N)$ なのだが、$Y$ の二次元配列を確保するところで $O(N^2)$ かかる。

Python3

C - Fair Elevator

• エレベーターが1階から $2N$ 階まで、1回だけ移動した
• その間、$N$ 人の人が乗り降りした
  • $2N$ 個のフロア全てで、乗りまたは降りが1回ずつ発生した
  • エレベーターに同時に乗っていた瞬間がある人達は、移動した階（降りた階-乗った階-1）が全て同じだった
• $N$ 人の人の乗降記録がある
  • $i$ 番目の人は $A_i$ 階で乗り、$B_i$ 階で降りた
  • ただし、$A_i=-1$ や $B_i=-1$ の時は、記録が無いことを表す
• 乗降記録が、上記の説明と矛盾しないか判定せよ
• $1 \le N \le 100$

丁寧な条件分岐をしての全探索。

まず、互いに-1でないのに $A_i \ge B_i$ だったり、$A_i,B_i$ の間で重複があったらアウト。

以下、そうで無いとする。「移動した階が全て同じ」という条件を考える。

仮に、ある人が1→5階へ移動したとする。2,3,4階で他の人の乗り降りが発生している。

ここで、他の人は同様に4階層移動しなければならないので、「降りた」ことはあり得ない（地下から乗ったことになってしまう）。

1  2  3  4  5  6  7  8  9 10
|---------->|
   |---------->|
      |---------->|
         |---------->|

結局、このようになるしか無い。

すると $1～8$ 階は全て埋まったため、この間ではこれ以上乗りも降りも発生しない。次は、9階が先ほどの1階と同じようにして、議論が進められる。

つまり、正しい乗降記録はある連続した偶数長の区間 $[i,i+2w)$ に分けられて、各区間で $[i,i+w)$ は全て乗り、$[i+w,i+2w)$ は全て降り、となるしかない。

この偶数長の区間を、「グループ」とする。
グループの分け方について全探索し、与えられた乗降記録と矛盾しないものがあるか調べる。
左から順番に仮確定し、残りを矛盾無く確定できるか調べていく。

関数 $f(L)$ を「$L～2N$ を矛盾無くグループ分けできるか？」とする。以下のように調べればよい。

• $L$ から $2w$ の長さのグループを作るとする
• 各 $w=1～(L+2wが2Nを越えないギリギリ)$ について
  • 各 $k=0～w-1$ について、
    • 以下の条件のいずれかに当てはまれば、$L$ からの長さ $2w$ のグループは不可能
      • $L+k$ 階で降りた人が乗降記録にある
      • $L+k+w$ 階で乗った人が乗降記録にある
      • $L+k$ 階で乗った人と $L+k+w$ 階で降りた人が乗降記録上で異なる
  • もし長さ $2w$ のグループが可能なら、仮確定し、$f(L+2w)$ へ進む
• $L=2N+1$ まで到達したら成功

$f(L)$ は $1～L-1$ の分け方に関わらないので、メモ化で高速化できる。

これ、嘘解法ですね……。同じ人が2回乗っても許されちゃう。

2
1 4
-1 -1

Noが正しいが、Yesになる

「$L+k$ 階で乗った人が指定されていて、さらにその人の降りた階も指定されている場合、$L+k+w$ がその階で無ければ不可能」という判定も必要。

Python3

D - Multiset Mean

• 正整数 $N,K,M$ が与えられる
• $x=1～N$ のそれぞれについて、以下を求めよ
  • $1～N$ の整数をそれぞれ $0$ 個以上 $K$ 個以下含む、空で無い多重集合であって、平均が $x$ であるものの個数を $M$ で割った余り
• $1 \le N,K \le 100$
• $10^8 \le M \le 10^9+9$
• $M$ は素数

$N=5,K=3$ で $x=4$ について求める場合、1～5を上限3個まで含む、平均が4の集合の個数。

{4}, {3,5}, {1,5,5,5} などが該当し、全部で27個存在する。

DPなんだけど、上手な高速化が必要となる。

たとえば $N=8$ で $x=4$ について求めたいとすると、全体から $4$ を引いて考え、平均を0にすると考えるとやりやすい。

 1  2  3    4    5  6  7  8
           ↓
-3 -2 -1    0    1  2  3  4

すると、以下のような値を事前計算しておくと、

• $DP[i][j]=1～i$ をそれぞれ上限 $K$ 個まで含む多重集合で、総和が $j$ となるものの個数

平均が0となるには、$0$ より左（$-1～-3$）の総和と、$0$ より右（$1～4$）の総和が打ち消し合ってくれればよいので、以下のように求められる。

• $\displaystyle \sum_{j=0}{(DP[3][j] \times DP[4][j])}$

さらに $0$ 自身も $0～K$ 個含んでいてよいので $K+1$ 倍、ただし空集合が含まれるのでそれは除き、最終的に以下が答えとなる。

• $\displaystyle \sum_{j=0}{(DP[3][j] \times DP[4][j])} \times (K+1)-1$

いざDPを求めようとすると、これが一筋縄ではいかないことに気付く。

というのも、$DP[i][j]$ において $i,j$ の範囲は以下のようになる。

• $i$: $x=1$ の時などが最小と最大を同時に必要とし、$0 \le i \le N-1$
• $j$: 和の最大値は、$i$ が最大値 $N-1$ の時、$(1+2+...+N-1) \times K = \dfrac{N(N-1)}{2}K$

つまり、$DP$ の必要とする空間サイズは $O(N^3K)$ となる。

そして、この更新は、愚直にやろうとすると骨子は以下のようになる。（添字が範囲外になる場合などは適宜除外する）

DP[0][0] = 1

for i in range(1, N):
    for j in range(0, N*(N-1)*K//2+1):
        for t in range(0, K):
            DP[i][j] += DP[i-1][j-i*t]

これは全体で $O(N^3K^2)$ のループとなり、枝刈りなどをしてもさすがにTLE。¹⁾

AtCoder-Libraryのconvolutionでも使うのかな？ と思ったが、それでも $O(N^3K \log{N^2K})$ であり、効果は薄い。 また、任意MODでのconvolutionは逆元を求めるフェイズで $M$ の値によって多少の時間がかかってしまう場合があり、 わざわざ問題設定で $M$ を任意にしているということは「convolutionじゃないぞ」というメッセージのような気がする。

解説を見ると、以下のような方法を用いて高速化している（難しいことはしていないのだが）。

• $j$ について順に処理するとき、$i$ 個周期で参照する箇所の多くが被ることになるので、その情報を上手く使う

具体的には、以下のようになる。

※DP[i-1] を単にDP1と表記する

DP[i][j]   = DP1[j] + DP1[j-i] + DP1[j-2i] + ... + DP1[j-Ki]
DP[i][j-i] =          DP1[j-i] + DP1[i-2i] + ... + DP1[j-Ki] + DP1[j-(K+1)i]

この差分だけを足し引きすればよい。

これで、$DP$ の構築が $O(N^3K)$ で収まる。

Python3

E - Random LIS

• 整数列 $A_1,A_2,...,A_N$ が与えられる
• ここから長さ $N$ の整数列 $X$ を作る
  • 各 $i=1～N$ に対して、$X_i$ は独立に $1～A_i$ の中から一様ランダムで選ばれる
• この $X$ の最長増加部分列（狭義単調増加）の長さの期待値を求めよ
• $1 \le N \le 6$
• $1 \le A_i \le 10^9$

制約が独特。

分数は考えるのが面倒なので、「全ての作り得る $X$ に対してLISの総和」を求めて、後から作り得る $X$ の個数で割ることにする。 作り得る $X$ の個数は単純に $A_1 \times A_2 \times ... \times A_N$ である。

通常のLISは、「$DP[i][j]=$ $A_1～A_i$ だけで長さ $j$ のLISを作るのに必要な最小の末尾要素」として前から順に更新すると解ける。

• 最長増加部分列・最長共通部分列

これを拡張して、試しに以下にしてみたらどうだろうか、と考えたが、

• $DP[i][j][k]=$ $A_1～A_i$ だけで長さ $j$ のLISを作るのに必要な最小の末尾要素が $k$ になる個数

これは最終的にDPを埋められたとしても、結局、ある $j$ が最終的なLISの長さとしてあり得るのか、途中経過にのみ出現するのか、区別することができない。

想定解は、$N \le 6$ という制約を利用して、$X$ における $N$ 個の数の大小関係を全て網羅してしまえばよいらしい。

たとえば、$N=4$ なら $(2,0,0,1)$ は、$X_2=X_3 \lt X_4 \lt X_1$ となるような $X$ を示す。

大小関係さえ分かれば、それに対する「LISの値」と「パターン数」をそれぞれ個別に求められるので、漏れなく全パターンの総和を求めることが可能となる。

大小関係 $D$ を、$(2,0,0,1)$ のように $0～k-1$ からなる重複ありの長さ $N$ の数列で表現するとする。

全探索するにあたり、$N^N$ 通りを調べてもよいが、たとえば $(2,0,0,1)$ や $(3,0,0,2)$ や $(3,1,1,2)$ は全て同じ関係なので、これらを重複して数えないようにしなければならない。

先に何通りの値が出てくるか $k=1～N-1$ を決めてしまって、$k^N$ 通りの数列を全て調べる。この内、使われている値の種類が $k$ に満たないものは除外すると、重複無く数えられる。

$k=N$ の時は順列を全列挙すればよいので、上記の方法は $k=N-1$ まででよい。

使われている値の種類を調べるのにも $N$ かかるとして、列挙にかかる計算量は $N(1^N+2^N+...+(N-1)^N)+N!$ に比例し、$N=6$ でも123810程度である。

また、実際にこの中で有効なのは、順序付きベル数と呼ばれるらしく、4683個しか無いらしい。

• Ordered_Bell_number

もっと上手な列挙の仕方はありそうな気がする。他の人のコードを読もう。

大小関係の配列のLISをそのまま求めればよい。

要は、$D=(2,0,0,1)$ のような大小関係の列が固定されたとき、$(15, 3, 3, 8)$ のような具体的な数字の当てはめ方を数えたい。
$0,1,2$ に相当する数がそれぞれ上限いくつまでを使えるのかを整理する。$A$ の対応する位置の最小値を見ればよい。

• $S_i=D$ 上で $i$ に対応する数が、上限いくつまで使用可能か

$A=(9,18,12,5)$ の場合、$0$ に対応する数は、対応する位置の $A_i$ が $18,12$ なので小さい方の $12$ が上限となる。
例の場合、$S=(12,5,9)$ となる。

各 $i$ について $1 \le T_i \le S_i$ かつ狭義単調増加となるような、各整数の割り当て方 $T$ を数える。

$A_i \le 10^9$ と大きいので、$A_i$ の値をそのまま添字にしたDPは使えないが、まずはそれが可能として考える。

• $DP[i][j]=S$ を $i$ 番目まで考慮して、$T_i=j$ である割り当て方のパターン数

すると、遷移は以下のようになる。

• $\displaystyle DP[i][j]=\sum_{k=1}^{j-1}DP[i-1][k]$（$j \le S_i$ の時）
• $DP[i][j]=0$（$j \gt S_i$ の時）

S   (0)  1   2   3   4   5   6   7   8   9  10  11  12
始   1   0   0   0   0   0   0   0   0   0   0   0   0
12   -   1   1   1   1   1   1   1   1   1   1   1   1
5    -   0   1   2   3   4   0   0   0   0   0   0   0
9    -   0   0   1   3   6  10  10  10  10   0   0   0  → パターン数はこの総和 50 通り

毎回 $S_i$ を超えた範囲は0になるという特徴があるが、基本は累積和をとる更新となる。

累積和を開始する地点が、$i$ ごとに1個ずつ後ろにずれていってしまうのが面倒くさい。
ここは「$T_i \le T_{i+1}$（広義単調増加）も許す」とすれば、常に累積和を1から開始できる。

$S'_i=S_i-i$ として新たに $S'=(12,4,7)$ とする。これがシフト後の $T_i$ の上限となる。

    →j
S'  (0)  1   2   3   4   5   6   7   8   9  10  11  12
始   1   0   0   0   0   0   0   0   0   0   0   0   0
12   -   1   1   1   1   1   1   1   1   1   1   1   1
4    -   1   2   3   4   0   0   0   0   0   0   0   0   ←1個左シフト
7    -   1   3   6  10  10  10  10   0   0   0   0   0   ←2個左シフト

ところで、このように繰り返し累積和が取られるような更新は、まとめて計算する方法がある。

$j \gt S'_i$ で0となってしまうのが不連続的だが、それが発生しない範囲では、$i$ が進む毎に繰り返し累積和が取られるので、

    →j
i  (0)  1   2   3   4   5   6   7   8   ...
0   1   0   0   0   0   0   0   0   0   ...
1   -   1   1   1   1   1   1   1   1   ...
2   -   1   2   3   4   5   6   7   8   ...
3   -   1   3   6  10  15  21  28  36   ...
4   -   1   4  10  20  35  56  84 120   ...

これは、斜めに見ると、二項係数が並ぶパスカルの三角形が現れる。

    1     上の表は、横列を↘方向に見ている感じ
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

従って、0になる更新が発生しない範囲では、$DP[i][j]$ の値は ${}_{i+j}C_{j}$、さらに $DP[i][1]～DP[i][j]$ の総和は ${}_{i+j+1}C_{j}$ と、二項係数一発で求められる。

さて、遷移がわかったところで、添字がでかすぎる問題に対処する。

$S'$ に出現する値で区切ることによって、各区間について、値を1個1個保持せずとも全体を上手く計算できないか考えてみる。この場合、区間数はたかだか6箇所となる。

(0, 4]   (4, 7]    (7, 12]
1 2 3 4 | 5 6 7 | 8 9 10 11 12

• $DP'[i][s]=i$ 番目まで考慮して、$s$ 番目の区間の○○（パターン数を上手く計算するために保持する何か）

$(4,7]$ のように、「自分たちは0のまま、自分より下の区間で累積和が更新されており、いざ累積和を求める遷移が発生した際、なんか中途半端な値で開始される」というような区間が、どのように立式すればいいのか一見わかりづらい。

    →j
S'  (0)  1   2   3   4  |  5   6   7  |  8   9  10  11  12
始   1   0   0   0   0  |  0   0   0  |  0   0   0   0   0
12   -   1   1   1   1  |  1   1   1  |  1   1   1   1   1
4    -   1   2   3   4  |  0   0   0  |  0   0   0   0   0
7    -   1   3   6  10  | 10  10  10  |  0   0   0   0   0
12   -   1   4  10  20  | 30  40  50  | 50  50  50  50  50
                          ~~~~~~~~~~
                          ↑どう全体をまとめて表現する？

DPの更新はすぐ左と上の足し算と言い換えられることを考えると、以下のように、前の区間の末尾の値が大きく関係してくることがわかる。

前区間末尾 | 区間
           |   0      0       0        0     ...
         x |   x      x       x        x     ...
         y |  x+y   2x+y    3x+y     4x+y    ...
         z | x+y+z 3x+2y+z 6x+3y+z 10x+4y+z  ...

これを例えば $x$ の係数についてのみ追いかけると、先ほどの二項係数の値がそのまま出てきている。
また、$y,z$ も、$x$ をそれぞれ追従する形で同じ係数が出てくる。

一度、区間全体が0になったら、$x,y,z$ はそれ以降に伝播しないので、情報は捨ててしまってよい。

従って、連続して区間の累積和を取る更新がかけられ続ける限り、$i$ 個前の前区間末尾の値 $x$ は、

• 区間内の $j$ 番目(0-index)の値に対し、${}_{i+j}C_{j}x$ だけ寄与する
• 区間長を $L$ とすると、区間全体に $x$ は ${}_{L+i+1}C_{L}x$ だけ寄与する

「その区間に連続して累積和を取る更新がかけられ続けている間、0個前、1個前、…の前区間の末尾が何であったか」という情報さえ覚えておけば良いことがわかる。

実際は同じ計算を省略する目的などで、以下の3つの値をDPに持たせた。

• 「その区間内の合計、その区間末尾の値、現在有効な0個前,1個前,…の前区間の末尾の値リスト」

計算量は、順序付きベル数を $F_N$ として、

• 列挙が $O(N^N)$ 未満
• その中で有効なもの（$F_N$ 個）に対して
  • LISは $O(N \log{N})$
  • パターン数の数え上げは $O(N^2)$

全体で $O(N^N+F_NN^2)$ 未満となり、十分間に合う。

Python3

F - Visibility Sequence