「連続する整数」が多い集合を管理するデータ構造! 【備忘録】

まえがき

 AtCoder ABC194のE-"Mex Min"を解いてたら、次のお方の記事で「ある整数の集合におけるmex(minimum excluded:集合に含まれない最小の整数)を対数時間で求められるデータ構造」を知りました。

rsk0315.hatenablog.com


 他の方のコードも参考にしながら自分なりに作ってみたので、備忘録も兼ねて残しておこうと思います。



コード

 アイデアは先のブログさまのものと一緒ですのでそちらをご参考ください......!
(※考えてる範囲は閉区間です!)

/*連続する整数が多い集合を管理するデータ構造.*/
class BigSet{
    std::set<std::pair<int,int> > s;//s:整数の集合, 連続する範囲[l,r]をstd::pairで管理する.
    int inf=(1<<30);//番兵用.
    
public:
    //constructor.
    BigSet(){
        s.emplace(-inf,-inf);
        s.emplace(inf,inf);
    }
    
    bool insert(int x){//挿入. O(logN).
        auto nitr=s.lower_bound((std::make_pair(x+1,x+1)));
        auto itr=std::prev(nitr);
        auto [l,r]=*itr;
        auto [nl,nr]=*nitr;
        if(l<=x and x<=r) return false;//既に集合に含まれている場合.
        if(r==x-1){
            if(nl==x+1){
                s.erase(itr);
                s.erase(nitr);
                s.emplace(l,nr);
            }else{
                s.erase(itr);
                s.emplace(l,x);
            }
        }else{
            if(nl==x+1){
                s.erase(nitr);
                s.emplace(x,nr);
            }else{
                s.emplace(x,x);
            }
        }
        return true;
    }
    bool insert(int l,int r){//範囲[l,r]の整数を挿入. O(logN).
        assert(l<=r);
        if(l==r) return insert(l);
        auto itr1=std::prev(s.lower_bound((std::make_pair(l+1,l+1))));
        auto [l1,r1]=*itr1;
        if(l1<=l and r<=r1) return false;//完全に集合に含まれている場合.
        auto itr3=s.lower_bound((std::make_pair(r+1,r+1)));
        auto itr2=std::prev(itr3);
        auto [l2,r2]=*itr2;
        auto [l3,r3]=*itr3;
        if(l1<=l and l<=r1+1){
            if(l3==r+1){
                itr3++;
                s.erase(itr1,itr3);
                s.emplace(l1,r3);
            }else{
                s.erase(itr1,itr3);
                if(l2<=r and r<=r2) s.emplace(l1,r2);
                else s.emplace(l1,r);
            }
        }else{
            itr1++;
            if(l3==r+1){
                itr3++;
                s.erase(itr1,itr3);
                s.emplace(l,r3);
            }else{
                s.erase(itr1,itr3);
                if(l2<=r and r<=r2) s.emplace(l,r2);
                else s.emplace(l,r);
            }
        }
        return true;
    }
    bool erase(int x){//削除. O(logN).
        auto itr=std::prev(s.lower_bound((std::make_pair(x+1,x+1))));
        auto [l,r]=*itr;
        if(x<l or r<x) return false;//集合に含まれていない場合.
        s.erase(itr);
        if(l!=x) s.emplace(l,x-1);
        if(r!=x) s.emplace(x+1,r);
        return true;
    }
    bool erase(int l,int r){//範囲[l,r]の整数を削除. O(logN).
        assert(l<=r);
        if(l==r) return erase(l);
        auto itr1=std::prev(s.lower_bound((std::make_pair(l+1,l+1))));
        auto itr3=s.lower_bound((std::make_pair(r+1,r+1)));
        auto itr2=std::prev(itr3);
        auto [l1,r1]=*itr1;
        auto [l2,r2]=*itr2;
        if(itr1==itr2 and r1<l) return false;//集合に完全に含まれていない場合.
        if(l1<=l and l<=r1){
            s.erase(itr1,itr3);
            if(l1<l) s.emplace(l1,l-1);
        }else{
            itr1++;
            s.erase(itr1,itr3);
        }
        if(l2<=r and r<r2) s.emplace(r+1,r2);
        return true;
    }
    bool contains(int x) const{//集合に整数xが含まれるか判定する. O(logN).
        auto [l,r]=*std::prev(s.lower_bound((std::make_pair(x+1,x+1))));
        return (l<=x and x<=r);
    }
    int mex(int x=0) const{//Minimum Excluded. x以上であって,集合に含まれない最小の整数を求める. O(logN).
        auto [l,r]=*std::prev(s.lower_bound((std::make_pair(x+1,x+1))));
        if(l<=x and x<=r) return r+1;
        else return x;
    }
    void print() const{
        for(const auto &[l,r]:s) fprintf(stderr,"[%d,%d]",l,r);
        std::cerr<<std::endl;
    }
};
あとがき

 一応確認しましたがバグってたら教えてくださると有難いです。

拡張フィボナッチ数列の任意の項までの和を高速に求める方法の考案

 暑い日が続いていますね...。最近2025大阪万博のロゴが気になってます。


 今回は掲題の内容について、高校数学の知識から実用的な(?)プログラムができたので紹介したいと思います。

 少し長くなりますがお付き合いください。

(未熟者ですので細かい点において誤った情報になっている可能性があります。もしお気づきの方がいらっしゃいましたら、ご指摘していただけると助かります。)

まえがき

 フィボナッチ数列とは「前にある2つの数を足した数の列」で、

 
\begin{cases}
f_0 = 0,  f_1 = 1\\
f_k = f_{k-1} + f_{k-2}  (k \geq 2)
\end{cases}

と定義されます。

 他にも前3つの数を足していくトリボナッチ数列や、前4つを足していくテトラボナッチ数列などがあります。


 ところでフィボナッチ数列 k番目の項までの和については、


 
\begin{eqnarray}
\sum^k_{i=0} f_i = f_{k+2} - f_1 = f_{k+2} - 1
\end{eqnarray}


という1つの一般項から導出できることが知られています。この式の求め方についてはこちらの他の方のブログをご覧ください。


 私は先日、
「この式の考え方を応用したらトリボナッチ数列やテトラボナッチ数列でも同じような式が書けるんじゃない?!」
という発想に至り、一般化した式を導出しました。Σ(゚Д゚)スゲェ!!



概要 ~数列の定義と“和の式”~

 以下の文章から足す数の個数を n, その数列を A(n)=\{a_0, a_1, a_2, ......\}とします。

拡張フィボナッチ数列 A(n)の定義

 すると数列 A(n)は、

 
\begin{cases}
a_0 = a_1 = ...... = a_{n-2} = 0\\
a_{n-1} = 1\\
a_k = a_{k-1} + a_{k-2} + ...... + a_{k-n}   (k \geq 2)
\end{cases}

と定義できます。

数列 A(n)の任意の項までの和の式

 このとき、数列 A(n) k番目の項までの和は



\begin{eqnarray}

\sum^k_{i=0} a_i = \frac{ a_{k+n} - a_{n-1} -\begin{eqnarray} \sum^{n-3}_{j=0} \{ (j+1)(a_{k+n-2-j} - a_{n-3-j}) \}\end{eqnarray} }{n-1}

\end{eqnarray}


と表現できます。これが今回私が導出した式です!

 この式のすごいところは、 k+1個の一般項の和の式が、僅か 2+2(n-2)個の一般項のみから導き出せる」ということです!



式の導出と証明

 タイプが面倒くさかったので自分が導出したときのメモを張っておきます(自我乱れて見づらいですが...)

 数学的帰納法で証明しました。(途中 n=3, 4, 5について書いていますが蛇足なので読み飛ばしてください。)




完成したプログラムFibonacci(C++

 以下が作ったプログラムです(個人色強いプログラムですがご了承ください)。オーダー記法も自信がないので参考程度にお願いします。

#include <vector>
#define REP(i,n) for(int i=0;i<(n);++i)

/*フィボナッチ数列
(数列の定義は,{F(0)=...=F(n-2)=0, F(n-1)=1. F(k)=F(k-n)+F(k-(n-1))+...+F(k-2)+F(k-1).})*/
class Fibonacci{
	using llong = long long;
	using vl    = vector<llong>;
	using vvl   = vector<vl >;
	const int mod=1e9+7;
	const int n;	//n:=(前にある足す数の個数). (2以上にすること! 約100以下が実用的?)
	vvl a,b;		//a:=(n*n行列A), b:=(1*n転置行列(F(n-1),.....,F(0))').
	
	vvl mul(vvl &x,vvl &y){//n*n行列xとyの積をとる. O(n^3).
		vvl res(x.size(),vl(y[0].size(),0LL));
		if(x[0].size()==y.size()){
			REP(i,x.size())REP(j,y[0].size())REP(k,x[0].size()){
				res[i][j]=(res[i][j]+x[i][k]*y[k][j]%mod+mod)%mod;
			}
		}
		return res;
	}
	llong mod_pow(llong n,llong k){//n^k(mod p). O(log K).
		if(k==0LL) return 1LL;
		llong res=mod_pow(n*n%mod,k/2);
		if(k&1LL) res=res*n%mod;
		return res;
	}
	
public:
	Fibonacci(unsigned int n_=2):n(n_),a(n,vl(n,0LL)),b(n,vl(1,0LL)){//constructor.
		REP(i,n) a[0][i]=1LL;
		REP(i,n-1) a[i+1][i]=1LL;
		b[0][0]=1LL;
	}
	
	int fibonacci(unsigned long long k){//フェボナッチ数列のk項目を求める. O((n^3)*log(i)).
		if(k<n-1) return 0;
		if(k==n-1) return 1;
		vvl aa=a, res=b;
		while(k>0LL){
			if(k&1LL) res=mul(aa,res);
			aa=mul(aa,aa);
			k>>=1;
		}
		return res[n-1][0];
	}
	/*フェボナッチ数列のk項目までの和を求める. O((n^4)*log(i)).
	(Σ(0~k)F(i)=[F(k+n)-F(n-1)-Σ(0~n-3){(j+1)(F(k+n-2-j)-F(n-3-j))}]/(n-1)より.)*/
	int sum(unsigned long long k){
		llong res=((llong)fibonacci(k+n)-fibonacci(n-1)+mod)%mod;
		llong tmp=0LL;
		for(int j=0;j<=n-3;++j){
			llong tmpp=(j+1LL)*(((llong)fibonacci(k+n-2-j)-fibonacci(n-3-j)+mod)%mod)%mod;
			tmp=(tmp+tmpp)%mod;
		}
		res=(res-tmp+mod)%mod;
		res=res*mod_pow(n-1,mod-2)%mod;//逆元.
		return (int)res;
	}
};

構造体Fibonacciの説明

前説明

 基本的なアイデアは行列を用いています。

 項が増えると数がとても大きくなるので、素数の1,000,000,007でmodとっています。

  nの値の定義はコンストラクタの部分で行います(2未満だとバグります)。このプログラムではサイズ n^2の配列が必要となったり、 O(n^3)の計算があったりするので大きすぎる値は注意が必要です。

機能説明

 この構造体の主な機能は、数列 A(n)における

  1. 任意の項の数の取得( 関数fibonacci() ).
  2. 任意の項までの和の取得( 関数sum() ).

の2つです。
 

 関数fibonacci()は行列の考え方を利用しています(Wikipedia)。行列の積の計算では最悪 O(n^3)となりますが、繰り返し二乗法のような(?)考え方を使うので全体的に O(n^3*log (k))です(要再考!)。

 関数sum()は今回考案した考え方を利用して計算しています。sum()内ではfibonacci()を 2+2(n-2)回呼出しです。ですので計算量は大体 O(n^4*log (k))となります(要再考!)。

 つまり、 nが大きかったり項が小さい場合は愚直に調べたほうがいいかもしれません。が、求めたい項が大きい場合は有効です。



メリット・有用性

 今回考案した式の有効な場面について再度説明します。

 もし 0項目から k 項目まで数を求めて足していくということをすると、計算量は O(k * n^3 * log(k))となります(要再考!)。

 対して今回の計算量は O(n^4*log (k))です(要再考!)。

 つまり、「 nが小さく、 kが大きい」というときにより早く計算できるということになります。

実行時間の検証

 次の2つの方法において、任意の項までの和を求めるのにかかる実行時間を計測して比較します。

  1.  0項目から k 項目まで数を求めて足していく.
  2. 考案した式を用いる.

 私が試した結果は以下のようになりました。(単位は[ms]です。)

 n  k(項番号) 手法1(愚直) 手法2(新)
2 100 30.0 0.0
3 100 50.3 0.0
10 100 319.2 50.3
100 1000 (not) 354953.2
2 10000 2334.9 0.0
3 10000 46009.3 0.0
10 10000 (not) 0.0

 初めて比較計測したので正しくできているかはわかりませんが、実感でも新手法が早かったと思います。



参考文献

あとがき

 正直これ正しいのかという不安や実用性の懸念もありますが、久しぶりにイチから(いろいろ参考にしながらも)プログラムを作るのが楽しかったです。

 また冒頭でも述べたように、誤った記述があるかもしれません(もしかしたらこの記事全体が間違っているかもしれません)。もし何か気付いたという方がいらっしゃいましたら、コメント機能やツイッターにて知らせていただけると有難いです。

 あと記事を引用などする場合はリンクやタイトルなどの明示をお願いいたします。

マイ競プロ用テンプレートの紹介

 最近長めの梅雨が明けて, 日差しがきつくなりましたね...。




 この記事では自分の競技プログラミングで使うテンプレートを紹介したいと思います。

 実は記事を書いてる日のお昼に我ながら出来のいい「forマクロ」を考案(たぶん既出)したので布教したいと思って書き始めました。


 まず下記がマイテンプレートです。

#include <bits/stdc++.h>
#define REP(i,n)   for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(long long i=(a);((a)>(b)?i>=(b):i<=(b));((a)>(b)?--i:++i))
#define ALL(v)     (v).begin(),(v).end()
#define debug(x)   cerr<<#x<<": "<<(x)<<endl
#define INF        (int)1e9
#define EPS        (double)1e-9
#define MOD        ((int)1e9+7)
using namespace std;
typedef long long     llong;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
typedef pair<int,int> pii;
template<class Type>
void line(const Type &a){int cnt=0;for(const auto &elem:a){cerr<<(cnt++?' ':'>');cerr<<elem;}cerr<<endl;}

 ではいくつかお気に入りのやつを紹介していきます。


1. FOR(i, a, b)

#define FOR(i,a,b) for(long long i=(a);((a)>(b)?i>=(b):i<=(b));((a)>(b)?--i:++i))

 これがおニューのforマクロです!  aから b間の整数に iが更新されていきます。ポイントは「 a < bでも a > bであってもよい」ということです!

 今までも以下のようなforマクロを導入しようかと思ったのですが, 大した利便性がないと思って避けていました。

#define FOR(i,a,b)  for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)

 しかし今回のマクロは, 条件演算子 a bの大小を比較しており,  iの遷移が増加したり減少したりします。この特徴は幅広い場面で使えると思います! ぜひ皆さんもお使いください!


2. REP(i, n)

#define REP(i,n) for(int i=0;i<(n);++i)

 他の方も多く使われているrepマクロです。「特定の処理を n回繰り返したい」というときとかに使い, 利用頻度多めです。


3. ALL(v)

#define ALL(v) (v).begin(),(v).end()
vector<int> v={6,1,8,2,0};
//sort(v.begin(),v.end());	//長い...
sort(ALL(v));			//短くて良き...!

 これも多くの人が使われていますね。ソートとかするのに簡潔に書けるのでよく使います。


4. debug(x), line(a)

#define debug(x)   cerr<<#x<<": "<<(x)<<endl
template<class Type>
void line(const Type &a){int cnt=0;for(const auto &elem:a){cerr<<(cnt++?' ':'>');cerr<<elem;}cerr<<endl;}

 デバック用のマクロと関数です。line関数はvectorなどの中身を列挙します。標準エラー出力にすることでデバックを消し忘れたときにもWAしません!(AtCoderだけ?)


5. llong

typedef long long llong;

 (個人的な意見ですが, " ll "だとなんだか物足りないです...。)




 他にも説明していないものもありますが, 他の方のテンプレートにもあるので省略させてもらいます。ぜひ紹介したforマクロ試してみてください!

 ではでは......。

『コンビニアイス』

 金曜日の夜、男は仕事から帰ってきてマンションのドアを開けた。ようやく一週間の勤務が終わり、程よい疲れとともにアイスの入ったコンビニ袋を持って充実感に満ちていた。

 買ったアイスはパルム。ハーゲンダッツを除くと男が最も好むアイスであった。バニラの周りに薄く、けど濃厚なチョコレートがコーティングされたものである。

 風呂から上がり、冷蔵庫からパルムとミルクを取り出す。そしてクーラーの効いた部屋でそれを食しながら、レコーダーに撮りためたドキュメンタリー番組を観る。

 男はそのひと時、外の熱気を忘れるのである——。

 

(完)

 

 

 

 あとがき。

 いきなり変な小説を投稿して驚かせてしまいました......。実は今日自分の誕生日プレゼントとしてアマゾンで注文していたキーボードが届いて、キーストロークを確かめるために少し長めの文章を書いたらこのショートストーリができてしまったという具合です。起承転結も深い意味もない話です。

 キーボードについては気が向いたら紹介出来たらなと思います。ちなみにアーキスというメーカのメカニクルキーボードです(赤軸)。はじめクセあるなと思ったんですが、慣れると使い心地がよいです。

 ではまた......。

Ubuntu 18.04 LTS で作業する前に行う準備

 今回は、前回仮想マシンにインストールしたUbuntu 18.04を使いやすく設定していきます。


表示画面(画面の幅)を合わせる

 初めは下の画像のように表示画面が小さいので、これを自分のPCの画面の幅に合わせます。

f:id:today_f:20191202203234p:plain:w350

  • VirtualBox側のメニューバーにある[デバイス]から「Guest Additions CDの挿入...」をクリック。
  • 表示された「実行」をクリック。

f:id:today_f:20191203104834p:plain:w250


 これで以下のようにぴったりになります。

f:id:today_f:20191203104739p:plain:w350

 さらに全画面にしたい場合は[表示]から「フルスクリーンモード」を選択します。


日本語入力を有効にする

 テキストで日本語入力する方法を紹介します。

  • 右上のメニューから下の画像のように「日本語(Mozc)」を選択し、入力モードを「ひらがな」を選択。

 これで日本語入力できます。次はショートカットで英語と切り替えられるようにします。

  • 右上のメニューから「日本語(Mozc)」→[ツール]→[プロパティ]と選択していき、「キー設定の選択」の[編集]をクリック。
  • 「入力キー」の列から「Ctrl Space」のエントリーをすべて削除(他のショートカットと被らないようにする)。
  • 「Hankaku / Zenkaku」をすべて「Ctrl Space」に変更する。

 以上で[Ctrl + Space](ここはお好みです)のショートカットにより入力モードを変更できます(もし変更できない場合は再起動を試してみてください)。


manコマンドで表示されるものを日本語にする

 デフォルトでは英語表記です。日本語にしたい人は以下のようにコマンドを打ち、必要なツールをインストールします。

$ sudo apt install manpages-ja
$ sudo apt install manpages-ja-dev

 これで日本語表記のマニュアルが読めるはずです。もし英語で読みたくなったら以下のコマンドで見れると思います。

$ LANG=C man [コマンド名]

共有フォルダの作成

 ホストOSとゲストOS間でファイルなどを共有したいときに便利です。

  • VirtualBox側のメニューから[仮想マシン]→[設定]→[一般]→[高度]に進み、「クリップボードの共有」の欄を「双方向」にする.
  • ホストOS側に共有するフォルダを作成する.
  • 仮想マシン]→[共有フォルダ]に進み、共有するフォルダのパスを入力.
  • [自動マウント]と[永続化する]にチェック.

 これで指定したフォルダを通して、ファイルを共有できます。もし共有フォルダが見れないという場合は以下のコマンドを入力してみてください。

$ users
$ sudo su -
$ sudo gpasswd -a [カウント名] vboxsf

 そして再起動します。これで大丈夫なはずです。


ファイアーウォールを設定する

 以下のサイトなどをご参考ください。

ファイアーウォールの設定をする - Ubuntu 18.04編
Ubuntuのファイヤーウォール「ufw」 - JavaScript勉強会


フォントを変更する

 フォントの大きさが小さく、変更したかったので調べてみました。以下のコマンドから「Tweaks」というソフトをインストールします。

$ sudo apt install gnome-tweaks

 入手したTweaksでは様々なことが設定できるので試してみてください。

f:id:today_f:20191213121402p:plain:w300


vimemacsなどのテキストエディタをインストール

$ sudo apt install vim

$ sudo apt install emacs

 インストールできたかは以下のコマンドで確認。

$ dpkg -l [pattern]

gccやg++などをインストール

 build-essentialというビルドツールを提供してくれるパッケージがあるそうです。

$ sudo apt install build-essential

スクリーンショットのショートカットを有効にする

 初期状態ではキーボードの[Ptr Sc]が使えませんでした。いろいろ試してみると、以下のコマンドを入力することで使えるようになりました(正しい方法かは知りませんが......)。

$ gnome-screenshot

 これでショートカットでスクリーンショットがとれます。ショートカットの組み合わせで様々な形式でとれますので、調べてみてください。





以上。



#日差しが暖かい金曜日

VM(VirtualBox)にLinux系OS Ubuntu 18.04をインストールする

 先日学校でLinuxでのプログラムを作る課題が出たのですが、自分のPCはWindowsでした。
 
 先生(放任的)にはVM(Virtual Machine)を使って仮想環境を構築することを勧められたのですが、正直初心者の自分には難しく、「作っては壊し、作っては壊し」を繰り返し3日以上かかりました......。

 今回は忘れないための自身の記録として、また同じ状況の方の参考にしていただければとこの記事を書こうと思います。



VM(Virtual Machine)とは?

 文字通り仮想機械で、仮想的にコンピュータを作って動作させることができます。今回はこのVMLinux系のOSをのっけて使っていこうということです。


環境

 紹介する環境は以下のものです。(他にもCentOSVMwareなどいろいろあるそうなのでそちらを使ってもいいかもです。)


手順

  1. UbuntuVirtualBOXの用意(ダウンロード).
  2. VitualBoxのインストール.
  3. VirtualBoxを使って仮想マシンを作って、その上にUbuntuをインストールする.


ダウンロード

 まずはネットからUbuntu 18.04のインストーラISOイメージとVirtualBoxをダウンロードしてきます。それぞれUbuntu Japan TeamOracleのサイトから入手可能です。ダウンロードは比較的簡単なので割愛します。


VirtualBoxのインストール

 ダウンロードしたVirtualBoxをインストールします。ここも意外と簡単です。割愛します。


仮想マシンの作成

 VirtualBoxを起動して、仮想マシンを作ってUbuntuをインストールします。ここが個人的に迷子になり難解でした......。

  • メイン画面にある[新規]ボタンをクリック。
  • 以下のような画面が出てきます。“名前”は適当に入力して、“タイプ”は「Linux」、“バージョン”は「Ubuntu(64-bit)」を選択。

f:id:today_f:20191201175542p:plain:w300

  • 次は“メモリーサイズ”。デフォルトでは1024MBですが自分の場合はこの後重くなったので大きめに取っておくのがいいと思います。

f:id:today_f:20191201181649p:plain:w300

  • “ハードディスク”では「仮想ハードディスクを作成する」にチェックを入れる。
  • “ハードディスクのファイルタイプ”には「VDI」にチェック。
  • “物理ハードディスクにあるストレージ”では「可変サイズ」にチェック。こっちのほうが効率がいいそうです。
  • “ファイルの場所とサイズ”。ファイルの場所は任意。サイズもデフォルトの10.00GBでよいと思います。
  • [作成]ボタンをクリック。
  • メイン画面の[設定]から「ストレージ」に進む。
  • “コントローラ: IDE”のところが「空」となっているので、そこに先ほどダウンロードしたUbuntu のISOイメージを選択します。

f:id:today_f:20191202184022p:plain:w300


 次は作った仮想マシンを起動します!


Ubuntuのインストール

  • メイン画面の[起動]をクリック。
  • “Welcome”のところでは日本語を選択して、[Ubuntuをインストール]をクリック。
  • “キーボードレイアウト”では自身のPCのキーボードの型を選択。もし「US」や「UKキーボード」などでしたらそう選択しましょう。
  • “アップデートと他のソフトウェア”。デフォルトの選択で良いと思います。
  • “インストールの種類”。ここではセキュリティをかけれるみたいです。今回は学習目的なので特にデフォルトで良いと思います(多分)。
  • [インストール]をクリック。
  • “住んでるところ”もデフォルトの「Tokyo」。
  • 任意の“名前”と“パスワード”を入力。


 以上でインストールが開始されます。少し時間がかかると思います。

 以下の画面になるので再起動します。

f:id:today_f:20191202192242p:plain:w300


 再起動するとログイン画面になるので、先ほど設定したパスワードを入力して利用開始しましょう。

 (初めいくつか設定やアップデートがあると思います。しましょう。)


 次の記事で、Ubuntu仮想マシンを使いやすくするための様々な設定について書いていこうと思います。



#師走

Union-Find木について<実践編>

 またまた日が空きました.......。


 前回は「Union-Find木」の内容を紹介しました。

today-f.hatenablog.jp


 今回は実際にAtCoderでUnion-Find木を用いて問題を解いてみたいと思います。



問題

 AtCoder ABC120のD問題。(この問題で初めてUnion-Find木に出会いました。)

atcoder.jp



解法

  {N}個の島と {M}本の橋があって、この橋が順番に崩落した際のその時その時の”行き来できない島と島の組み合わせ”=”不便さ”を求める問題ですね。


 これは時間の流れを逆にして考えるのだそうです。

 どの島同士もつながっていない状態から入力の逆順に橋をつなげていくことで、Union-Find木の「グループの結合」という特徴を利用することができるのです。


 まずはじめの状態においてどの島も孤島ですから、”不便さ”は  {_n C _2}


 次に {i}回目に橋を架けるとき、架ける島と島がもう別の橋から行き来できる場合は不便さは変わらないので、 {i-1}回目に橋を架けた際の不便さと同じです。

  {i}回目で初めて2つの島が行き来できるようになる場合は、それぞれの島が属するグループの総数の組み合わせですから求める不便さは、

( {i-1}回目のときの不便さ)ー(島1のグループのサイズ)*(島2のグループのサイズ)

となります。



実装
 
 C++でのコードは以下のようになりました。

#include<iostream>
#include<vector>
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long   llong;
typedef vector<int> vi;

struct UnionFind{
	std::vector<int> par;
        /*xの親はpar[x]. 
        もしx自身が親ならpar[x]<0で,-par[x]がその集合のサイズ.*/
	int cnt;//グループの数.
	
	UnionFind(int n):par(n,-1),cnt(n){}//コンストラクタ.
	
	void reset(int n){par.assign(n,-1),cnt=n;}
	int root(int x){return (par[x]<0)?x:par[x]=root(par[x]);}
        /*再帰.*/
	int size(int x){return -par[root(x)];}
	bool same(int x,int y){return root(x)==root(y);}
	bool unite(int x,int y){
		x=root(x), y=root(y);
		if(x==y) return false;//do nothing.
		if(size(x)<size(y)) swap(x,y);//merge technique.
		par[x]+=par[y];
		par[y]=x;
		cnt--;
		return true;
	}
};

int main(){
	int n,m;
	cin>>n>>m;
	
	vi a(m),b(m);
	REP(i,m){
		cin>>a[i]>>b[i];
		a[i]--, b[i]--;
	}
	
	UnionFind is(n);
	vector<llong> ans(m);
	ans[m-1]=(llong)n*(n-1)/2;//nC2.
	for(int i=m-1;i>=1;--i){
		if(is.same(a[i],b[i])) ans[i-1]=ans[i];
		else{
                ans[i-1]=ans[i]-(llong)is.size(a[i])*is.size(b[i]);
                }
		is.unite(a[i],b[i]);
	}
	
	REP(i,m) cout<<ans[i]<<endl;
}

 以上がUnion-Findを使った例でした。理解すると構造体の仕組みに感動して、使うのがなかなか面白かったです。



#寒くなってきた夜