2013-03-11

個人的良問リスト

少し前から始めていた、良問だなーと思った問題をひたすらリストしていったものを上げます
良問、というより解く価値のある問題、といった方が正確かもしれません
2ヶ月ごとぐらいにアップデートする予定です
問題のリンクが貼ってあり、右に白い文字で解法の要素が単語で書いて有ります(マウスで囲うと見えます)
解法の要素は自分にわかるように作ったので不明な点があるかもしれません
☆は僕が初見では解けなかった問題たちです
一部、キーワードが変なひらがなになってるのがありますが、それははてなのキーワードに引っ掛けないためです

キーワードのみではわからないのも多いと思うのでなんか気になったら聞いてください(僕は全部解いているはずです)

問題たちには偏りがあります。今のところCF,USACO,Polish OIがほとんどです

誤解を招きそうな表現-> O(N)は問題の本質部分がO(N)で解けるということを言ってて、全体の計算量がO(N)というのを示すわけではないです

追加 5/5

http://www.codeforces.com/contest/280/problem/C 木確率
http://main.edu.pl/en/archive/oi/18/imp 貪欲 ☆
http://main.edu.pl/en/archive/oi/18/met BIT 二分探索
http://main.edu.pl/en/archive/oi/18/pro フロー貪欲 X最小費用流 ☆
http://main.edu.pl/en/archive/oi/17/kor 調和きゅうすうローリングハッシュ
http://www.codeforces.com/contest/283/problem/C DP
http://www.codeforces.com/contest/283/problem/E セグメント木数え上げ ☆
http://joisc2013-day3.contest.atcoder.jp/tasks/joisc2013_cake 分割統治実はO(NlogN) or セグメント木 ☆
http://joisc2013-day1.contest.atcoder.jp/tasks/joisc2013_communication グラフ木 Union-find 隣り合ったものがすべて繋がっていればOK ☆
http://joisc2013-day1.contest.atcoder.jp/tasks/joisc2013_collecting セグメント木包除数え上げ
http://joisc2013-day2.contest.atcoder.jp/tasks/joisc2013_mascots DP 数え上げ縦に伸ばす・横に伸ばすのみで十分
http://main.edu.pl/en/archive/oi/17/klo O(N) ☆ 取りうるものは階段上になる一部のみ
http://www.codeforces.com/contest/277/problem/E 最小費用流 O(N^3logN)
http://main.edu.pl/en/archive/oi/17/owc 円環しゃくとり DP O(N^3)
http://main.edu.pl/en/archive/oi/17/tel 貪欲グラフ O(N+M) ☆
http://www.codeforces.com/contest/286/problem/A 実験 O(N)
http://www.codeforces.com/contest/286/problem/B 調和きゅうすうほとんどの場所は動かない O(NlogN)
http://www.codeforces.com/contest/286/problem/D 区間重複を取り除く->イベント O*1
http://main.edu.pl/en/archive/oi/16/gas 木貪欲葉から貪欲に切り離す O(NK)
http://main.edu.pl/en/archive/oi/16/baj 回文の中心を決めて、幅優先。2ステップ一気にやろうとするとTLE O(NM+DM)
http://main.edu.pl/en/archive/oi/16/kon DP 1ステップに複数の移動候補がある方が、却ってメモリ面で優秀 O(N^2K)
http://main.edu.pl/en/archive/oi/16/arc リスト省メモリ STD::リスト使える　(広義)減少列に分割して、それぞれのステップで消すのは最初の減少列の最後いれれーたで頑張る ☆
http://main.edu.pl/en/archive/oi/16/lyz セグメント木ある区間の和が、区間の長さをD増やしても入らないならOUT と言い換えられる　O((n+m)log n) ☆
http://main.edu.pl/en/archive/oi/16/slw 文字列　検索　貪欲？　f^k(0)に含まれるなら、f^(k-1)(0)で求められる文字列も定まる　これをk=0になるまで繰り返す。途中で0が挟まったりするとアウト ☆
http://main.edu.pl/en/archive/oi/16/wsp 幾何貪欲スタックある街からは、そこから一番首都側にいける辺以外は使う必要がない最初は円環状に回るのをどんどんショートカットしていく感じ O(n+mlogm) ☆
http://main.edu.pl/en/archive/oi/15/blo dfs lowlink 関節点のみ、自明コスト以外に足す必要がある low[dst]>=pre[v] のとき、dstの先は上に戻れないので、通る必要のある組み合わせをたす O(E)
http://main.edu.pl/en/archive/oi/15/rob BFS imos法タコ型状なので、上と下に分割する。上に凸な三角形っぽいものに分割すると、上から平面走査していき、一番後まで邪魔になるのは一番下にあるX これを利用してimos法などを使い、どこに入れないかを求める。　あとはBFSだけ O(N^2) ☆
http://main.edu.pl/en/archive/oi/15/bbb デック　スライド最小値累積和 k回revolveした時を考えると、その時預金額が最も少ないときから、いくつ変更するかが分かる O(N)
http://www.codeforces.com/contest/295/problem/D 数え上げ DP imos法 dp[高さ][幅] で、ピラミッド状の形をいくつ作れるかを数える遷移で、一次関数状に値が増える感じの足し方をするが、imos法を2回やればOK caveの形は、最後の膨らんだところで分割して、ここでも多重imos法を使ってがんばる O(NM)
http://www.codeforces.com/contest/295/problem/E DP セグメント木座標圧縮列で持たずに、どこの場所がONになってるかを考える更新も、(左ノードのコスト)+(左ノードが左の右端まで行く値)*(左ノードの数)+(左ノードの数)(右ノードの数)(左と右の間隙) ... のようにすればいける O(MlogN)
http://www.codeforces.com/contest/150/problem/E 木　セグメント木重心分解二分探索定数倍　中央値k以上にできるか、という二分探索をする。パスの中で、上方に寄与する辺が半分以上ならよい。重心分解をして、重心からの距離がある範囲の中で最大に上方に寄与する頂点を求めたくなる。これはセグメント木で実現できる O(Nlog^3n) logはひとつ外れる。
http://main.edu.pl/en/archive/oi/14/drz セグメント木　コスト付けで問題になるのはそれ自体の値、左、右の値交換先の木の高さをxとして隣接する2つのコストの和のグラフを作ると、3つのパートから成る。　木の高さでソートし、常に、交換相手にとって交換する木が、3つのパートのどこに位置するかを持っておく。また、交換する木にとって相手が3つのどのパートにあるかも場合分けして求める。これらをセグメント木を使って行う。端の場合・隣接する2つを交換する場合に注意。 O(NlogN)
http://main.edu.pl/en/archive/oi/14/grz φ関数整数　φ(k)*(a/k)*(b/k) の合計を求めることになる。 kを1...√b まで調べ、そのあとはb/kの値別に、kが√b以上のものを調べる。 O(N*B^0.5)
http://main.edu.pl/en/archive/oi/14/grz 素因数ぶんかい文字列クエリ長さLの範囲のとき、Lの素因数について独立に切れるかどうか考えればよいまた、Kの長さでに切れるかどうかは、 [0,L-K)==[K,L)を調べればよい O(NloglogN+QlogN)

POIとかむっちゃ難しいのでちゅうい
良問の基準も人によって違うので注意しましょう僕は比較的甘いほうだと思うのでそこまで良くないのも混ざってるかもしれません

*1:Q+N)*log(Q+N

2013-02-02

Codeforces #165 div1-D Maximum Waterfall

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

2013-02-02

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

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

2013-02-02

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

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

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

hogloidのブログ

へなちょこ

個人的良問リスト

Codeforces #165 div1-D Maximum Waterfall

問題概要

方針

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

問題概要

方針

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

問題概要

方針

POJ Solved Graph

セグメント木問題集

☆

☆☆

☆☆☆

☆☆☆☆

☆☆☆☆☆

Codeforces #157 div1E Little Elephant and Tree

問題概要

方針