絶滅

どうでもいい

素集合データ構造と Union-Find アルゴリズム

素集合データ構造(そしゅうごうデータこうぞう、英: disjoint-set data structure)は、データの集合を素集合(互いにオーバーラップしない集合)に分割して保持するデータ構造。このデータ構造に対する以下の2つの便利な操作をUnion-Findアルゴリズムと呼ぶ。

  • Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。
  • Union: 2つの集合を1つに統合する。

これら2つの操作をサポートしているため、素集合データ構造は「Union-Findデータ構造」あるいは「Merge-Find集合」とも呼ばれる。これら以外の重要な操作として MakeSetがある。これは、与えられた1つの要素だけを格納した集合(シングルトン)を作成する。これら3つの操作により、様々な実用的分割問題を解くことができる(「応用」の節を参照)。

素集合データ構造 - Wikipedia

続きを読む

AtCoder Beginner Contest 075

f:id:my316g:20171014234239p:plain

時間ギリギリ 95 分弱でなんとか 4 問全部 AC できた.まあまあうれしい

f:id:my316g:20171014234246p:plain

レートは 200 ちょい上がって名前が緑色になった.

1200 まではビギナーで頑張ろうかなと思う(レギュラーで 1 完とかだと悲しいので…)

続きを読む

プログラミング言語C++

プログラミング言語C++ の第三版が研の床に落ちていたので読み始めた
本当は C++11 対応している第四版が気になったが日雇い労働者には無理なのでまあいいや

でかいプログラムが書けるようになりたいね

yukicoder - No.228

No.228 ゆきこちゃんの 15 パズル

問題ページ

続きを読む

yukicoder - No.212

No.212 素数サイコロと合成数サイコロ (2)

問題ページ

続きを読む