ABC255F (Sub) tree を区間で表す．Pre order P : \( [r \ (A_{0})(A_{1})] \), In order I: \( [(B_{0})\ r \ (B_{1})] \)の形で表せる．ここで， \(r\) は root, \(A_{0}, B_{0}\) は左側の subtree, \(A_{1}, B_{1}\) は右側の subtree. Root \(r\) の入…

ABC217F 区間DPとなる． ペアを作って取り除いていく場合の数を数えるが， これは取り除く順序を木構造にして，それを数え上げる問題． 今回は，木の形が決まっていない． \([l,r)\) に対する答えを，より小さい区間に帰着させたい． \(i \in [l,r),\ i += 2…

ABC187F 連結成分ごとに完全グラフになっていることが必要十分． DPでの全探索を考える． \(s \in 2^{N}\) に対する答えを \(dp_{s}\) とおく． 連結成分の頂点の選び方さえ決まってしまえば， その内部でどの様に辺を削除したのかは関係ないので， \(s \in …

ABC218C \(\mathbb{Z}\times \mathbb{Z}\) 平面における回転を実装すると， \(N \times N\) のグリッドの回転と違って index のはみ出しを気にしなくて良いので楽． グラフの様に，'#'の位置情報を持っておく． \(vs_{i} := s_{i,j} = \) '#'となる \(j\) 全…