記事一覧
ABC282F のジャッジ
問題：https://atcoder.jp/contests/abc282/tasks/abc282_f 注意 $${[l, r] = \lbrace l, l + 1, \cdots, r\rbrace}$$です。 やること 次の問題を$${O((M + N)\log N)}…
Range Tree のメモ
はしがき タイトル通りです。可読性は低いです。やる気が出たら可読性を上げます。 todo point add rectangle sum （https://judge.yosupo.jp/problem/point_add_rectan…
23JOIG春合宿1-1 - Rocket Launching
問題リンク: https://atcoder.jp/contests/joigsp2023/tasks/joigsp2023_a $${A, B}$$を整数からなる多重集合とします。突然ですが、次のクエリをオンラインで処理するこ…
ABC282F のジャッジ
問題：https://atcoder.jp/contests/abc282/tasks/abc282_f
注意
$${[l, r] = \lbrace l, l + 1, \cdots, r\rbrace}$$です。
やること
次の問題を$${O((M + N)\log N)}$$時間で解きます：
$${M}$$個の閉区間$${[l_1, r_1], \cdots, [l_M, r_M]
PCK2017K (予選) - ネットワークの課金システム
問題文
解法
クエリを$${B}$$個ごとにまとめて処理することを考えます。
加算クエリは、頂点の重みを増やすことで高速化を図ります。これにより、辺$${i}$$の重みが$${w_{a_i} + w_{b_i} + c_i}$$で計算できます（$${w_v}$$は頂点$${v}$$の重み）。
また、加算クエリで現れる$${x}$$からなる集合$${X}$$を求めます。$${X}$$に属して
PCK2020K (予選) - パスポート
問題文
解法
次のように定めます。求める答えは$${f(1)}$$です。
$${f(v) := }$$(国$${v}$$から国$${N}$$まで最適に向かったとき、パスポートに書かれている文字列)
各国について、次に行くべき国が分かればよいです。これを末尾から決めていきます。
次に行くべき国の候補が$${x_1, \cdots, x_k}$$であるとします。このうち$${f(x_1),
Range Tree のメモ
はしがき
タイトル通りです。可読性は低いです。やる気が出たら可読性を上げます。
todo
point add rectangle sum （https://judge.yosupo.jp/problem/point_add_rectangle_sum）を解きます。
tree.build()
まず、登場する点をすべて先読みし、ソート済みの点列$${P = ((x_1, y_1), \cdo
23JOIG春合宿1-1 - Rocket Launching
問題リンク: https://atcoder.jp/contests/joigsp2023/tasks/joigsp2023_a
$${A, B}$$を整数からなる多重集合とします。突然ですが、次のクエリをオンラインで処理することを考えます（$${x, h, t}$$はクエリで与えられます）。
クエリ 1 : $${A}$$に$${x}$$を追加する。
クエリ 2 : $${A}$$から$$
PCK2023M (Final) - 点の削除 / Deleting Points
$${d_{\min}}$$を固定し、次の問題を解くことを考えます。
最小で何個の点を削除することで、距離をすべて$${d_{\min}}$$より大きくできるか？
距離が$${d_{\min}}$$以下であるような頂点同士をつないだ無向グラフを用意します。ある点を削除することは、それに対応する頂点とその頂点に接続する辺を削除することだと見做せます。つまり、問題は、「最小で何個の頂点を削除するこ
ABC334C - Socks 2
なくしていない靴下を色の昇順に$${B=(B_1, \cdots, B_M)}$$とします。特に、$${M=2N-K}$$です。
DP をします。$${dp[i][j]:=}$$「$${(B_1, \cdots, B_{i-1})}$$からちょうど$${j}$$個を削除したときの、奇妙さの最小値」とします。求めるべき値は、$${M}$$が偶数のとき$${dp[M][0]}$$、$${M}$$が奇
AGC035B - Even Degrees
出次数は mod 2 で考えてもよい。このとき、辺$${i}$$の向きを flip をすることは、頂点$${A_i, B_i}$$の出次数を flip することと同値になる。
いま、ある相異なる頂点$${u, v}$$が存在して、いずれの出次数も 1 であるとする。与えられるグラフは連結であるから$${u, v}$$を繋ぐ単純パス$${P}$$が少なくとも 1 つ存在する。$${P}$$に含まれ
ARC153C - ± Increasing Sequence
問題文
リンク：
解説
$${p=(1, 2, \cdots, N)}$$に対して次の操作を好きな回数施しても，$${p}$$は狭義単調増加なままです．
$${p}$$の prefix に -1 を足す．
$${p}$$の suffix に 1 を足す．
簡単のため，$${s=\sum_{i=1}^N p_i A_i\gt 0}$$とします．
$${\sum_{i=1}^{pp} A