記事一覧

ABC282F のジャッジ

問題:https://atcoder.jp/contests/abc282/tasks/abc282_f 注意 $${[l, r] = \lbrace l, l + 1, \cdots, r\rbrace}$$です。 やること 次の問題を$${O((M + N)\log N)}…

ripity
3か月前

PCK2017K (予選) - ネットワークの課金システム

問題文 解法 クエリを$${B}$$個ごとにまとめて処理することを考えます。 加算クエリは、頂点の重みを増やすことで高速化を図ります。これにより、辺$${i}$$の重みが$${w…

ripity
5か月前

PCK2020K (予選) - パスポート

問題文 解法 次のように定めます。求める答えは$${f(1)}$$です。 $${f(v) := }$$(国$${v}$$から国$${N}$$まで最適に向かったとき、パスポートに書かれている文字列) 各…

ripity
6か月前

Range Tree のメモ

はしがき タイトル通りです。可読性は低いです。やる気が出たら可読性を上げます。 todo point add rectangle sum (https://judge.yosupo.jp/problem/point_add_rectan

ripity
7か月前

23JOIG春合宿1-1 - Rocket Launching

問題リンク: https://atcoder.jp/contests/joigsp2023/tasks/joigsp2023_a $${A, B}$$を整数からなる多重集合とします。突然ですが、次のクエリをオンラインで処理するこ…

ripity
8か月前

PCK2023M (Final) - 点の削除 / Deleting Points

$${d_{\min}}$$を固定し、次の問題を解くことを考えます。 最小で何個の点を削除することで、距離をすべて$${d_{\min}}$$より大きくできるか? 距離が$${d_{\min}}$$以下…

ripity
8か月前

ABC334C - Socks 2

なくしていない靴下を色の昇順に$${B=(B_1, \cdots, B_M)}$$とします。特に、$${M=2N-K}$$です。 DP をします。$${dp[i][j]:=}$$「$${(B_1, \cdots, B_{i-1})}$$からちょ…

ripity
9か月前

AGC035B - Even Degrees

出次数は mod 2 で考えてもよい。このとき、辺$${i}$$の向きを flip をすることは、頂点$${A_i, B_i}$$の出次数を flip することと同値になる。 いま、ある相異なる頂点$$…

ripity
9か月前

ARC153C - ± Increasing Sequence

問題文 リンク: 解説 $${p=(1, 2, \cdots, N)}$$に対して次の操作を好きな回数施しても,$${p}$$は狭義単調増加なままです. $${p}$$の prefix に -1 を足す. $${p}…

ripity
1年前
1

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

もっとみる