\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) \(\def \ra {\rightarrow}\) ABC296F 解法 1回の操作で \(A\) の \(i,j\) の部分を swap して， 同時に \(B\) の \(i,k\) の部分を swap する． 一致できるかどうかだけが問題なので， \(A\) を固定して \(B\) だ…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) \(\def \ra {\rightarrow}\) ABC322F 解法 (交わらない)隣の二つの区間 \(I,J\) を結合したときを考える． 基本的には，\(I,J\) それぞれの 1 の連続区間の最大が \(I \cup J\) における最大となる． しかし，結…

ABC334F スタートとゴールの vertex を \(0\), それ以外の vertex を \(1, \cdots , N-1\) として， \(N\) 個の頂点で書き直したバージョンで説明する． \(d_{i,i+1}\) を \(i\) から \(i+1\) への距離とおく． 解法 0: Segtree まず簡単なバージョンの問題…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC282F 解法 0: Sparse table 長さ \(2^{i}\) の区間を用意して，それらの組み合わせで 区間を覆うことができる． 区間を指定されたとき，sarse table から使う幅 \(w\) を全探索する． \([l, l+w) \cup [r-w, r…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC147E 解法 absでなく差で考える． 基本は部分和と同じ様に解ける． つまり， \(dp_{i,j} := \) マス\(\ (i,j)\ \) にいるときの 偏り全体 とする． 実装 集合でなく bitset を使うと高速化出来る． 使っている…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) 問題の性質 まずは問題の性質から探る． 同じ種類の寿司なら，美味しさが高い物から食べるのが最善． 同じ種類を食べるときは，最初の 1個だけは種類ボーナスに影響するが， 2個目以降は影響しない． 簡単な問題 …

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) 解法 Lazy segtree. 文字列を 10進数とみなすので，segtree に乗せる． 区間の書き換えを保留しておくのがポイント． Segtree の積が，文字列の結合に対応する． 10進数で考えるので，結合する前の桁数を持ってお…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC225E 解法 問題文を翻訳すれば，区間スケジューリング問題と同じ． 区間の両端を，直線の傾きと考えればよい． 整数のペアとして，傾きを有理数で扱うと比較も整数でできる． 注意 分母が0になる場合と，既約…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC151F 解法 最小包含円を求めるアルゴリズムが知られている． 下に凸な関数に対して三分探索を二回用いる． \(P := {P_{i}}_{i \in N}\) を平面の点の集合とする． \(f_{P}(x,y) := \) 点 \(\ (x,y)\ \) から\(…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC331F 解法 ハッシュで部分文字列であるかを高速に判定する． 回文の判定として，通常の文字列と反転した文字列の2種類のハッシュを用意する． 文字列のハッシュを segtree に乗せることで， \(O(log N)\) でハ…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC321E 解法 1-indexed で complete binary tree の頂点に番号を付ける． LCA \(v\) を全探索． \(v\) を root とする subtree において，\(v\) からの距離が \(d\) である頂点全体の個数 \(f(v,d)\) を求める．…