昨日の ABC258-G問題で BitSet という（C++の）データ構造を利用する想定の問題が出ました*1。 atcoder.jp BitSet は、MultiSet と同じく C# には（似たようなものはありますが）存在しないデータ構造です。C++だと通るらしい愚直解は通らなかったので、この…

ここで言う MultiSet とは C++ の multiset を模したデータ構造です。C# に標準で存在しないため、競技プログラミングなどで利用したい場合は自作する必要があります。 MultiSet が満たすべき性質 MultiSet は端的に言うと、順序を保ったまま高速に要素を追…

双方向リストは、片方向リストと比較して「前後両方のノードへのポインタを持つ」という点が特徴です。C# では LinkedList として実装されています。 双方向リスト 双方向リストは、以下のような特徴を持ちます。 先頭・末尾への要素追加が で可能 (そのノー…

競技プログラミングでよく使われる「セグメント木」というデータ構造があります。 これは、配列データに対して2のべき乗区間ごとに「合計値」「最大値」など注目したい演算を適用しておき、任意の区間に対する演算結果を で取得できるものです。 セグメント…