問題概要

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;
}

2013-01-08

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#です

2012-12-27

セグメント木問題集

コンテスト系その他

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

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

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

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

Codeforces #157 div1E Little Elephant and Tree

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解けないのさすがにどうにかしたい

2012-12-22

Codeforces #152 div1C,div2E Piglet's Birthday

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はただでさえ遅いですが小数に対してはめちゃくちゃ遅かった。注意

2012-12-14

Codeforces#148 div1C,div2E World Eater Brothers

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

問題概要

有向全域木が与えられる。2つ頂点を選んで、そこからすべての頂点へ辺の向きに従って到達できるように辺の向きを変える。
変えなければいけない辺の数をコストとすると、最小のコストはいくらか。

頂点数<=3000

方針

2つの頂点で到達すればよいので、ある一つの辺で覆う範囲を分割できる。
分割した後は、
まずある頂点を選び、そこを始点としたとき分割したグラフ内で向きを変える辺の数(cost'と呼ぶ)を数える。
ここで、その選んだ頂点と隣接する頂点を始点とする向きを変える辺の数は、
最初に選んだ頂点が隣接する頂点に向いているなら、cost'+1
そうでないなら、cost'-1
となることが簡単に分かる。これはO(N)で実装できる

すべての辺で分割し、上の方針を繰り返す。O(N^2)

小さいケースに注意！

using namespace std;
static const int INF =500000000;

typedef pair<int,int> pi;
int n;
vector<pi> g[3005];
pi es[3005];
int dfs(int v,int p){
	int res=0;
	for(int i=0;i<g[v].size();++i){
		pi& e=g[v][i];
		if(e.first==p) continue;
		res+=e.second+dfs(e.first,v);
	}
	return res;
}
int move(int v,int p,int val){
	int res=val;
	for(int i=0;i<g[v].size();++i){
		pi& e=g[v][i];
		if(e.first==p) continue;
		res=min(res,move(e.first,v,val+1-e.second*2));
	}
	return res;
}

int main(){
	cin>>n;
	for(int i=0;i<n-1;++i){
		int a,b;cin>>a>>b;--a;--b;
		g[a].push_back(make_pair(b,0));
		g[b].push_back(make_pair(a,1));
		es[i]=make_pair(a,b);
	}
	int ans=INF;
	if(n<=2) ans=0;
	for(int i=0;i<n-1;++i){
		int A,B;
		A=es[i].first;B=es[i].second;

		int sum1=dfs(A,B),sum2=dfs(B,A);

		ans=min(ans,move(A,B,sum1)+move(B,A,sum2));
	}
	cout<<ans<<endl;


	return 0;
}

こういう回の場合、BよりCを先にやったほうが(解ける人にとっては)いいです

2012-12-14

Codeforces#148 div1B,div2D Boring Partition

URL:http://www.codeforces.com/contest/238/problem/B

問題概要

ある数列が与えられる。
これを、2つの部分列に分ける（どちらかが空でも良い）
ある2つの要素の間のコストを、2つが同じ部分列に分けられているならその和、そうでないなら和に+hしたもの(hは与えられる)と定義する。
すべての要素の間のコストの最大の差(つまり、一番大きいコスト-一番小さいコスト)の最小値はいくらか。
また、最小値を取るときどのように分けるかも出力せよ。
数列の長さ<=10^5、h<=10^8、数列の要素<=10^8

方針

貪欲
考えると、ソートしてから一番小さい要素の他を数列A,そこからいくらかまでを数列B,そのあとは再び数列A、
とするか、すべて同じ数列に入れるか、が最適
あとは、律儀に実装。
比較的頭悪い実装している・・・

using namespace std;

pair<int,int> a[100005];
int h;
int n;
int ans[100005];
int main(){
	cin>>n>>h;
	for(int i=0;i<n;++i) cin>>a[i].first,a[i].second=i;
	sort(a,a+n);

	if(n==2){
		printf("%d\n",0);
		printf("%d %d\n",1,1);
		return 0;
	}

	int res=INF;
	pair<int,int> range;
	{
		int minval=min(a[1].first+a[2].first,a[0].first+a[1].first+h),
			maxval=max(a[n-1].first+a[n-2].first,a[0].first+a[n-1].first+h);
		if(maxval-minval<res){
			res=maxval-minval;
			range=make_pair(1,n-1);
		}
	}
	{
		int minval=a[0].first+a[1].first,maxval=a[n-1].first+a[n-2].first;
		if(maxval-minval<res){
			res=maxval-minval;
			range=make_pair(0,n-1);
		}
	}

	for(int i=1;i<n-1;++i){
		int minval=min(a[0].first+a[1].first+h,a[0].first+a[i+1].first);
		if(i>=2) minval=min(minval,a[2].first+a[1].first);
		int maxval=-1;
		if(i<n-2) maxval=a[n-1].first+a[n-2].first;
		maxval=max(maxval,a[n-1].first+a[i].first+h);
		if(maxval-minval<res){
			range=make_pair(1,i);
			res=maxval-minval;
		}
	}

	printf("%d\n",res);
	for(int i=0;i<n;++i) ans[i]=1;
	for(int i=0;i<n;++i) if(range.first<=i && i<=range.second) ans[a[i].second]=2;

	for(int i=0;i<n;++i) printf("%d%c",ans[i],i==n-1?'\n':' ');

	return 0;
}

hogloidのブログ

へなちょこ

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

問題概要

方針

POJ Solved Graph

セグメント木問題集

☆

☆☆

☆☆☆

☆☆☆☆

☆☆☆☆☆

Codeforces #157 div1E Little Elephant and Tree

問題概要

方針

Codeforces #152 div1C,div2E Piglet's Birthday

問題概要

方針

Codeforces#148 div1C,div2E World Eater Brothers

問題概要

方針

Codeforces#148 div1B,div2D Boring Partition

問題概要

方針