No.3491 右結合的総乗
p-adic注意
この問題のメモリ制限は100[MB]です。
問題文
入力に非負整数 $N$ と $N+1$ 以下の正整数 $M$ と、$N$ 以下の非負整数のみからなる長さ $2N+1$ の整数列 $A$ と、$N$ 以下の非負整数のみからなる要素数 $M$ の集合 $S$ が与えられます。
集合 $T$ が最初は $S$ として与えられています。$T$ に以下の操作を $0$ 回以上の好きな回数繰り返すことで $T$ を更新した時の、最終的な $T$ の要素数の最大値を求めてください。
- $i \in S$ と $j \in T$ を選び、$T \cup \{A_{i+j}\}$ で $T$ を置き換える。
ただし $2N$ 以下の各非負整数 $k$ に対し、$A$ の $1+k$ 個目の成分を $A_k$ と書き表します。
背景
代数を知っている人向けに背景を説明します。$N$ 以下の非負整数全体の集合を $I_N$ と置き、$N$ 以下の各非負整数 $i,j$ に対し $i A j = A_{i+j}$ と定めることで $A$ を $I_N$ 上の $2$ 項演算とみなします。各正整数 $\ell$ と $N$ 以下の非負整数のみからなる長さ $\ell$ の各整数列 $(i_k)_{k=1}^{\ell}$ に対し、その $A$ に関する右結合的総乗 $A^{\prod} (i_k)_{k=1}^{\ell}$を次の再帰式で定めます：
$\displaystyle A^{\prod} (i_k)_{k=1}^{\ell} = \left\{ \begin{array}{ll} i_1 & (\ell = 1) \\ i_1 A (A^{\prod} (i_{k+1})_{k=1}^{\ell-1}) & (\ell > 1) \end{array} \right. $
要するに $A$ による右からの結合です。例えば $\ell = 3$ の時は $A^{\prod} (i_k)_{k=1}^{\ell} = i_1 A (i_2 A i_3)$ となります。ただし $A$ は単位的とは限らないのでモノイド演算に関する総乗のように $\ell = 0$ の場合へ定義を拡張しないこと、また $A$ は可換ですが結合的とは限らないので $A$ の結合順を変えたら総乗の値が変わりうることに注意しましょう。
$S$ の要素の $A$ に関する右結合的総乗全体の集合を $S'$ と置きます。この時 $S'$ は $T$ に何回か操作を行って得られ、かつ $T$ に $0$ 回以上の操作を行った時の最終的な $T$ は全て $S'$ の部分集合です。従ってこの問題は $S'$ の要素数を求める問題と等価です。
入力
$S$ の要素を $M$ 未満の各非負整数 $m$ で小さい順に番号づけて $s_m$ と書き表します。
この時、入力は以下の形式で標準入力から $3$ 行で与えられます：
- $1$ 行目に $N, M$ が半角空白区切りで与えられます。
- $2$ 行目に $2N$ 以下の各非負整数 $k$ に対する $A_k$ が $k$ の小さい順に半角空白区切りで与えられます。
- $3$ 行目に $M$ 未満の各非負整数 $m$ に対する $s_m$ が $m$ の小さい順に半角空白区切りで与えられます。
$N$ $M$
$A_0$ $\cdots$ $A_{2N}$
$s_0$ $\cdots$ $s_{M-1}$
制約
入力は以下の制約を満たします：
- $N$ は $0 \leq N \leq 4 \times 10^3$ を満たす整数である。
- $M$ は $1 \leq M \leq N+1$ を満たす整数である。
- $2N$ 以下の任意の非負整数 $k$ に対し、$A_k$ は $0 \leq A_k \leq N$ を満たす整数である。
- $M$ 未満の任意の非負整数 $m$ に対し、$s_m$ は $0 \leq s_m \leq N$ を満たす整数である。
- $M$ 未満の任意の非負整数 $m_0, m_1$ に対し、$m_0 < m_1$ ならば $s_{m_0} < s_{m_1}$ である。
出力
最終的な $T$ の要素数の最大値を $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
0 1 0 0
出力
1
$A = (A_0) = (0)$ かつ $S = \{0\}$ です。最初に $T = S = \{0\}$ と与えられています。
$T$ に $1$ 回目の操作を行います。$i \in S$ と $j \in T$ としては $(i,j) = (0,0)$ しか選べません。これを選んだ結果、$T$ が $T \cup \{A_{i+j}\} = \{0\} \cup \{0\} = \{0\}$ に置き換わります。つまり $T$ は変化しません。従って $0$ 回以上操作した後の $T$ は常に $\{0\}$ であり、その要素数は $1$ です。
代数を知っている人向けに言うと、$(I_N,A)$ は自明群です。
サンプル2
入力
1 1 0 1 0 1
出力
2
$A = (A_0,A_1,A_2) = (0,1,0)$ かつ $S = \{1\}$ です。最初に $T = S = \{1\}$ と与えられています。
$T$ に $1$ 回目の操作を行います。$i \in S$ と $j \in T$ としては $(i,j) = (1,1)$ しか選べません。これを選んだ結果、$T$ が $T \cup \{A_{i+j}\} = \{1\} \cup \{0\} = \{0,1\}$ に置き換わります。これは $N = 1$ 以下の非負整数全体の集合と等しいです。
各操作では $T$ が $N$ 以下の非負整数のみからなる $T$ を含む集合にしか置き換わらないため、$1$ 回以上操作した後の $T$ は常に $\{0,1\}$ であり、その要素数は $2$ です。
代数を知っている人向けに言うと、$(I_N,A)$ は法 $2$ の加法群と同型です。
サンプル3
入力
2 2 0 1 2 2 2 1 2
出力
2
$A = (A_0,A_1,A_2,A_3,A_4) = (0,1,2,2,2)$ かつ $S = \{1,2\}$ です。最初に $T = S = \{1,2\}$ と与えられています。
$T$ に $1$ 回目の操作を行います。$i \in S$ と $j \in T$ として $(i,j) = (1,1), (1,2), (2,1), (2,2)$ の $4$ 通りが選べます。このいずれを選んでも、$T$ が $T \cup \{A_{i+j}\} = \{1,2\} \cup \{2\} = \{1,2\}$ に置き換わります。つまり $T$ は変化しません。従って $1$ 回以上操作した後の $T$ は常に $\{1,2\}$ であり、その要素数は $2$ です。
代数を知っている人向けに言うと、$(I_N,A)$ は加法を上限 $2$ で打ち切った可換モノイドです。
サンプル4
入力
3 1 0 0 0 3 0 1 2 3
出力
4
$A = (A_0,A_1,A_2,A_3,A_4,A_5,A_6) = (0,0,0,3,0,1,2)$ かつ $S = \{3\}$ です。最初に $T = S = \{3\}$ と与えられています。
$T$ に $1$ 回目の操作を行います。$i \in S$ と $j \in T$ として $(i,j) = (3,3)$ しか選べません。これを選んだ結果、$T$ が $T \cup \{A_{3+3}\} = \{3\} \cup \{2\} = \{2,3\}$ に置き換わります。
$T$ に $2$ 回目の操作を行います。$i \in S$ と $j \in T$ として $(i,j) = (3,2), (3,3)$ の $2$ 通りが選べます。例えば $(i,j) = (3,2)$ を選んだとします。すると $T$ が $T \cup \{A_{3+2}\} = \{2,3\} \cup \{1\} = \{1,2,3\}$ に置き換わります。
$T$ に $3$ 回目の操作を行います。$i \in S$ と $j \in T$ として $(i,j) = (3,1), (3,2), (3,3)$ の $3$ 通りが選べます。例えば $(i,j) = (3,1)$ を選んだとします。すると $T$ が $T \cup \{A_{3+1}\} = \{1,2,3\} \cup \{0\} = \{0,1,2,3\}$ に置き換わります。これは $N = 3$ 以下の非負整数全体の集合と等しいです。
各操作では $T$ が $N$ 以下の非負整数のみからなる $T$ を含む集合にしか置き換わらないため、これ以降の $T$ は常に $\{0,1,2,3\}$ であり、その要素数は $4$ です。
代数を知っている人向けに言うと、$(I_N,A)$ は非単位的非結合的可換マグマです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。