概要 AtCoder Heuristic Contest 016 に参加したときに、頂点数 と次数 とを任意に指定して正則グラフを生成するアルゴリズムを調べて実装しました。せっかくなので、それについて書きます。生成されるグラフのランダム性などは考えず、とりあえず所望の正則…

競プロでダブリングと呼ばれるアルゴリズムの抽象化を考えてみました。ダブリングのアルゴリズム自体の解説はしません。 扱う問題 有限の状態集合 と、半群 を考えます。2つの写像 と とが与えられたとき、任意の と に対して、 を求めるという問題を扱いま…

はじめに 自然数全体の集合 は、以下のように和とスカラー倍を定めることにより、体 上のベクトル空間と見なせます。このベクトル空間を と書きます。 和は、bitwiseのXOR演算（以下では単に と書く） スカラー倍は、 本記事では、 の部分空間の基底を管理す…