最近の記事

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

問題文 解法 クエリを$${B}$$個ごとにまとめて処理することを考えます。 加算クエリは、頂点の重みを増やすことで高速化を図ります。これにより、辺$${i}$$の重みが$${w_{a_i} + w_{b_i} + c_i}$$で計算できます($${w_v}$$は頂点$${v}$$の重み)。 また、加算クエリで現れる$${x}$$からなる集合$${X}$$を求めます。$${X}$$に属している、または$${X}$$に属している頂点と隣接している頂点を悪い頂点と呼ぶこと

    • PCK2020K (予選) - パスポート

      問題文 解法 次のように定めます。求める答えは$${f(1)}$$です。 $${f(v) := }$$(国$${v}$$から国$${N}$$まで最適に向かったとき、パスポートに書かれている文字列) 各国について、次に行くべき国が分かればよいです。これを末尾から決めていきます。 次に行くべき国の候補が$${x_1, \cdots, x_k}$$であるとします。このうち$${f(x_1), \cdots, f(x_k)}$$が最小になる国に行くのが最適です。以下では文字

      • Range Tree のメモ

        はしがき タイトル通りです。可読性は低いです。やる気が出たら可読性を上げます。 todo point add rectangle sum (https://judge.yosupo.jp/problem/point_add_rectangle_sum)を解きます。 tree.build() まず、登場する点をすべて先読みし、ソート済みの点列$${P = ((x_1, y_1), \cdots, (x_k, y_k))}$$を作ります。この$${P}$$から$${se

        • 23JOIG春合宿1-1 - Rocket Launching

          問題リンク: https://atcoder.jp/contests/joigsp2023/tasks/joigsp2023_a $${A, B}$$を整数からなる多重集合とします。突然ですが、次のクエリをオンラインで処理することを考えます($${x, h, t}$$はクエリで与えられます)。 クエリ 1 : $${A}$$に$${x}$$を追加する。 クエリ 2 : $${A}$$から$${x}$$を削除し、$${B}$$に$${h}$$を追加する。ただし、$${x\

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

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

          $${d_{\min}}$$を固定し、次の問題を解くことを考えます。 最小で何個の点を削除することで、距離をすべて$${d_{\min}}$$より大きくできるか? 距離が$${d_{\min}}$$以下であるような頂点同士をつないだ無向グラフを用意します。ある点を削除することは、それに対応する頂点とその頂点に接続する辺を削除することだと見做せます。つまり、問題は、「最小で何個の頂点を削除することで、辺を 0 本にできるか?」と言い換えられます。この答えは最小頂点被覆のサイ

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

          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}$$が奇数のときは$${\min(dp[M-1][0], dp[M][1])}$$です。

          ABC334C - Socks 2

          AGC035B - Even Degrees

          出次数は mod 2 で考えてもよい。このとき、辺$${i}$$の向きを flip をすることは、頂点$${A_i, B_i}$$の出次数を flip することと同値になる。 いま、ある相異なる頂点$${u, v}$$が存在して、いずれの出次数も 1 であるとする。与えられるグラフは連結であるから$${u, v}$$を繋ぐ単純パス$${P}$$が少なくとも 1 つ存在する。$${P}$$に含まれる辺の向きをすべて flip することで$${u, v}$$の出次数だけを fl

          AGC035B - Even Degrees

          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_i=1}$$なる$${pp}$$,または$${\sum_{i=y}^{sn}

          ARC153C - ± Increasing Sequence