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$通り ...

日立製作所 社会システム事業部 プログラミングコンテスト2020 C問題

ARC203Cにかなり苦戦したが、そこで次のような計算が出てきたので紹介する。（本来の考察の順番としては後半のステップが最初にあるんだけど、そこからすぐうまくいくのが気づかなかった） 問題 \[[x^i y^j] \frac{1}{(1-x-y)^2 (1-x)^2}\] を求めよ。 解法 \[\frac{1}{(1-x-y)^2 (1-x)^2} = \left( \frac{1...

ハケンアニメ！ 辻村 深月 面白かった 火星に住むつもりかい? 伊坂 幸太郎 世界観に引き込まれる。ストーリーも面白い。 マイクロスパイ・アンサンブル 伊坂幸太郎 「現代版おとぎ話」というキャッチコピーらしい。すごい面白いという感じではなかったけどあんまり読んだこと感じで不思議な感覚だった。 夜のピクニック 恩田 陸 高校の行事でほぼ丸一日歩く話。いい話だったけど、自分なら嫌だなぁ ...

#include <bits/stdc++.h> int main() { int a = 2, b = 1; std::tie(a, b) = std::minmax(a, b); std::cout << a << " " << b << std::endl; } このコードを実行すると 1 1 が出...

マージ過程を表す木を用いる典型テクを学んだので紹介する。 マージ過程を表す木とは 頂点$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}| )\] で遷移させれば良い。 B - Frog 2 Aと同様...

公式解説の言い換えが思いつかなかったので遠回り 問題 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$ 解法 見た目的にも...