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

はじめに esperanto.cardsやankiweb上の共用デッキにてEsperanto cards (for English speakers)というデッキが公開されています。これはAnkiというアプリで使える英語話者用のエスペラントの単語帳なんですが、2500語収録されており（EO→ENとEN→EOで5000枚）音声や例文等も充実していて結構作り込まれているようです。このデッキを日本...

Rui Ueyamaさんの『低レイヤを知りたい人のためのCコンパイラ作成入門』と『chibicc』のリファレンス実装を読みながらCコンパイラをCで作っていきます。セルフホストできるところまで進めるのが当面の目標です。日記形式で書いていきます。 9/2 ～ 9/10 「ステップ14: 関数の呼び出しに対応する」まで進めた。 9/11 Commit aedbf56 では関数呼び出しの際RS...

日立製作所 社会システム事業部 プログラミングコンテスト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}{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} ...