hogloidのブログ

へなちょこ

Codeforces #165 div1-D Maximum Waterfall

CF

http://www.codeforces.com/contest/269/problem/D

問題概要

高さ、左端、右端の決まった棚がN個ある。
i番目の棚の高さ、左端、右端をそれぞれhi,li,riとおく。

ある棚iから、ある棚jに水を流せる時、

  • max(li,lj)＜min(ri,rj) つまり棚iと棚jが上から見た時重なっていて、
  • hj＜hi で
  • 棚iから棚kに水を流せて、棚kから棚jへ水を流せるようなkが存在しない

という3つが満たされている。

ある棚iからある棚jに水を流すとき、流せる量は、min(ri,rj)-max(li,lj)

最も上の長さが無限の棚から、最も下の長さが無限の棚に、なるべく多く一本の水を流したい
水を流す経路の流量は、棚から棚へ流せる水の量の最小値

流せる水の最大値を求めよ

N<=10^5
|li,ri|<=10^9
hi<=10^9




















方針

左右の座標の値をまずは圧縮

棚を下から順番に見ていく
dp[i]:=棚iから水を流すときの流せる水の最大値

棚iの範囲で、棚iより下の棚たちを見下ろした時に見える棚(棚jとおく)すべてについて、
棚jに棚iから水を下ろせるか考える。

棚jに水を下ろせるのは、棚iの範囲とかぶっている棚jの範囲がすべて見えるとき
この時、dp[i]=max(dp[i],min(dp[j],(iとjの被っている部分の長さ)))
と更新できる。

更新が終わったら、上から見た時に見える棚に棚iを追加する
上から見た時に見える棚の管理には、set＜pair＜int,int> >などを使えばできる

dp[最も上の棚の番号] が答え

棚iから下へ見える棚は最大N個有りそうなので、O(N^2)かO(N^2logN)のような気がするが、
もしある区間を見下ろせたなら、その区間はiによって覆われるので棚iによってしか見下ろされない
更新が終わると、棚iの区間、棚iの両側にもともとあり、途切れることとなった区間 の3つが追加される

区間は1回しか見下ろされないので、O(N * logN)ぐらいで終了する。





下のコードのdoitは、上の方針と少し違い、
[l,r)の範囲で最も上にある区間をセグメント木により探し、その区間で更新できるか調べ、
最も上にある区間以外の残りの範囲について再帰的に調べています

実装量は多いですが挿入削除の面倒なことが少ないかと思います

using namespace std;
static const int INF =1000000005;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
typedef long long int lint;
typedef pair<int,int> pi;
struct segtree{
	int val[800005],all[800005];
	int n;
	void init(int n_){
		n=1;
		while(n<n_) n<<=1;
		for(int i=0;i<n*2;++i) val[i]=-1,all[i]=-1;
	}
	int query(int a,int b,int i,int l,int r){
		if(a<=l && r<=b) return val[i];
		if(b<=l || r<=a) return -1;
		int md=(l+r)>>1;
		if(all[i]!=-1){
			all[i*2+1]=all[i*2+2]=val[i*2+1]=val[i*2+2]=all[i];
			all[i]=-1;
		}
		return max(query(a,b,i*2+1,l,md),query(a,b,i*2+2,md,r));
	}
	void set(int a,int b,int i,int l,int r,int v){
		if(a<=l && r<=b){
			val[i]=v;
			all[i]=v;
			return;
		}
		if(b<=l || r<=a) return;
		int md=(l+r)>>1;
		if(all[i]!=-1){
			all[i*2+1]=all[i*2+2]=val[i*2+1]=val[i*2+2]=all[i];
			all[i]=-1;
		}
		set(a,b,i*2+1,l,md,v);
		set(a,b,i*2+2,md,r,v);
		val[i]=max(val[i*2+1],val[i*2+2]);
	}
};
segtree seg;
pair<int,pi> wall[100005];
int zip[200005];
int n,t;
int dp[100005];

void doit(int l,int r,int who,int excL=1,int excR=1){
//excL/excR 左/右に伸びていてよいかどうか(1ならOK)
	int id=seg.query(l,r,0,0,seg.n);
	if(id==-1){//最も下の棚専用
		seg.set(l,r,0,0,seg.n,who);
		dp[who]=zip[r]-zip[l];
		return;
	}
	int l2=wall[id].second.first,r2=wall[id].second.second;
	if(!(l2<l && excL==0) && !(r<r2 && excR==0)){
		dp[who]=max(dp[who],min(dp[id],min(zip[r],zip[r2])-max(zip[l],zip[l2])));
	}

	if(l<l2) doit(l,l2,who,excL,0);
	if(r2<r) doit(r2,r,who,0,excR);
}

int main(){
	scanf("%d%d",&n,&t);
	for(int i=0;i<n;++i){
		int a,b,h;scanf("%d%d%d",&h,&a,&b);
		zip[i*2]=a;
		zip[i*2+1]=b;
		wall[i]=make_pair(h,make_pair(a,b));
	}

	zip[n*2]=-INF;
	zip[n*2+1]=INF;
	sort(zip,zip+n*2+2);
	int zn=unique(zip,zip+n*2+2)-zip;
	wall[n++]=make_pair(0,make_pair(-INF,INF));
	wall[n++]=make_pair(t,make_pair(-INF,INF));
	for(int i=0;i<n;++i){
		wall[i].second.first=lower_bound(zip,zip+zn,wall[i].second.first)-zip;
		wall[i].second.second=lower_bound(zip,zip+zn,wall[i].second.second)-zip;
	}
	sort(wall,wall+n);

	seg.init(zn);
	for(int i=0;i<n;++i){
		int h=wall[i].first,l=wall[i].second.first,r=wall[i].second.second;

		doit(l,r,i);
		seg.set(l,r,0,0,seg.n,i);
	}
	printf("%d\n",dp[n-1]);


	return 0;
}

Codeforces #165 div1-C,div2-E Flawed Flow

CF

http://www.codeforces.com/contest/269/problem/C

問題概要

N頂点、M辺のグラフが与えられ、頂点1がソース、Nがシンクである
ソースからシンクへの最大フローを流した時の、辺に流れた流量が辺ごとに与えられる(向きは与えられない)
フローが成り立つようにそれぞれの辺について向きを決めよ
ただし、得られるフローはサイクルを含んではいけない
グラフは連結で、答えは必ず存在する

N,M<=2*10^5
1<=流量<=10^4






















方針

サイクルを含まないので、得られるフローのグラフは、トポロジカル順序をつけることが出来る。
ソースは最も順序の早い点で、そこから出る辺はすべてソースと逆向きに流れている
ここで、ソースに隣接する点のうち、どれかはトポロジカル順序がソースの次に小さいはずである
トポロジカル順序がソースの次に小さい頂点をvと置くと、vにはソース以外からフローが流れこまないので、
ソースから向かう辺の流量と、それ以外のつながれた辺の流量が等しいはず
逆に、ソース->vの辺以外はvから流れださなければフローが成立しないので、
ソースの時と同様にvから流す

残った頂点の中でトポロジカル順序が最も早いものが必ず見つかるはずなので、これを繰り返せば答えが求まる。

ソース、シンクの扱いに注意

O(N+M)

using namespace std;
static const int INF =500000000;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
typedef long long int lint;
typedef pair<int,int> pi;
int n,m;
vector<pair<pi,pi> > g[200005];
int in[200005],flow[200005];
int vis[200005];
int ans[200005];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);--a;--b;
		g[a].push_back(make_pair(make_pair(b,c),make_pair(0,i)));
		g[b].push_back(make_pair(make_pair(a,c),make_pair(1,i)));
		flow[a]+=c;
		flow[b]+=c;
	}

	memset(ans,-1,sizeof(ans));

	queue<int> q;q.push(0);
	while(!q.empty()){
		int v=q.front();q.pop();
		vis[v]=1;
		for(int i=0;i<g[v].size();++i){
			pair<pi,pi>& e=g[v][i];
			if(vis[e.first.first]) continue;
			in[e.first.first]+=e.first.second;
			ans[e.second.second]=e.second.first;
			if(in[e.first.first]==flow[e.first.first]/2 && e.first.first!=n-1) q.push(e.first.first);
		}
	}


	for(int i=0;i<m;++i) printf("%d\n",ans[i]);





	return 0;
}

Codeforces #165 div1-A,div2-C Magical Boxes

CF

http://www.codeforces.com/contest/269/problem/A

問題概要

N種類の大きさの箱がある。
i番目の箱の大きさは2^k(i)で、a(i)個ある。

新しく2^pの大きさの箱を作って、それにすべての元の箱を詰めたい。
ある箱には、それより小さい大きさの箱を、半分の大きさなら4個、1/4の大きさなら16個、というように詰めることができ、入れ子状に詰めることも出来る。
ある箱に、サイズの異なる箱を詰めることも出来る(半分の大きさの箱1つ、1/4の大きさの箱12個 のように)
pの最小値を求めよ



N<=10^5 a,k<=10^9

















方針

ある箱が入れ子状に詰められているとしても、
サイズごとに、互いに干渉しない箱を別々に新しい箱に詰めている、とみなすことができる
なので、それぞれのサイズについて、箱を詰めることが出来る最小のサイズを求め、maxを取る。
サイズ2^k(i)のa(i)個の箱が詰まる最小のサイズは、2^(p-k(i))>=a(i)を満たす最小のp
ただし、p>k(i)

O(N*log a)


int n;
pair<int,int> box[100005];
int main(){
	cin>>n;

	int res=0;
	for(int i=0;i<n;++i){
		scanf("%d%d",&box[i].first,&box[i].second);
		
		if(box[i].second==1) res=max(res,box[i].first+1);
		else{
			while(box[i].second>1){
				box[i].second=(box[i].second+3)/4;
				++box[i].first;
			}
			res=max(res,box[i].first);
		}
	}
	printf("%d\n",res);

	return 0;
}

POJ Solved Graph

自作プログラム

PKUのアカウントのsolvedを横軸時間、縦軸solvedのグラフにして表示します。

複数アカウントに対応しています。名前を入れるところに、コロン(',')区切りで空白などを入れずに複数のアカウントを入力してください

 

ボタンを押すと、その時のウィンドウのサイズに合わせてグラフを作ります

ページ読み込みに結構時間がかかるので、マッタリ待ちましょう。合計solvedが4000とか行くようだと1分弱かかります

同じディレクトリに、page.htmlというファイルを作りますが気にしなくていいです。プログラムを終了したら削除しても問題無いです

 

サイズを変更すると勝手に大きさを変えてくれます

 

Windows用です また、.NET Framework 4が必要です

リンク：

https://docs.google.com/open?id=0B4bMtJgy4TSHZzR2RU5BWGNTQzQ

 

グラフの例：

f:id:hogloid:20130108160544p:plain

 

Last updated:2013/1/9

制作言語はC#です

セグメント木 問題集

コンテスト系その他

https://twitter.com/hogloid/status/284225774142251008
こんなことを言ったので
書きます
問題は、セグメント木を使う解法がおそらく楽で、セグメント木が問題の重要な部分で、JOIとかPCKでない問題、とします（JOIの問題とかみんな知ってる&解いてるだろうし）
あと、明確に悪問と分かる問題は載せません。

解説が欲しい場合は、(一応僕は全部解いたので)僕になにか言ってくれると解説ページを開設すると思います。下のコメント欄とかにどうぞ。
記事を出してからも、ボチボチ更新していく予定です。
☆の数は、主観的な難易度です。

書き終わって気づきましたがかなりグロイ問題ばかりなのでやばいですが頑張ってください

似たような記事 http://d.hatena.ne.jp/tozangezan/20111111/1320993464
(こっちのほうが、おそらく簡単な問題が多いです 問題はかぶってないはずです)

☆

☆☆

☆☆☆

☆☆☆☆

☆☆☆☆☆

Codeforces #157 div1E Little Elephant and Tree

CF

URL:http://www.codeforces.com/contest/258/problem/E

問題概要

N頂点からなる全域木がある。根は頂点1。
それぞれの頂点はあるリストを持っている。
M回処理をする。i番目の処理は、
頂点uiより下の部分木、頂点viより下の部分木 の頂点すべてのリストに、数iを入れる。

処理が終わったら、それぞれの頂点について、
自分以外の頂点で、リストに一つでも同じ数を含む頂点の数を求めよ。
N<=100000














方針

segtreeで解けます。

ある頂点xとリストに同じ数を含む頂点は、xの子孫とも同じ数を含む、ということに注意。
まず、euler-tourをして、segtreeを建てます。
それぞれの頂点で、処理のui,viのどちらかになっているなら、もう片方の頂点の部分木の範囲に+1します。
また、自分の頂点の部分木にも+1します。
それぞれの頂点で、segtreeの列の上で正の数を持っている要素の数を求めます。
これが、同じ数をもつ頂点に対応します。
ただし、値が正になったら必ず自分を含んでいるので-1します

上の処理は、segtreeがそれぞれのノードで、
「子に伝播させていない変更」「区間の最小値」「区間の最小値を取る要素の数」
を覚えれば、なんとかできます。

O(NlogN)

using namespace std;
static const int INF =500000000;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
typedef long long int lint;
typedef pair<int,int> pi;
struct segtree{
	int n,n2;
	int val[400005],mini[400005],lazy[400005];
	void init(int n_){
		n2=n_;
		n=1;
		while(n<n_) n<<=1;
		for(int i=0;i<n_;++i){
			mini[i+n-1]=0;
			val[i+n-1]=1;
		}
		for(int i=n-2;i>=0;--i){
			mini[i]=0;
			val[i]=val[i*2+1]+val[i*2+2];
		}
	}
	void add(int a,int b,int i,int l,int r,int v){
		if(a<=l && r<=b){
			lazy[i]+=v;
			mini[i]+=v;
			return;
		}
		if(b<=l || r<=a) return;
		int md=(l+r)>>1;
		if(lazy[i]){
			lazy[i*2+1]+=lazy[i];
			mini[i*2+1]+=lazy[i];
			lazy[i*2+2]+=lazy[i];
			mini[i*2+2]+=lazy[i];
			lazy[i]=0;
		}
		add(a,b,i*2+1,l,md,v);
		add(a,b,i*2+2,md,r,v);
		mini[i]=min(mini[i*2+1],mini[i*2+2]);
		val[i]=0;
		if(mini[i]==mini[i*2+1]) val[i]+=val[i*2+1];
		if(mini[i]==mini[i*2+2]) val[i]+=val[i*2+2];
	}
	int query(){
		if(mini[0]==0) return n2-val[0];
		return n2;
	}
};
segtree seg;
int n,m,cnt;
int begin[100005],end[100005];
vector<int> g[100005];
void dfs(int v,int p){
	begin[v]=cnt++;
	for(int i=0;i<g[v].size();++i){
		int to=g[v][i];
		if(to==p) continue;
		dfs(to,v);
	}
	end[v]=cnt;
}

vector<int> connect[100005];
int ans[100005];
void dfs2(int v,int p){
	for(int i=0;i<connect[v].size();++i){
		int to=connect[v][i];
		seg.add(begin[to],end[to],0,0,seg.n,1);
	}
	ans[v]=seg.query();
	if(ans[v]>0) --ans[v];
	for(int i=0;i<g[v].size();++i){
		int to=g[v][i];
		if(to==p) continue;
		dfs2(to,v);
	}
	for(int i=0;i<connect[v].size();++i){
		int to=connect[v][i];
		seg.add(begin[to],end[to],0,0,seg.n,-1);
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n-1;++i){
		int a,b;scanf("%d%d",&a,&b);--a;--b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(0,-1);

	for(int i=0;i<m;++i){
		int a,b;scanf("%d%d",&a,&b);--a;--b;
		connect[a].push_back(b);
		connect[b].push_back(a);
		connect[a].push_back(a);
		connect[b].push_back(b);
	}

	seg.init(n);
	dfs2(0,-1);

	for(int i=0;i<n;++i) printf("%d ",ans[i]);
	putchar('\n');

	return 0;
}

CFのEでsegtreeが出ておきながら解かないor解けないのさすがにどうにかしたい

Codeforces #152 div1C,div2E Piglet's Birthday

CF

URL http://www.codeforces.com/contest/249/problem/C

問題概要

棚がN個ある。
それぞれの棚には、最初、未開封のハチミツ瓶がa[i]個入っている。
q回イベントがある。
それぞれのイベントでは、棚uからランダムにk個ハチミツ瓶を選び、それらを開けて、棚vに入れる。
それぞれのイベント後、未開封のハチミツ瓶を一つも含んでいない棚の数の期待値 を小数で出力せよ。

N,q<=100000
0<=a[i]<=100
k<=5
u,v<=N










方針

確率dpです
dp[i][j]=棚番号iで 未開封のハチミツ瓶の数がj となる確率
とすると、未開封のハチミツ瓶の数は絶対に増えないのでうまく行きます。
最初に瓶がない棚もあることに注意

using namespace std;
static const int INF =500000000;

int n;
double dp[100005][105];
double tmp[105];
int init[100005],has[100005];
double C[1000005][10];
//コンビネーション
int main(){
	for(int i=0;i<105;++i) for(int j=0;j<105;++j) dp[i][j]=0;
	for(int i=0;i<1000005;++i){
		C[i][0]=1;
		for(int j=0;j<min(i,9);++j) C[i][j+1]=C[i-1][j]+C[i-1][j+1];
	}
//コンビネーションを予め計算
	scanf("%d",&n);
	double cur=0;
	for(int i=0;i<n;++i){
		scanf("%d",&init[i]);
		has[i]=init[i];
		dp[i][init[i]]=1;
		if(init[i]==0) ++cur;
	}
	int q;scanf("%d",&q);
	while(q--){
		int u,v,k;scanf("%d%d%d",&u,&v,&k);--u;--v;

		cur-=dp[u][0];
		for(int j=0;j<105;++j) tmp[j]=0;
		for(int i=0;i<=init[u];++i) if(dp[u][i]>1e-30){
			for(int j=0;j<=k && j<=i;++j){
//j:=いくつ未開封の瓶を選ぶか
				tmp[i-j]+=dp[u][i]*C[i][j]*C[has[u]-i][k-j]/C[has[u]][k];
//has[u]個からk個選ぶとき、i個の未開封瓶がj個選ばれる確率
			}
		}
		for(int j=0;j<105;++j) dp[u][j]=tmp[j];
		has[u]-=k;
		has[v]+=k;
		cur+=dp[u][0];
		printf("%.10f\n",cur);
	}


	return 0;
}

cinはただでさえ遅いですが小数に対してはめちゃくちゃ遅かった。注意