自分だけ解けない問題

この記事は、Codeforces Global Round 25 F. Inversion Composition の解き方を提案したものです。自分は解説を見て考えただけです。

2024-04-01

AtCoder 黄色になりました！（橙→黄になっただけなので中身は入橙記事）

橙

AtCoder Regular Contest 173 で、AtCoder 橙色(2400) になることができました！

2024-02-05

ARC171-C Swap on Tree が理解できたかもしれない

はじめに

問題は以下です。

https://atcoder.jp/contests/arc171/tasks/arc171_c

この記事は本番中に通せなかった AtCoder Regular Contest 171 C問題 - Swap on Tree の解き方の解釈を与えたものです。

2023-12-18

連載しょぼんコーダー 7 有限位相空間の判定

連載しょぼんコーダー

第7回では, $\{0, 1, \cdots, n-1\}$ の部分集合系 $S$ が与えられたときに, $S$ が開集合系の定義を満たす（ $(\{0, 1, \cdots, n-1\}, S)$ が位相空間になる）かどうかの判定について書きます.

計算量は $S$ の要素数を $m$ , ワードサイズを $w$ として, 時間計算量 $O(n^2 m /w)$ , 空間計算量 $O(n^2+m)$ です. これが多項式時間になるという雰囲気が好きです.

あらすじ: $S$ を含む最小の位相空間の要素数が $m$ であるかを判定すればよい. $S$ を含む最小の位相空間と対応する preorder を作り, 縮約し DAG にする. その DAG についてある種の DFS を行い, 開集合の個数を数え上げる. ただし, 個数が $m$ を超えたら切り上げる.

2023-11-03

Yukicoder No.2530 Yellow Cards 別解(Bonus 解法)

問題解説

yukicoder.me

今日 yukicoder contest 411 オムニバスコンテスト - yukicoder というコンテストにて, はちじさん Writer の問題 Yellow Cards が公開されました. 自分は Tester をさせていただきましたが, そこで別解を見つけたので書きたいと思います. この方法では, $N \lt 998244353, K \le 10^{18}$ という制約で解くことが可能であり, 想定解法より高速です.

2023-07-13

連載しょぼんコーダー 6 一般化された包除原理と二項変換

連載しょぼんコーダー

第6回では, 一般化された包除原理について扱います. 包除原理は「条件を $1$ 個以上満たすものの個数」を数え上げるものです. これを一般化すると, 「条件を $K$ 個以上満たす」「条件をちょうど $K$ 個満たす」や「条件を $k$ 個満たすものは $k^2$ が答えに足される」などもふつうの包除原理と同じノリで解くことができます.