頂点数と次数を指定して正則グラフを生成する

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

XORベクトル空間の基底の数え上げ

体 上のベクトル空間 について。 線形独立な集合 とする。このとき、任意の に対して もまた線形独立になる。ただし、 である。また、線形独立な集合の部分集合もまた線形独立である。線形代数で基本的なことだけど、これらにより次がわかる。 線形独立で大…

ARC145 C - Split and Maximize 解法の正当性

ARC145 C - Split and Maximize の公式解説があっさりしていて説明不足だと思ったので、行間を埋めていたら結構たいへんだった。 スコアが最大となる構造の分析 のとき、 が成り立つのは公式解説の通りです。 〜 を使った ペアの作り方が任意に与えられたと…

ダブリングの抽象化

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

ARC138 D - Differ by K bits の解法の正当性を示す

なんの記事? ビットグレイコードの、ハミング距離 のバージョンは存在しますか?存在するならばそのひとつを構築してください、という問題がARC138 Dにて出題されました。 問題へのリンク 公式解説 のときはグレイコードそのものなので、必ず構築できます。…

XORベクトル空間のアルゴリズムとその正当性

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