Official

Overall Editorial by toam

ヒント集

A - Flip Row or Col 2

ヒント 1 この問題の最大のポイントは $R_i,C_j\lt N/4$ という制約です．この制約を利用する方法を考えてみましょう．
ヒント 2 最初に適宜列 flip をすることで，$A$ の一行目の要素はすべて $0$ であるとしてもかまいません．
ヒント 3 $A$ の一行目の要素がすべて $0$ である状態から始めて，行 flip → 列 flip の順番に操作することにします．このとき，各行を flip すべきかどうかはあることに注目することで一意に定まります．
ヒント 4 列 flip は多くても $(N-1)/4$ 回しか行えません．
ヒント 5 行 flip が終わった後，各行の総和は $N/2$ 以下である必要があります．

解説 → https://atcoder.jp/contests/arc199/editorial/13070

B - Adjacent Replace

ヒント 1 この問題は大きく分けて $2$ つのパートからなります．$1$ つ目は $K$ を作ることができるかという判定パート，$2$ つ目は実際にどのような操作方法をすればよいかという構築パートです．
ヒント 2 まずは $A=(2^0,2^1,\ldots,2^{N-1})$ としたときにどのような数を作ることができるか考えてみましょう．
ヒント 2 の答え $A=(2^0,2^1,\ldots,2^{N-1})$ のときに作ることができる $K$ は $0\leq K\lt 2^N$ かつ $K\neq 2^0\oplus 2^2\oplus 2^4\oplus\dots$ かつ $K\neq 2^1\oplus 2^3\oplus 2^5\oplus\dots$ です．
ヒント 3 $A=(2^0,2^1,\ldots,2^{N-1})$ かつ $K$ が作ることが可能なとき，実際にどのような手順で作ることができるかを考えてみましょう．例えば $K\ \mathrm{AND}\ 2^j=0\land\ K\mathrm{AND}\ 2^{j+1}=0$ となる $j\ (0\leq j\leq N-2)$ が存在するときはどのような操作の方針が立てられるでしょうか．
ヒント 4 $A$ が一般の場合，$\displaystyle\bigoplus_{i\in S}A_i=K\land S\neq \lbrace 1,3,5,\ldots\rbrace\wedge S\neq \lbrace 2,4,6,\ldots\rbrace$ を満たす $S$ が存在するかどうかが分かればよいです．これは掃き出し法で求めることができます．

解説 → https://atcoder.jp/contests/arc199/editorial/13075

C - Circular Tree Embedding

ヒント 1 まずは $M=1$ かつ $P^1=(1,2,\ldots,N)$ の場合を考えてみましょう．この $P^1$ が良い順列となる木はどのような性質があるでしょうか．
ヒント 2 木を頂点 $1$ を根とする根付き木とします．$(1,2,\ldots,N)$ が良い順列となるような根付き木はどのようなものか，部分木の頂点集合に着目して必要十分条件を考えてみましょう．
ヒント 2 の答え 根付き木の任意の部分木の頂点集合は，うまく並び換えることで$(1,2,\ldots,N)$ の連続部分列になっています．これが必要十分条件です．
ヒント 3 $P^i$ が良い順列であることと $((P^i_1+k\ \mathrm{mod} \ N) + 1,(P^i_2+k\ \mathrm{mod} \ N) + 1,\ldots,(P^i_N+k\ \mathrm{mod} \ N) + 1)$ が良い順列であることは同値なので，$P^i_1=1$ としても良いです．一般の順列 $P^i\ (P^i_1=1)$ について，$P^i$ が良い順列となるような根付き木は，任意の部分木の頂点集合をうまく並び換えると $P^i$ の逆順列の連続部分列になっています．
ヒント 4 各 $P^i$ について，部分木の頂点集合としてよいものはそれぞれ $N(N+1)/2$ 個あります．$P^1,P^2,\ldots$ それぞれについてその集合を求めたとき，そのすべてで現れるような集合のみが条件を満たす根付き木の部分木の頂点集合としてよいです．
ところで，すべての順列を同時にうまく変換することで $P^1=(1,2,\ldots,N)$ とすることができます．このように変換すると，条件を満たす根付き木の頂点集合は $\lbrace l,l+1,\ldots,r\rbrace$ のように表すことができます．
ヒント 5 あとは $\mathrm{dp}[l][r]$ を「$\lbrace l,l+1,\ldots,r\rbrace$ を頂点集合とする部分木の場合の数」として，区間 dp で数え上げられます．

解説 → https://atcoder.jp/contests/arc199/editorial/13069

D - Limestone

ヒント 1 まずは，作ることができる行列の個数を求める方法を考えてみましょう．これを求める方法と同じ方法で $\sum A$ の総和を求める問題も解くことができます．
ヒント 2 各行でそれぞれ左からいくつ $1$ にするか，各列でそれぞれ上からいくつ $1$ にするかを決めると行列 $A$ を生成することができます．ある $A$ を生成する方法は一般に複数通りありますが，生成する方法を特徴づけることによって $A$ と生成方法の間に単射を作ることができます．
ヒント 3 $i$ 行目では左から $R_i$ 個を $1$ に，$j$ 列目では上から $C_j$ 個を $1$ にするとしたとき，ある $A$ を生成する $R,C$ のうち，$R$ が辞書順最大のもの，さらにその中で $C$ が辞書順最大のものと特徴づけると良いです．
ヒント 4 ヒント 3 で特徴づけた条件を満たしている $(R,C)$ の組の集合を $S$ とします．$R$ を固定したとき，$(R,C')\in S$ を満たすような $C'$ の個数を $O(H+W)$ で求める方法を考えてみましょう．
ヒント 5 ヒント 4 の問題を考えるときに重要となる点をキーにする dp で $A$ の個数を求めることができます．

解説 → https://atcoder.jp/contests/arc199/editorial/13076

posted:
last update: