1. [1-] $S,T$を互いに素な$1$要素の集合としたとき、$S \cup T$の要素数は？ $2$.(それはそう) 2.[1+] $\mathrm{(a)}$ $[10]$の部分集合であって少なくとも1つの奇数を含むものは何通り？ 偶数と奇数別々に考えて良くて偶数の選び方は$2^5$通り,奇数の選び方は$2^5-1$通りあるから$2^5\cdot(2^5-1) = 992$通り ...

マージ過程を表す木を用いる典型テクを学んだので紹介する。 マージ過程を表す木とは 頂点$0,\dots,N-1$からなる$N$頂点$0$辺のグラフについて、指定された頂点のペアに辺を貼り連結成分をマージしていく操作を考える。各時点での連結成分に関するなんらかの値を求めたい場合や、ある頂点のペアが初めて連結になった時点での何らかの情報を得たい場合マージ過程を表す木が役に立つ可能性がある。マージ...

問題概要 $N$頂点$M$辺のグラフが与えられる。辺の削除が$Q$回行われる。頂点$2,\dots,N$について頂点$1$と非連結になったタイミングを答えよ。 解法 後ろから考えれば辺の追加を行っていき、頂点$1$と連結になったタイミングを答える問題に帰着できる。これは他の解説通りマージテクにより可能で、時間計算量$\Theta(N \log N)$になる。しかし素集合の要素の列挙と併合を...

EDPCを解いていこう A - Frog 1 $ \text{dp}[i] $ を足場$i$にたどり着くまでに支払うコストの総和の最小値とする。 [\text{dp}[i] \leftarrow \min(\text{dp}[i-1]+ h_i-h_{i-1} ,\text{dp}[i-2]+ h_i-h_{i-2} ...

公式解説の言い換えが思いつかなかったので遠回り 問題 E - Kth Number $0$以上$M$以下の整数からなる長さ$N$の数列$A$が与えられる。$A_i = 0$を満たすそれぞれの$i$について$、A_i$を$1$以上$M$以下の一様ランダムに選んだ整数で書き換える。その後$A$を昇順にソートしたとき、$A_K$の期待値を求めよ。 $N,M\le 2000$ 解法 数列の添字は0...

どの$C$を使えるかが問題 問題 E - Wish List $1,\dots,N$の番号がついた$N$個の商品がありそのうち$M$個の商品がほしい。商品$i$を買うためには、その時点で購入されていない商品の番号のうち$i$が小さい順に$j$番目だとすると $A_i+C_j$を払う必要がある。欲しい商品を全て買うために払う金額の最小値を求めよ。$N\le 5000$ 解法 見た目的にも...

いろいろ方法がある 問題概要 $H\times W$のマス目に正整数が書かれている。高橋くんが$H_1\times W_1$の領域を選び、それを見て青木くんが$H_2\times W_2$の領域を選ぶ。このときのスコアを高橋くんが選び、青木くんが選んでないマス目に書かれた整数の和とする。高橋くんがスコアを最大に、青木くんがスコアを最小にするような戦略を選ぶときスコアはいくらになるか？$H,...

補グラフ、２部グラフ、DP 問題概要 E - Independence $N$頂点$M$辺の無向グラフがある。グラフを2つの完全グラフに分けることができるかを判定し、できるなら両グラフの辺の数の和の最小値を求めよ。 解法 補グラフを考える。頂点を$S,T=[N]\setminus S$に分けるとき、辺は$S,T$間にのみ張られている必要がある。従って補グラフが2部グラフでないなら不可能であ...

hackに失敗して勉強になった 問題概要 $X_1,Y_1$が与えられる。$X_n,Y_n$を [\begin{align} X_{n+1} &= X_1 X_n - 5Y_1 Y_n Y_{n+1} &= Y_1 X_n + X_1 Y_n \end{align}] で定めるとき$X_1+\dots+X_N,Y_1+\dots+Y_N$を$\mod 9982443...

何回か前の精進でポインタを知らなくてポインタ木のコードが読めないという事があったのでポインタの入門をしながらsplay treeを書いた。 主に参考にしたのは splay tree をソラで書く！！！ エッ！？ 平衝二分木の update, push (eval, propagate) のタイミングがわからないですって？ フッフッフ…… maspyさんのライブラリ imp...