しょぼんブログ

数学の色々とか様々とか

連載 しょぼんコーダー 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 を超えたら切り上げる.

続きを読む

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

yukicoder.me

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

続きを読む

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

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

この一般化は, 「二項変換」と関連があるのでそれについても述べます.

続きを読む

ICPC 2019 模擬国内予選H: 不思議なボタン 解説

問題文

問題文は以下をご覧ください。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2951&lang=jp

この記事は非公式です。この問題の公式解説は以下からご覧ください。

2019/Practice/模擬国内予選/講評 - ICPC OB/OG の会

続きを読む

yukicoder で合同コンを開きました(二回目!)

yukicoder で noya2 さんと合同でコンテストを開きました.

yukicoder.me

全体Tester にはまた Nachia さんに来ていただきました. 二回も全体Tester を引き受けていただき本当に感謝しています!!!!

F は特に難しかったので Tester に kaichou243 さんに来ていただきました!!! ありがとうございます!!!!

前回のコンテストは以下です。

yukicoder.me

難易度は ★2.0 - ★2.5 - ★3.5 - ★3.5 - ★4.5 - ★5.0 の 2時間40分 (ジャッジつまりで10分延長!) でした. 前回よりも難しめのセットになっております. Writer / Tester を除いて, 参加者は 119 人、各問題の正解者は
[A] 105人 / 107 ★2.0
[B] 67人 / 76 ★2.5
[C] 36人 / 47 ★3.5
[D] 26人 / 32 ★3.5
[E] 2人 / 10 ★4.5
[F] 1人 / 4 ★5.0
でした.

FA 者は以下をご覧ください! yukicoder.me

この記事では, 問題の裏話や, 人々がどんな感じで解いてたかを作問者が覗き見た感じ(?)を書いています.

A - Find Zero (★2.0)

No.2252 Find Zero - yukicoder

B - Ignore Subtle Differences (★2.5)

No.2253 Ignore Subtle Differences - yukicoder

C - Reverse Only (★3.5)

No.2254 Reverse Only - yukicoder

D - Determinant Sum (★3.5)

No.2255 Determinant Sum - yukicoder

E - Step by Step (★4.5)

No.2256 Step by Step - yukicoder

F - Swim and Sleep (★5.0)

No.2257 Swim and Sleep - yukicoder