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

n, s = input().split()
n = int(n)

dp = [[0] * 10005 for _ in range(10005)]
dp[0][0] = 1
i = 0
j = 0
ans = 0
for c in s:
    if c == 'A':
        i += 1
    elif c == 'T':
        i -= 1
    elif c == 'C':
        j += 1
    elif c == 'G':
        j -= 1
    ans += dp[i][j]
    dp[i][j] += 1

print(ans)

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

import sys
from functools import lru_cache


@lru_cache(maxsize=None)
def dfs(l):
    if l == 2 * n + 1:
        return True
    max_w = (n * 2 - l + 1) // 2
    for w in range(1, max_w + 1):
        for k in range(l, l + w):
            if floors[k] != -1 and not (floors[k] < 1000):
                break
            if floors[k + w] != -1 and not (1000 <= floors[k + w]):
                break
            if floors[k] != -1 and floors[k + w] != -1 and (floors[k] != floors[k + w] - 1000):
                break
        else:
            if dfs(l + 2 * w):
                return True
    return False


n = int(input())
floors = [-1] * (2 * n + 1)
for i in range(n):
    a, b = map(int, input().split())
    if a != -1 and b != -1 and a >= b:
        print('No')
        exit()
    if a != -1:
        if floors[a] != -1:
            print('No')
            exit()
        floors[a] = i
    if b != -1:
        if floors[b] != -1:
            print('No')
            exit()
        floors[b] = i + 1000

print('Yes' if dfs(1) else 'No')

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を求めようとすると、これが一筋縄ではいかないことに気付く。

というのも、$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

import os
import sys

import numpy as np


def solve(inp):
    n, k, m = inp
    max_sum = n * n * k + 10
    dp = np.zeros((n + 1, max_sum), np.int64)
    dp[0, 0] = 1
    max_len = np.zeros(n + 1, np.int64)
    max_len[0] = 1
    serial_sum = 0
    for i in range(1, n + 1):
        serial_sum += i
        max_len[i] = serial_sum * k + 1
        for j in range(max_len[i]):
            tmp = dp[i - 1, j]
            if j >= i:
                tmp += dp[i, j - i]
            if j >= i * (k + 1):
                tmp -= dp[i - 1, j - i * (k + 1)]
            dp[i, j] = tmp % m

    ans = np.zeros(n, np.int64)
    for i in range((n + 1) // 2):
        j = n - 1 - i
        l = min(max_len[i], max_len[j])
        tmp = (dp[i, :l] * dp[j, :l] % m).sum() % m
        ans[i] = ans[n - i - 1] = (tmp * (k + 1) - 1) % m

    return ans


np.set_printoptions(edgeitems=100)
np.core.arrayprint._line_width = 500

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

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の求め方

大小関係の配列の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$ を数える。

冗長なDP

$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}$ と、二項係数一発で求められる。

縮約したDP

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

$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

import sys
from itertools import product, permutations

MOD = 10 ** 9 + 7


def inv(x):
    return pow(x, MOD - 2, MOD)


inv2 = inv(2)
inv6 = inv(6)
inv24 = inv(24)
inv120 = inv(120)
inv720 = inv(720)

repsum = [
    lambda x: x,
    lambda x: x * (x + 1) * inv2 % MOD,
    lambda x: x * (x + 1) * (x + 2) * inv6 % MOD,
    lambda x: x * (x + 1) * (x + 2) * (x + 3) * inv24 % MOD,
    lambda x: x * (x + 1) * (x + 2) * (x + 3) * (x + 4) * inv120 % MOD,
    lambda x: x * (x + 1) * (x + 2) * (x + 3) * (x + 4) * (x + 5) * inv720 % MOD,
]


def lis(aaa):
    dp = [-1]
    for a in aaa:
        if dp[-1] < a:
            dp.append(a)
        else:
            for i, b in enumerate(dp):
                if a <= b:
                    dp[i] = a
                    break
    return len(dp) - 1


def count_patterns(aaa, order, k):
    d = [1000000007] * k
    for i, o in enumerate(order):
        d[o] = min(d[o], aaa[i] - o)
    segments = [0] + sorted(set(d))
    dp = [[0, 0, []] for _ in segments]  # [区間合計値, 区間末尾値, [r次累積和, r-1次累積和, ..., 0次累積和 のbase]]
    dp[0][1] = 1
    for a in d:
        for i in range(1, len(segments)):
            t = segments[i]
            if a < t:
                dp[i][0] = 0
                dp[i][1] = 0
                dp[i][2].clear()
            else:
                s = segments[i - 1]
                l = t - s
                dp[i][1] = (dp[i - 1][1] + dp[i][0]) % MOD
                dp[i][2].append(dp[i - 1][1])
                if i == 1:
                    dp[0][1] = 0
                tmp = 0
                w = len(dp[i][2])
                for j, x in enumerate(dp[i][2]):
                    tmp = (tmp + repsum[w - j - 1](l) * x) % MOD
                dp[i][0] = tmp
    return sum(dpi[0] for dpi in dp[1:])


n, *aaa = map(int, sys.stdin.buffer.read().split())
ans = 0

for k in range(1, n):
    for order in product(range(k), repeat=n):
        if len(set(order)) != k:
            continue
        this_lis = lis(order)
        this_pat = count_patterns(aaa, order, k)
        ans = (ans + this_lis * this_pat) % MOD

for order in permutations(range(n)):
    this_lis = lis(order)
    this_pat = count_patterns(aaa, order, n)
    ans = (ans + this_lis * this_pat) % MOD

for a in aaa:
    ans = ans * inv(a) % MOD

print(ans)

F - Visibility Sequence

問題

例

解法

¹⁾

枝刈りして高速な言語なら通るらしい?

目次

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

B - DNA Sequence

問題

解法

C - Fair Elevator

問題

解法

D - Multiset Mean

問題

例

解法

方針

DPの求め方

E - Random LIS

問題

解法

大小関係の列挙方法

LISの求め方

パターン数の求め方

冗長なDP

縮約したDP

F - Visibility Sequence

問題

例

解法