AtCoder Beginner Contest 252 G,Ex問題メモ

AtCoder Beginner Contest 252

G - Pre-Order

• $1～N$ の順列 $P=(P_1,P_2,...,P_N)$ が与えられる
• $N$ 頂点の根付き木のうち、以下の条件を満たすものの個数を $\mod{998244353}$ で求めよ
  • 各頂点に $1～N$ の番号がついていて、根は頂点 $1$
  • 根からDFSで訪れた頂点番号を行きがけ順に記録すると $P$ になる
  • 1つのノードが複数の子を持つ場合は、必ず頂点番号が小さい順に訪れる
• $2 \le N \le 500$
• $P_1=1$

※行きがけ順: はじめて訪れたときに1回だけ記録する

区間DP。

• $DP1[l][r]=P_l,P_{l+1},...,P_{r-1}$ の $[l,r)$ の区間で同じことを考えて、1つの部分木は何通りあるか？
• $DP2[l][r]=P_l,P_{l+1},...,P_{r-1}$ の $[l,r)$ の区間で、木が複数本あってもよい場合は何通りあるか？

P[l,r) = (5 3 7 2 4 8)

DP1での管理対象例:

  5          5
 / \        / \
3   7      3   4
   /|\     |   |
  2 4 8    7   8
           |
           2

DP2での管理対象例: 上記に加え、

  5  7        ←ただし根は番号昇順に並んでいること
  |  |
  3  2
    / \
   4   8

$P$ の添字を $P_0,P_1,...,P_{N-1}$ に置き換えて考えるとして、$DP1[0][N]$ が答えとなる。

$DP1[l][r],DP2[l][r]$ を考えるとき、それより短い区間は全て計算済みとして、遷移は

• $P_l$ を根とした1つの木を作る場合:
  • $[l+1,r)$ からできる複数の木を、$P_l$ 直下にまるっとくっつける
  • $DP1[l][r]=DP2[l+1][r]$
• 複数の木からなる森を作る場合:
  • 最初の木がどこまで続くか $k$ を全探索
  • $[l,k)$ まで1つの木、$[k,r)$ は複数の木
  • $P_l \lt P_k$ という条件ときのみ、そこで区切ってくっつけられる
  • $\displaystyle DP2[l][r]=\sum_{k=l+1}^{r-1}DP1[l][k] \times DP2[k][r] \ if \ P_l \lt P_k$

これで区間が短い方から計算していける。
初期値は、各 $i=0,...,N-1$ につき $DP1[i][i+1]=DP2[i][i+1]=1$ としておけばよい。

で、このまま解いても別にいいのだが、上記の遷移からもわかるとおり、$DP1[l][r]$ は $DP2[l+1][r]$ と同じとなる。
従って、実際に管理するのは $DP2$ のみでよく、$DP2[1][N]$ が答えとなる。

Python3

Ex - K-th beautiful Necklace

• $N$ 個の宝石、色は $C$ 種類
  • 宝石 $i$ の色は $D_i$、価値は $V_i$
  • どの色の宝石も、少なくとも1個は存在する
• 各色から宝石を1つずつ選ぶ
  • 選んだ $C$ 個の宝石の $V_i$ の総XORを、その選び方の「美しさ」とする
• $K$ 番目に美しい選び方をした時の美しさを求めよ（最も美しいのが1番目）
  • 同じ美しさでも、選び方が異なれば別に数える
• $1 \le C \le N \le 70$
• $0 \le V_i \le 2^{60}$
• $1 \le K \le 10^{18}$

計算量解析と、半分全列挙。

$N=70$ という、十分小さいが愚直には大きすぎる中途半端な制約。

もし選び方を全探索するとすると、色が $1,2,...$ である宝石の個数を $L_1,L_2,...$ として、 選び方の個数はこれらの総積となる。

しかし、$L_i$ の総和の上限が70である。
最大でもそこまで大きくならないのでは？ ということで、上限を考える。

和が一定の場合の総積は、でかい値が1個あるよりは、2とか3とかがいっぱいあった方が、明らかにでかくなる。

具体的には、

• $1$ は総積を増やすのに全く寄与しないため、無い方がよい
• $L_i \ge 4$ のとき、$2$ と $L_i-2$ に分割した方がでかくなる（小さくならない）
• $2$ が3個と $3$ が2個では、$3$ が2個の方が積がでかくなる
• よって、$L_i$ の総和が一定の時、一番総積がでかくなるのは、$3$ がなるべくいっぱいあるとき

ということになる。
1とか2とかでなく、3という値に意味があるのって、なんか珍しい気がする。
（なお、整数でなく実数で、総和が一定の上で総積を最大化させるのは、ネイピア数 $e$ をたくさん作るのがいいらしい。参考）

よって、全探索の上限は $2^2 3^{22}=1.25 \times 10^{11}$ となる。

もちろん、これはまだ多すぎるが、半分こすれば $3.5 \times 10^5$ と、十分可能な量となる。
綺麗に半分こできるとは限らないが、そんなに大きくならないことが期待できる。

半分全列挙の考え方を用いて、 互いに同程度となるように色を2グループに振り分け、各グループだけで作れるXORを全て計算しておく。

2つの、要素数 $3.5 \times 10^5$ くらいの多重集合ができた。（グループA,Bとする）
あとは、互いから1つずつ取り出してXORして作れる値から、$K$ 番目に大きいものを求めればよい。
だが、この方法もなかなか難しい。

TLEとなるが、基本的な考え方をまず示す。

両グループの値をそれぞれBinary Trieに登録する。
各ノードに「自身の部分木に含まれる要素数」を持たせておく。

A: (0101, 0111, 1101, 1111)    B: (0001, 0100, 1110)

      ④                   ③
   0／  ＼1             0／  ＼1
  ②      ②           ②      ①
   \1      \1        0/  \1     \1
   ②      ②        ①  ①     ①
  0/\1    0/\1     0/   0/       \1
 ①  ①  ①  ①    ①   ①       ①
  \1  \1  \1  \1    \1 0/       0/
  ①  ①  ①  ①    ① ①       ①

答えを二分探索する。
「XORの結果、$X$ より大きい値はいくつあるか？」は、1回につき、2つのTrieの小さい方のノード数程度で抑えられる。

$f($ A側で着目中のノード $a$, B側で着目中のノード $b$, 着目中のbit $d$, 境界値 $X)$ として、 $a,b$ の各ノード以下に登録された値同士のXORで $X$ 以上になるものの個数を返す関数を考える。

$d$ は大きい方から考えるとして、$X$ で $d$ が立っているなら、、、

• 以下の2つの部分木の組では、XORで $d$ bit目が0になり $X$ 以上にならない
  • $a$ の0の方の部分木と、$b$ の0の方の部分木
  • $a$ の1の方の部分木と、$b$ の1の方の部分木
• 以下の2つの部分木の組で、再帰的に求める
  • $f(aの0の方の部分木, bの1の方の部分木, d>>1, X)$
  • $f(aの1の方の部分木, bの0の方の部分木, d>>1, X)$

$X$ で $d$ が立っていないなら、、、

• 以下の2つの部分木の組では、XORで $d$ bit目が1になり必ず $X$ 以上になるため、即座に答えに加算してよい
  • $a$ の0の方の部分木と、$b$ の1の方の部分木
  • $a$ の1の方の部分木と、$b$ の0の方の部分木
• 以下の2つの部分木の組で、再帰的に求める
  • $f(aの0の方の部分木, bの0の方の部分木, d>>1, X)$
  • $f(aの1の方の部分木, bの1の方の部分木, d>>1, X)$

これで $f($ AのTrieの根, BのTrieの根, 1«59, X)$ とすると、全体での答えが求められる。

$X$ を二分探索し、「$X$ 以上になるXORが $K$ 個以上になる、最も小さい値」が答えとなる。

計算量は、まずBinaryTrieへの登録が、$O(3^{\frac{N}{6}}) \propto 3.5 \times 10^5$ 個の値で $O(\log{V_{max}}) \propto 60$ 個のノードを作るので、だいたい $10^7$ に数倍をかけたくらい。

次に二分探索が、最悪の場合は全ノードが探索されうるので、1回あたり $O(3^{\frac{N}{6}}\log{V_{max}})$ なので、 答えまで行き着くには $O(3^{\frac{N}{6}}\log{V_{max}}\log{K})$ で、$10^8～10^{10}$ くらいとなり、ちょっと厳しい。

まぁ、実際にほぼ全ノードが探索されうるような $X$ はあったとしても限られるので、 全ての二分探索の試行がここまでかかるわけではないが、実際にTLEだった。

logを1つにする方法もある（公式Editorial参照）が、小手先の高速化を試みる。

結構、BinaryTrieの構築の時点で、それなりの計算量がかかっている。
最初にグループA,Bの全ての値をTrieに登録しきってしまうことはせず、遅延させることを考える。

ノードに個数で無く、値の多重集合自体を持たせておき、二分探索で必要とされたときに初めて（まだ作ってなければ）子を作る。

二分探索開始前のグループAのTrieは、根にグループAの多重集合だけ持った状態

      (0101,0111,1101,1111)  ←根

二分探索で仮に $X=0110$ などが試されたとして、$f(a,b,d,X)$ による再帰で次の $a,b$ として必要になる箇所だけ、作られてなければその時に作る。

      (0101,0111,1101,1111)
         0／           ＼1
    (0101, 0111)   (1101, 1111)
          \1
       (0101,0111)
        0/      \1
     (0101,)   (0111,)
                  \1
                 (0111,)

$f(a,b,d,X)$ は、$a,b$ セットで再帰していくので、Bの側のTrieに次の $b$ に該当するノードが存在しなかったりした場合は、 $a$ の側でそれ以下を作っていることが無駄だったりする（$X$ が変わったら改めて必要になることはありえるが）ので、 この無駄を省くことで一定の高速化になる。

また、$d$ が深く（下の桁に）なるにつれ、そのノード以下にある値の個数は少なくなり、 よほど人為的に作らない限りは $60$ bit目まで降りなくても早々に1などになる。

$f(a,b,d,X)$ を求めるとき、$|a| \times |b|$ が100～1000など、 全探索できる程度に十分に小さければ、その時点で全探索して、再帰せず直接求めてしまえばよい。

このような高速化を図ることで、2秒ギリギリではあるが、通る。

Python3