ABC241F 大事な座標だけもって BFS. オブジェクトの周囲 4マスだけがグラフの頂点となる． map や upper_bound を使うので，遷移ごとに \(log(V)\) がかかる． ここで \(V\) は vertex の集合のサイズ． 前処理にもソートで \(log V\) が余分にかかる． 遷移…

ABC237F 制約から，DPで計算するときに 状態 \( O(NM^3) \), 遷移 \( O(M) \) でも間に合う． LIS の求め方を考えると， LIS の 3つの項が \(x,y,z\) のときを状態に持てばよい． 一旦，LIS を無視して考える． 長さ \(N\) の vector \(v\) であって，各元 \…

ABC236F \(V := (\mathbb{F}_{2}\) における \(N\) 次元ベクトル空間) の基底を求める問題． コストの小さいほうから貪欲に選んでいく． コストを無視すれば，吐き出し法で基底は求まる． \(b\) を 1次独立な vector の集合として，\(V\) を span できるまで…

ABC232F swap たち全て \(\rightarrow\) abs たち全ての順で操作をしても良い． まず \(n\) 次 permutation \(P\) を固定して， \(P\) に対するコストを求める． Swap of \(P\) の回数は，転倒数で求まる． これに \(y\) を掛けると，swap に対するコストに…

ABC224F 遷移が線形なので，行列積で書ける． + を置いたときに，+ より左にある項の和を \(t\), 今計算中の項を \(x\) とおく． 遷移は， \(s_{i}\) の直前に + を置く場合：\(t \rightarrow t + x\), \(x \rightarrow s_{i}\), \(1 \rightarrow 1\) となる…

ABC314E まず，0 の目が出ない様に変換しておく． 0 の個数を \(z\) 個とおく． 0 以外の目が出るまでの回数の期待値は \(\frac{p}{p-z}\) 回． \(c\) を \(c \cdot \frac{p}{p-z}\) で置き換えて，\(z\) を除いたルーレットで考えてよい． \(e_{x}\) を，ス…