AtCoder Regular Contest 199 (Div. 1) A,B,C問題メモ

AtCoder Regular Contest 199 (Div. 1)

A - Flip Row or Col 2

問題文

$N\times N$ 行列 $A=(A_{i,j})\ (1\leq i,j\leq N)$ および長さ $N$ の整数列 $R=(R_1,R_2,\ldots,R_N), C=(C_1,C_2,\ldots,C_N)$ が与えられます． $A$ の各要素は $0$ または $1$ であり，$R,C$ の各要素は $0$ 以上 $\frac{N}{4}$ 未満です．
あなたは好きな行・列を選んで、その行・列全体をフリップする（0と1を置き換える）ことができます。
フリップする行と列をうまく選ぶことで操作後の $A$ が以下の条件を満たすことが可能かどうか判定してください。
- 各 $i=1,2,\ldots,N$ に対して，$A$ の $i$ 行目の要素の総和 $\displaystyle \sum_{j=1}^N A_{i,j}$ は $R_i$ である．
- 各 $j=1,2,\ldots,N$ に対して，$A$ の $j$ 列目の要素の総和 $\displaystyle \sum_{i=1}^N A_{i,j}$ は $C_j$ である．
可能ならばフリップする列と行の組の一例を出力してください．

$T$ 個のテストケースが与えられるので，それぞれについて答えてください．

制約

$ 1\leq T\leq 10^5$
$ 1\leq N\leq 1000$
$A_{i,j} \in\lbrace 0,1\rbrace$
$0\leq R_i,C_j\lt \frac{N}{4}$
$T,N,R_i,C_j$ は整数
$1$ つの入力ファイルに含まれる $N^2$ の総和は $10^6$ 以下

解法

$R_i,C_j \lt \frac{N}{4}$ という制約がどう見ても際立っているのだが、どう活かせばよいかわからなかった。

実は、$R,C$ との合致以前に、そもそも行・列フリップを繰り返して作れる「全ての行・列について総和が $\frac{N}{4}$ 未満」となるような盤面は、高々1通りしかない。

略証

フリップする行と列を決めたとき、操作後の $A$ は、以下のように、フリップ行とフリップ列の01行列を、各 $(i,j)$ 毎にかけあわせたものと表せる。

元のA     行F       列G       操作後B
10101     00000     10001     00100      +: ここではxor演算を表す ⊕ の代用とする
11110     11111     10001     10000         （⊕はフォントによって幅が安定しないため）
01111  +  11111  +  10001  =  00001
10011     00000     10001     00010
00110     11111     10001     01000

これを、$A \oplus F \oplus G = B$ と表現する。

もし、2つの行列 $B_1$ と $B_2$ があって、ともに「全ての行・列について総和が $\frac{N}{4}$ 未満」となるとする。

$A \oplus F_1 \oplus G_1 = B_1$
$A \oplus F_2 \oplus G_2 = B_2$

$B_1 \oplus B_2$ を考える。

$B_1 \oplus B_2 = A \oplus F_1 \oplus G_1 \oplus A \oplus F_2 \oplus G_2$
$B_1 \oplus B_2 = (F_1 \oplus F_2) \oplus (G_1 \oplus G_2)$

各行・各列の総和は多くとも $\frac{N}{2}$ 未満である（1が被らない場合の上限がこれで、被ったらもっと小さくなる）。
また、$F_1 \oplus F_2$ は各行が全て0か全て1、$G_1 \oplus G_2$ は各列が全て0か全て1の行列である。

よって、こんな感じにしかならない。

F1⊕F2     G1⊕G2
11111     11000     00111    F1⊕F2で1の行を上に寄せ、
11111     11000     00111    G1⊕G2で1の行を左に寄せて考えると、
00000  +  11000  =  11000    どこかの格子点で十字に0と1が切り替わる
00000     11000     11000    ような状態になる。
00000     11000     11000

$F_1 \neq F_2$ または $G_1 \neq G_2$ の場合、どうしても行・列には総和が $\frac{N}{2}$ 以上の箇所ができてしまうので矛盾する。

よって、「全ての行・列について総和が $\frac{N}{4}$ 未満」という状態を1つ作れれば、それが $R,C$ と合致するかを調べればよい。

具体的な構築方法も、$\frac{N}{4}$ を上手く使わないとなかなか思いつきづらいが、

まず、行に操作して、1列目を全て $0$ にする。
10101      01010
11110      00001
01111  →  01111
10011      01100
00110      00110

こうすると、今後、行について操作するのは $\frac{N}{4}$ 回未満に限られる。（1列目が $\frac{N}{4}$ 以上になってはいけないので）

よって、この時点で1列に'1'が $\frac{N}{2}$ 個以上ある列は反転させなければいけないし、$\frac{N}{2}$ 未満の列は反転させてはいけない。フリップする列が一意に決まる。

 vvv
01010      00100
00001      01111
01111  →  00001
01100      00010
00110      01000

その後、$\frac{N}{4}$ 個以上ある行をフリップすればよい。
$A$ が「全ての行・列について総和が $\frac{N}{4}$ 未満」とすることが可能であれば、そのようになっている。

00100      00100
01111      10000
00001  →  00001
00010      00010
01000      01000

Python3

def solve(n, aaa, rrr, ccc):
    def transpose():
        trans = [0] * n
        for i in range(n):
            for j in range(n):
                if aaa[i] & (1 << j):
                    trans[j] |= 1 << i
        return trans

    def print_aaa():
        fmt = f'  {{row:0{n}b}}'
        for row in aaa:
            print(fmt.format(row=row))

    limit2 = (n - 1) // 4 * 2
    limit4 = (n - 1) // 4
    mask = (1 << n) - 1
    xxx = [0] * n
    yyy = [0] * n

    for i in range(n):
        if aaa[i] & 1:
            aaa[i] ^= mask
            xxx[i] = 1
    aaa = transpose()

    for i in range(n):
        if aaa[i].bit_count() > limit2:
            aaa[i] ^= mask
            yyy[i] = 1
    aaa = transpose()

    for i in range(n):
        if aaa[i].bit_count() > limit4:
            aaa[i] ^= mask
            xxx[i] ^= 1

    for i in range(n):
        if aaa[i].bit_count() != rrr[i]:
            return None, None
    aaa = transpose()
    for i in range(n):
        if aaa[i].bit_count() != ccc[n - i - 1]:
            return None, None

    yyy.reverse()
    return xxx, yyy


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = [int(input(), base=2) for _ in range(n)]
    rrr = list(map(int, input().split()))
    ccc = list(map(int, input().split()))
    xxx, yyy = solve(n, aaa, rrr, ccc)
    if xxx is None:
        print('No')
    else:
        print('Yes')
        print(''.join(map(str, xxx)))
        print(''.join(map(str, yyy)))

B - Adjacent Replace

問題文

長さ $N$ の非負整数列 $A=(A_1,A_2,\ldots,A_N)$ および非負整数 $K$ が与えられます．
以下の操作を $10^4$ 回以下行うことで $A_1=K$ にすることが可能かどうか判定してください．
- 整数 $i\ (1\leq i\leq N-1)$ を選ぶ．$x=A_i\oplus A_{i+1}$ としたとき，$A_i,A_{i+1}$ をそれぞれ $x$ で置き換える．
- ここで，$\oplus$ はビット単位 $\mathrm{XOR}$ 演算です．

可能な場合，そのような操作手順を一つ出力してください．
$T$ 個のテストケースが与えられるので，それぞれについて答えてください．

制約

$1\leq T\leq 50$
$3\leq N\leq 60$
$0\leq A_i,K\lt 2^{60}$
入力は全て整数

解法

基本的な方針は早々に分かって、後は場合分けを頑張るだけやし時間かければいけるやろ！で挑戦したけど、個々の場合分けに対する実装が遅すぎて間に合わなかった。どうやって素早く実装できるの。。。

使うindexの決定

まず、隣接は関係なく「$A$ から好きな要素を抽出して、総XORで $K$ を作ってください」という問題は典型であり、 XOR基底を求めることで可能不可能を判定できる。

基底を求める際に、「この基底は、元の $A$ のどれとどれをXORして作られたもの」という情報も計算しておけば、具体的な構築方法の一例も求められる。

これにより、そもそも $A$ をどのように組み合わせても $K$ を作れない場合は“No”。
以下、作れるとする。

上記の方法で見つけた $K$ の構築方法の1つを $I=(i_1,i_2,...,i_m)$ として元の問題に戻ると、「操作を繰り返して、$A_1$ を、$A_{i1} \oplus A_{i2} \oplus ... \oplus A_{im}$ にする」とよいことがわかる。

じゃあ、実際に可能か？を考える。

使わない要素が2つ連続している箇所がある場合

a   b   c   d   e   f    o: 使う
o   x   x   o   x   o    x: 使わない

構築方法の一例
a   b   c   d   e   f
      x
a  bc  bc   d   e   f    同じ箇所に2回操作することで
      x                  隣接2要素を0にできる
a   0   0   d   e   f
          x              dをずらして d,f の間を2つ以上開ける
a   0   d   d   e   f
              xx         2回の操作で0にする
a   0   d   0   0   f
          x   x   x      右から順に
a   0  df  df   f   f
  x   x                  右から順に
adf adf df df   f   f

使わない要素が2つ連続している箇所があったら、その2つを0にして、使う要素を移動できる。
他に使わない要素が1つしか連続していない箇所があっても、↑の移動で順にずらして、2つ以上の連続にすることができる。

使う要素が2つ連続している箇所がある場合

a   b   c   d   e   f    o: 使う
o   x   o   o   x   o    x: 使わない

構築方法の一例
a   b   c   d   e   f    ともに使うc,dを1つにまとめると、
          x              どちらか一方は「使わない要素」と見なして良くなる
a   b  cd  cd   e   f
      xx
a   0   0  cd   e   f    後の流れは、1つめの例の3行目以降と同様

最初、使わない要素が2つ連続してる箇所が無い場合でも、使う要素が2つ以上連続してる箇所があれば、その連続箇所の端の2要素を1つにまとめると、使わない箇所の2つの連続を作ることができる。

どちらも無い場合

a   b   c   d   e   f    o: 使う
o   x   o   x   o   x    x: 使わない
  or
x   o   x   o   x   o

使用・不使用が最後まで交互に並ぶ状態のみ該当する。

この場合は不可能。どうしても初手で o と x が混ざり合ってしまい、それを分離する方法が無い。

ただし、$I$ の他にも $K$ を作り出せるindexの組がある場合は、そちらでできる可能性がある。

他に $K$ を作り出せる方法があるかどうかは、XOR基底に“0”が存在する（という言い方は厳密には正しくない？まぁ、掃き出し法の過程で最後に余った0が出てくる、という意味）のと同値。
“0”を作るためのindexの組の1つ $J=(j_1,j_2,...)$ と、$I$ の、集合としてのXOR（片方にのみ含まれる要素からなる集合）が $I$ の他に $K$ を作り出せる方法の1つとなる。

ただし、作り方が2通りあっても、どちらもダメ、という場合もあるので注意。

6 21             1,4,16 か 2,8,31 でしか 21 を作れないが
1 2 4 8 16 31    どちらもダメ

不可能な状態は2通りしかないので、XOR基底に“0”が2個以上存在すれば、4通り以上の $K$ を作る方法があり、必ず可能な状態にできる。
高々2通りの $J$ を試せばよい。

構築方法

まず、コーナーケースとして、使う要素が0個の状態を考える。
これはつまり、$K=0$ ということなので、$i=1$ に2回操作すれば簡単にできる。

以降、使う要素は1個以上あるとする。

$K$ を作るための要素 $I=(i_1,...,i_m)$ に対し、右端の $A_{im}$ から降順に、$I$ に含まれるindexの要素だけをXOR合成しながら $A_1$ まで運んでいきたい。
ひとまず、$A_1$ まで運ばずとも「使う要素を全て合成し、$i_1$ の位置に $K$ を作る」ところまでを目指す。

そのために、「$i_m$ の右に、使わない要素（バッファ）が2個以上ある」初期状態を目指す。
使わない要素が1個しか連続していない箇所を上手く乗り越えるには、右側に2個のバッファを要するからである。なお、間が0個、2個以上、の場合はバッファは不要。

右から合成していくための初期状態として目指す形

○   ... o x x ]    o: 最も右で使う要素
×   ..... o x ]    ]: 配列の終わり
×   ....... o ]

b を a にXOR合成するために、その間に使わない要素が何個あるか、で場合分け

0個
...  a  b             そのまま操作すればよい
... ab ab

1個
...  a  x  b  x  x    a,b:使う要素
...  a  x  b  0  0    x:使わない要素
...  a  x  b  b  0
...  a  0  0  b  0    b の右にバッファが2個あれば
... ab ab  b  b  0    b を、間にある x を含めず a と合成できる

2個以上
...  a  x  x  x  b    間の使わない要素を全て0にした上で、
...  a  0  0  0  b    降順に操作して b を運んでいける。
... ab ab  b  b  b

最初から右側にバッファが2個以上あればよいが、そうで無い場合、事前に調整して作っておく必要がある。
調整の方法を考える。

使う要素のうち、最も右にあるもののindexを $i_m$ とする。バッファが2個未満という前提で、$i_m=N-1$ または $i_m=N$ である。
最も右にある使わない要素の連続箇所を $u$、使う要素の連続箇所を $v$ とする。

どちらも存在しない場合はあり得ない。（使用不使用が交互に並ぶ不可能配置となり、判定の時点ではじかれているはずなので）

・u が存在する場合:
    u 以降の使う要素を、左から順番に左に寄せていける。
    ... x x a x b x c    a,b,c: 使う要素
    ... 0 0 a x b x c    x: 使わない要素
    ... a a a x b x c
    ... a 0 0 0 b x c
    ... a b b b b x c
    ... a b 0 0 0 0 c
    ... a b c c c c c    ←最も左以外のcは使わない要素なので
    ... a b c x x x x    ←このように見なせ、条件を満たす。
    
    なお、a,b,c をどこまで左に移動させるかは、
    上記の例のように「隙間無く並べる」だけでなく
    「この時点で合成までしてしまう」「それぞれ2個ずつ左に寄せる」などでもよい。お好みで。

・u が存在せず、v が存在する場合
  ・v が、最も右の使う要素を含む場合
    ・右にバッファが1個ある場合
        ...  a  b  x ]
        ... ab ab  x ]    ←この、右側のabは使わない要素なので
        ... ab  x  x ]    ←このように見なせ、条件を満たす。

    ・バッファが0個で、使う要素が3つ以上連続している場合
        ...  a   b   c ]
        ...  a  bc  bc ]    末尾から順に操作していけばよい。
        ...abc abc  bc ]
        ...abc   x   x ]    ←このように見なせ、条件を満たす。
        
    ・バッファが0個で、使う要素の連続が2個のみの場合
        ...  x  b  c ]
        ...  x bc bc ]    ちょっとややこしいが、
        ...  0  0 bc ]    一旦右にまとめてから左に移動させる
        ... bc bc bc ]
        ... bc  x  x ]
  
  ・v が、最も右の使う要素より左にある場合
    ...  a  b  x  c  x  d
    ... ab ab  x  c  x  d
    ... ab  x  x  c  x  d    ←このように見なせるので、uが存在する場合に帰着

これで事前調整して、末尾から $I$ に含まれるindexだけを合成していき、$i_1$ の位置に $K$ を作れたとする。
これを $i=1$ まで運ぶ作業も、だいたいは上記と同じ感じで、

i1=1
既に完成している

i=2
x  o  x  x ...    N=3 の時は判定問題の時点で不可能とはじかれているため、
x  o  0  0 ...    N>=4 で、使う要素の右側には2個以上の使わない要素の連続がある。
x  o  o  0 ...
0  0  o  0 ...    一旦右に待避させることで、
o  o  o  0 ...    左側に2個以上の使わない要素の連続を作る。

i1>=3
x  x  x  o ...    2個以上の使わない要素の連続があれば、
0  0  0  o ...    操作を繰り返して0にできるので、
o  o  o  o ...    後は降順に操作して、使う要素を運んでいける。

これで完成である。

操作回数を見積もる。以下の場合にかさみそう。

「$u$ が存在する場合」で、$u$ が $A$ の左端にあり、各要素を左端にはるばる集める場合
ほとんど交互で、右端だけバッファが2個ある状態

前者は、使用不使用が交互に並ぶ中の使う要素（$\frac{N}{2}$ 個程度）の各 $A_i$ それぞれについて、$O(i)$ 個の使わない区間を $0$ に舗装してから $O(i)$ かけて運ぶ必要がある。定数倍を考慮すると、$2i+2$ 以内には可能なので、これを飛び飛びで総和を取っていくと、だいたい $\frac{N^2}{2}$ 程度と見積もれる。

後者は、1つ使わない要素を乗り越えるのに $8$ 回の操作が必要なので、$4N$ 程度と見積もれる。

いずれにしても、十分余裕を持って $10^4$ 回以内に収めることができる。

Python3

C - Circular Tree Embedding

問題文

この問題では，頂点に $1,2,\ldots,N$ の番号が付けられ，辺に番号が付いていない $N$ 頂点の木を単に $N$ 頂点の木と呼ぶことにします．
$N$ 頂点の木 $T$ および $(1,2,\ldots,N)$ の順列 $Q=(Q_1,Q_2,\ldots,Q_N)$ が次の条件を満たすとき，順列 $Q$ は木 $T$ の良い順列であると呼びます．
- 円周上に $N$ 個の点 $1,2,\ldots,N$ がこの順で反時計回りに等間隔で配置されている．
- 木 $T$ の各辺 $\lbrace u,v\rbrace$ に対して $2$ 点 $Q_u,Q_v$ を結ぶ線分を書き込む．
- このとき，書き込まれた $N-1$ 本の線分のうちどの $2$ 本を選んでも，それらは端点を除いて共有点を持たない．

$M$ 個の $(1,2,\ldots,N)$ の順列 $P^1=(P^1_1,P^1_2,\ldots,P^1_N),P^2=(P^2_1,P^2_2,\ldots,P^2_N),\ldots,P^M=(P^M_1,P^M_2,\ldots,P^M_N)$ が与えられます．
$P^1,P^2,\ldots,P^M$ が全て良い順列となるような $N$ 頂点の木の個数を $998244353$ で割った余りを求めて下さい．

制約

$2\leq N,M\leq 500$
$P^1,P^2,\ldots,P^M$ は $(1,2,\ldots,N)$ の順列
入力は全て整数

解法

問題設定を理解するのがまず難しい。

満たすべき条件

頂点番号は 0-indexed に読み替える。

各 $P$ の逆順列（$Q[P_i]=i$ となるような $Q$）を求めて、$Q$ の順に円周上に並べる。

i  0 1 2 3 4 5 6 7
P  5 2 4 6 7 0 1 3
Q  5 6 1 7 2 0 3 4
    ↓               他のPも同様に
  ⑤ ⑥             ③ ④      ⓪ ②
④     ①         ②     ⑤  ③     ④
③     ⑦         ⓪     ⑦  ⑦     ⑤
  ⓪ ②             ⑥ ①      ① ⑥

$N$ 頂点の木に対して「円を1つ選び、周上の対応する番号の位置に頂点を置いていく」操作を考える。
この時「どの円を選んで操作しても、辺が交差しない」ような木の個数が答えとなる。

ひとまず、最大の⑦を根とした木で考える。
（通常は⓪を根とすることが多いが、今回は後述のDPで⑦を根とした方がやりやすい）

条件を満たす木は、「木の全ての部分木について『含まれる頂点集合がどの円周上でも連続している』」ことが必要十分条件となる。

      ⑦       部分木の頂点集合（1頂点のみのを除く）
    ／  ＼       ②⓪③
   ⑤    ⑥      ⑤②⓪③④
  /  \   ｜      ⑥①
 ②  ④  ①      ⑦⑤②⓪③④⑥①
 /\            これらは全て、どの円周上でも連続している
⓪③           （集合内での順序は円ごとに変わってよい）
               →この木は条件を満たす

ある部分木をなす頂点集合 $U$ の間に、部分木の外にある頂点 $v$ があり連続が途切れていたら、 $v$ は $U$ のどの頂点とも結ばれない（それ以外の頂点と結ばれる必要がある）のに、$U$ 同士は結ばれる必要があり、どうしても交差してしまう。

U = {0,1,2,3},   v = 4

   ：        ：    ⓪①②③が部分木を為す場合、
   ⓪--------③    どうしても(⓪①)と(②③)の間は結ばれることになり、
     ①----②'     ④は他の頂点に結びに行けなくなる。
        ④

数えあげ

ある部分木に対し、含まれる頂点集合がどの円周上でも連続しているものを「条件★を満たす」とする。
また、ある「条件★を満たす部分木」の集合のうち、どの円周上でも含まれる頂点が連続しているものを「条件☆を満たす部分森」と呼ぶことにする。

たとえば上例の木では、②⓪③と④はそれぞれ条件★を満たす部分木で、さらに②⓪③④も各円周上で連続しているので、{②⓪③, ④}は「条件☆を満たす部分森」である。

根を除く $N-1$ 頂点集合から作れる「条件☆を満たす部分森の個数」が答えとなる。
この森のそれぞれと根を結ぶことで木が完成する。
（全 $N$ 頂点からなる条件★を満たす部分木を数えると、構造が同じでも根を区別するため、重複が発生する）

順列上で連続していることが条件であることから、区間DPで数え上げることを考える。
ただ、「区間」が何を示すものなのか、まだちょっと曖昧である。

各順列 $Q$ に以下の改変を行う。

1つめの順列を、頂点を置換して、⓪①②…⑦ の順にする
残りの順列にも同じ置換を施した上で、⑦が最後になるように巡回シフトする

i    0 1 2 3 4 5 6 7
P1   5 2 4 6 7 0 1 3
Q1   5 6 1 7 2 0 3 4
     ↓                 置換
Q'1  0 1 2 3 4 5 6 7

Q2   3 4 5 7 1 6 0 2
     ↓                 同じマッピングで置換
     6 7 0 3 2 1 5 4
     ↓                 7が末尾になるように巡回シフト
Q'2  0 3 2 1 5 4 6 7

1つめの順列をこうすることで「条件★を満たす部分木」となるためには「頂点番号が連続するものからなる」が必要条件となり、「区間 $[l,r)$」を「頂点番号 $l,l+1,...,r-1$ の頂点集合」と自然な形で定義することができる。

また円環で考えると、⑦の位置が中ほどにあると順列の端を跨ぐ部分の処理に困るが、端にすることでそこで切り開いて数列と考えてよくなる。
以下、円周上での連続は、数列上での連続という判定に置き換えられる。

まず、以下を求める。

$\mathrm{ok}[i,j]:=$ 値 $i,i+1,...,j-1$ が、全ての順列上で連続しているか（bool）

これは、全ての順列の全ての区間について調べて間に合う。

まず、$\mathrm{ok}[i,j]$ を全て True で初期化する。
また、着目中の順列 $Q'$ における値 $k$ のindexを、$R_k$ とする。

順列 $Q'$ 上で $(l,l+1,...,r-1)$ が連続しているかの判定を行いたい場合、 $\max(R_{l},R_{l+1},...,R_{r-1}) - \min(R_{l},R_{l+1},...,R_{r-1}) = r-l-1$ かどうかを調べればよい。
違反していたら $\mathrm{ok}[l,r]$ を False にする。
各 $l$ から $r=l+1,l+2,...,N$ と1つずつ拡張していけば、1つ区間を伸ばすのに $O(1)$、全体 $O(N^2M)$ で調べられる。

これをもとに、以下のDPをおこなう。

$\mathrm{DP}_1[l,r]:=$ 区間 $[l,r)$ の頂点からなる、条件★を満たす部分木の個数
$\mathrm{DP}_2[l,r]:=$ 区間 $[l,r)$ の頂点からなる、条件☆を満たす部分森の個数
- それぞれは、部分木の根がどれかも区別する。

初期状態は以下のようにしておく。
長さ0と長さ1の区間は、1通りであることは自明なので、最初から埋めておく。

$\mathrm{DP}_1[i,i] = \mathrm{DP}_1[i, i+1] = 1$
$\mathrm{DP}_2[i,i] = \mathrm{DP}_2[i, i+1] = 1$
その他は0

長さ2以上の区間 $[l,r)$ について更新を考える。これより短い区間のDPは全て埋まっているとする。

$\mathrm{ok}[l,r]=$True であれば、単一の部分木が作れる。
根を $m=l,l+1,...,r-1$ とした場合の部分木の個数は、$\mathrm{DP}_2[l,m] \times \mathrm{DP}_2[m+1,r]$ となる。

また、複数の部分木からなる部分森については、1つめの部分木がどこまで続くかを全探索する。

$\displaystyle \mathrm{DP}_1[l,r] = \sum_{m=l}^{r-1} \mathrm{DP}_2[l,m] \times \mathrm{DP}_2[m+1,r]$（※$\mathrm{ok}[l,r]=$True の場合。Falseの場合、$0$）
$\displaystyle \mathrm{DP}_2[l,r] = \mathrm{DP}_1[l,r] + \sum_{m=l+1}^{r-2} \mathrm{DP}_2[l,m] \times \mathrm{DP}_2[m,r]$

としてDPを埋めていき、$\mathrm{DP}_2[0,N-1]$ が答えとなる。

Python3

import os
import sys

import numpy as np


def solve(inp):
    n, m = inp[:2]
    ppp_list = np.ascontiguousarray(inp[2:]).reshape(m, n) - 1
    qqq_list = np.empty_like(ppp_list)  # ppp の逆行列（実際の頂点の並び）、最大要素を末尾に揃える
    rrr_list = np.empty_like(ppp_list)  # qqq の逆行列
    for i in range(m):
        qqq_list[i] = np.argsort(ppp_list[i])
    converter = np.argsort(qqq_list[0])
    for i in range(m):
        qqq_list[i] = converter[qqq_list[i]]
        k = np.argmax(qqq_list[i])
        qqq_list[i] = np.roll(qqq_list[i], -k - 1)
        rrr_list[i] = np.argsort(qqq_list[i])

    ok = np.ones((n, n), dtype=np.int64)
    for i in range(1, m):
        for j in range(n - 1):
            mn = mx = rrr_list[i, j]
            for k in range(j + 1, n - 1):
                mn = min(mn, rrr_list[i, k])
                mx = max(mx, rrr_list[i, k])
                if mx - mn != k - j:
                    ok[j, k + 1] = 0

    dp1 = np.eye(n, k=1, dtype=np.int64)  # 単一の根を持つ部分木として、あり得る個数
    dp2 = np.eye(n, k=1, dtype=np.int64)  # 部分森としてあり得る個数
    for i in range(n):
        dp1[i, i] = 1
        dp2[i, i] = 1
    MOD = 998244353

    for w in range(2, n):
        for l in range(n - w):
            r = l + w
            tmp1 = 0
            tmp2 = 0
            if ok[l, r] == 1:
                for m in range(l, r):
                    tmp1 += dp2[l, m] * dp2[m + 1, r]
                    tmp1 %= MOD
                dp1[l, r] = tmp1
            for m in range(l + 1, r):
                tmp2 += dp1[l, m] * dp2[m, r]
                tmp2 %= MOD
            dp2[l, r] = (tmp1 + tmp2) % MOD

    return dp2[0, n - 1]


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

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

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

目次

AtCoder Regular Contest 199 (Div. 1) A,B,C問題メモ

A - Flip Row or Col 2

問題文

制約

解法

B - Adjacent Replace

問題文

制約

解法

使うindexの決定

使わない要素が2つ連続している箇所がある場合

使う要素が2つ連続している箇所がある場合

どちらも無い場合

構築方法

C - Circular Tree Embedding

問題文

制約

解法

満たすべき条件

数えあげ