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

ABC259F 木DP. DFSは，葉から決まるので木の問題を解くのに適している． 今いる頂点 \(cu\) に対して， \(ne \in to[cu]\) の結果を集計をどうするかを考える． 今回の問題では，辺と次数が重要なので， \(cu,ne\) を結ぶ辺が影響を与える． 逆に，それ以外…

ABC253F とりあえず欲しいのは出力クエリでの \((i,j)\) 成分の値． これは， \(i\) 行目に対する最後の代入クエリと，それ以降の \(i\) 行目に対する加算クエリの和が分かれば十分． これらは，クエリを先読みすることで得られる． 必要なデータ構造は，範…

ABC283F 平面走査の問題で，実装ではsegtreeを使う． まず，絶対値を外して考えるために，4つに場合分けする． 実装では，reverse をしたりすればある程度使いまわせるので，4つ書く必要はない． Case: \(i > j \) かつ \(P_{i} > P_{j}\)これは，よくある平…

ABC268F もし置換に関してDPをするなら， どれを選んだかという集合を持ちながら遷移するので， \(O(2^{N})\) がかかって無理． そこで，最適戦略を考える方針にする． いきなりは難しいので，簡単に考えるとすれば， 数字を1だけで考える 置換は互換のみ，…

ABC267F 木の直径に関する問題． 木の最長パスの一つを直径といい，これはDFSを2回することで求まる． まず任意の点 \(v\) からDFSをして，一番遠かった点を \(a\) とする． 次に \(a\) からDFSをして，一番遠かった点を \(b\) とする． \(a,b\) のパスが直…