ABC427E 解法 \(H,W \leq 12\) と小さいことに注目． ごみ全体の座標を持ちながら BFS をしても間に合う． ごみ全体の配置として，常に長方形領域に収まるということから， 状態数は \*1{ dis[trash] = d; que.push(trash); } }; // init ll th, tw; { T tra…

ABC428E 解法 木の直径を求めるアルゴリズム(ダブルスイープ)で OK. 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n; cin >> n; vvll to(n); rep(i,n-1){ ll a,b; cin >> a >> b; --a, --b; to[a].…

ABC429E 解法 多始点BFS. イメージとしては，始点とpath に色を付けて区別しながら BFS. 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n,m; cin >> n >> m; vvll to(n); rep(i,m){ ll a,b; cin >> …

ABC434E 解法 各ウサギについて，左右2通りが選べる． ウサギの座標を \(x\)として，左右の \(x-r, x+r\) の2つに辺を張ったグラフを考える． 左右を選ぶことは，辺の向きを選ぶことに対応する，もしくは辺の両端の一方に色をつけるという事に対応する． 頂…

ABC444D 解法 今の桁数を保持しながら，筆算の要領で計算すればよい． 桁数を保持しておくことで，今の桁にいくつ \(1\) を足せばよいか確定する． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n;…

ABC444C 解法 \(A\) をソートしておく． シェイクした後に一番長いスティック \(T\) に注目して場合分け． シェイク前の長さを \(L\) とおく． Case: \(T\) が折れてる\(A\) のサイズが奇数なら，シェイク前に全て \(L\) にできない． \(A\) のうち，一番長…

ABC436E 解法 1回目の操作を考えるのは難しいので，まずは最小の操作(もしくはその回数)を求める事を考える． 置換をサイクルに分轄すると，最小の回数が分かる． 互換を1回することで，サイクルが分離するまたは結合する． 今回は，恒等置換を作りたいので…

ABC438E 解法 バケツと水の量を，それぞれダブリング． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n,q; cin >> n >> q; vll a(n); rep(i,n) { cin >> a[i]; a[i]--; } const ll k = 35; vvll dp…

ABC439E 問題概要 拡張したLIS. 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n; cin >> n; vector<pll> pa(n); rep(i,n){ ll a,b; cin >> a >> b; pa[i] = {a, -b}; } sort(all(pa)); vll bs; for(auto</pll>…

ABC440E 解法 priority queue を用いてシミュレーションすれば良い． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n,k,x; cin >> n >> k >> x; vector<ull> a(n); rep(i,n) { cin >> a[i]; } sort(rall</ull>…

ABC441E 解法 累積和を使う． A に対して +1, B に対して -1 としておくと，A と B で共通の変数で累積和が求められて楽． この累積和を \(cum\) とおく． \(cum[r] > cum[l]\) となる \*1{ ans += fw.sum(0, cum[j]); fw.add(cum[j], 1); } cout << ans << …