締まっていこう (AOJ1164)

AOJ-ICPC Programming

たわみを無くすまで引っ張る・・・はせずに解きました.


解法はrngさんがこどふぉで記事に書いているとおりです.


しかし実装の細かい部分が結構たいへんだった.
まず,始点,終点をどう扱うか.ピンの点と同様に扱おうとすると,上をとおるか下をとおるかみたいなのの判定の時に飛ばさなきゃいけなくてちょっと面倒.別扱いにしても,長さ求めるDPの時にアクセスしにくくて面倒.
結局長さを求めるのをcalclen(始点,終点,半直線のidのvector)にすることで適当にやった.
こういうの短時間で綺麗に書くのはなかなか難しいですね・・・

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef double D;
typedef complex<D> P;
int K,N;
P ps[100],as[100];
bool up(P s,P t,P p){			//line over point
	D sx=s.real(),tx=t.real(),sy=s.imag(),ty=t.imag(),x=p.real(),y=p.imag();
	D ly=sy+(ty-sy)/(tx-sx)*(x-sx);
	return ly>y;
}
void addpath(vector<int>& vc,P s,P t){
	vector<int> ad;
	D sx=s.real(),tx=t.real(),sy=s.imag(),ty=t.imag();
	bool sw=0;
	if(sx>tx){
		sw=1;
		swap(sx,tx);
		swap(sy,ty);
	}
	rep(i,N){
		D x=as[i].real(),y=as[i].imag();
		if(sx<x&&x<tx){
			if(up(s,t,as[i])) ad.pb(i*2);
			else ad.pb(i*2+1);
		}
	}
	if(sw) reverse(all(ad));
	vc.insert(vc.end(),all(ad));
}
bool cancel(vector<int>& vc){
	bool update=0;
	int A=vc.size();
	vector<bool> gomi(A,0);
	rep(i,A-1){
		if(vc[i]==vc[i+1]){
			gomi[i]=gomi[i+1]=1;
			update=1;
			i++;
		}
	}
	vector<int> nvc;
	rep(i,A) if(!gomi[i]) nvc.pb(vc[i]);
	vc=nvc;
	return update;
}
P point(int id){
	return as[id/2];
}
D calclen(P S,P T,vector<int>& vc){
//	show(S);
//	show(T);
	int A=vc.size();
//	show(A);
//	for(int v:vc) cout<<v<<" ";
//	puts("");
	D dp[110];
	rep(i,A+2) dp[i]=1e9;
	dp[0]=0;
	rep(i,A+1){
		P t=(i==A?T:point(vc[i]));
		rep(j,i+1){
			P s=(j==0?S:point(vc[j-1]));
			bool ok=1;
			for(int k=j;k<i;k++){
				if(up(s,t,point(vc[k]))==(vc[k]&1)){
					ok=0;
					break;
				}
			}
			if(ok) chmin(dp[i+1],dp[j]+abs(s-t));
		}
	}
	return dp[A+1];
}
int main(){
	while(true){
		cin>>K>>N;
		if(K==0) break;
		rep(i,K){
			D x,y;
			cin>>x>>y;
			ps[i]=P(x,y)*polar(1.0,1.0);
		}
		rep(i,N){
			D x,y;
			cin>>x>>y;
			as[i]=P(x,y)*polar(1.0,1.0);
		}
		rep(i,N-1) rep(j,N-1) if(as[j].real()>as[j+1].real()) swap(as[j],as[j+1]);
		vector<int> vc;
		rep(i,K-1) addpath(vc,ps[i],ps[i+1]);
		while(cancel(vc));
		D ans=0;
		int M=vc.size();
		int l=-1;
		for(int r=1;r<=M;r++){
			if(r==M||(vc[r]^vc[r-1])==1){
				vector<int> tmp;
				P s,t;
				if(l==-1) s=ps[0];
				else s=point(vc[l]);
				if(r==M) t=ps[K-1];
				else t=point(vc[r]);
				if(r==M) r++;
				for(int i=l+1;i<r-1;i++) tmp.pb(vc[i]);
				ans+=calclen(s,t,tmp);
//				show(calclen(s,t,tmp));
				l=r;
			}
		}
		printf("%.12f\n",ans);
	}
}

Presentation (AOJ2453)

AOJ-ICPC

問題:
Presentation | Aizu Online Judge

考えれば解ける系の綺麗な問題.
でも1100はない気がするなあ(900くらい?)





一度ある木をコピーすると,その木を組み合わせたようなものしか出来ない.その木Xを使ってできるかの判定は根から順にdfsをすればできる(実際今どの頂点か+今Xでどの頂点にいるか を持つ). O(N)
どういうものがありえるか考える.N=200000くらいなんで選択肢がいっぱいあると困る.

適当に切った上の部分:正しいけど可能性がありすぎる
各頂点を根とする部分木:N個ある.ただし,辺の個数が元の木の約数じゃなきゃいけない ということを考えると結構減る がまだ不十分.

最も深い点(のうちの任意のひとつ) (vとする)の先祖たちを根とする部分木:これも最大N個あるが,明らかに辺の個数がdistinctになるので,高々約数個しか考えなくていい.N=200000までだと約数の個数は160が最大なので間に合う.

上記のやつだけでいいことはなぜわかるかというと,木Xを任意に取ってきて,それがvをどう覆うか考える.この時,Xの根に対応する頂点をrとする.Xがrを根とする部分木になってることを示せばOK.なってないとするとある頂点wがありXに覆われていない.従ってその頂点からさらにXが生えていることになるが,これはvが深さが最大であることに矛盾する.


で,コピーしてコピーして・・・みたいなグラフは結局どう考えるかというと,今やったことをXそれぞれに対してやってもいいけどかなりTLEギリギリっぽい.実は今OKと判定した木X,Yに対しては,「XからYが作れる」⇔「Xの辺の個数がYの辺の個数の約数」となる.(→は当たり前.←は,Xでのさっきのuを取ってくると,Yでそこいかが綺麗に埋まらなければおかしいことがわかるので)

なのでDAGが簡単に作れて,dpができます(最大160^2)

全体でO(Nσ(N) + σ(N)^2)


ちなみに,グラフ作るときにdfsするとスタックオーバーフローするので,魔法を使いましょう

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
#define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);
using namespace std;
int N;
vector<int> G[200001];
int par[200001],dep[200001],num[200001];
void makegraph(){
	string s;
	cin>>s;
	int v=-1;
	for(char c:s){
		if(c=='('){
			if(v>=0) G[v].pb(N),dep[N]=dep[v]+1;
			par[N]=v;
			v=N;
			N++;
		}else{
			num[v]=1;
			for(int u:G[v]) num[v]+=num[u];
			v=par[v];
		}
	}
}
bool dfs(int v,int w,int s){
	if(G[v].size()==0&&G[w].size()==2) return false;
	if(G[v].size()==0&&G[w].size()==0) return true;
	if(G[v].size()==2&&G[w].size()==2) return dfs(G[v][0],G[w][0],s)&&dfs(G[v][1],G[w][1],s);
	return dfs(v,s,s);
}
bool ok(int v){
	return dfs(0,v,v);
}
int main(){
	BEGIN_STACK_EXTEND(128*1024*1024);
	makegraph();
	vector<int> ds;
	int v=0;
	rep(i,N) if(dep[i]>dep[v]) v=i;
	v=par[v];
	while(v>=0){
		if((N-1)%(num[v]-1)==0){
			if(ok(v)) ds.pb(num[v]-1);
		}
		v=par[v];
	}
	int K=ds.size();
	int dp[161]={};
	rep(i,K) dp[i]=1e9;
	dp[0]=0;
	rep(i,K){
		rep(j,i){
			if(ds[i]%ds[j]==0){
				chmin(dp[i],dp[j]+ds[i]/ds[j]-1);
			}
		}
	}
	cout<<dp[K-1]<<endl;
	END_STACK_EXTEND;
}

CF345

CF Programming

19位で赤に戻った はじめてCFとTC両方赤になった やったぜ。

Copenした
C:大小関係(のうち最も近いものだけ)でDAGを作り,最短経路を求めればいい.先にunionfindしたけど,よく考えるとSCCすればよかった.
A:同じ点があることに注意して数える
B:片方どこまで行くか固定して,もう片側はにぶたん.絶対バグらせまくると思ったけど割とスムーズに行けた.
D:ドワコンのLISのやつにめっちゃ似ている.動いた点を使わない場合:もとのLISに含まれてない点 もしくは含まれているがそこと同じランク(LISで何番目か)の点が複数あればLISは減らない.そうでなければLIS-1.使う場合:クエリ先読みしておいて,LISを左右から作るとき,該当の場所で実際にそれを追加してみようとすると左右への長さがわかるので求まる.

全部通ってよかった.

あまりレーティングというものを気にしないほうがいいことがわかる

コンテスト後
E:適当に辺を一つ取得できる機能を持つLCTreeでできるっぽいが,実はめちゃくちゃ簡単に出来る.

N頂点の木Aを木Bに変えるとする.最小回数はN-1 - (AとBで一致してる辺の数) になる(これは明らかな下限).これを構成する.
とりあえずA,Bで一致してる辺のみでunionfindする.その後AとBで適当な頂点(同じ)からそれぞれdfsする.dfs(v,p)時に,もしvとpが同じ連結成分(unionfindの話)でなければ(つまり,AにあってBにない辺ならば),「vの連結成分のidから, 辺(v,p)にアクセスできる」ように配列を持っておく.

で,構成だが,Aのdfsの帰りがけ順でAの辺を(必要な物は)外す.今外した辺をv→pとしてvの連結成分のidをvidとおく,その後は,Bの方でvidから(根向きに)生えてる辺をつける(これは一意に存在(∵Aの方とBの方でのunionfindで同じものを同じ頂点とみなした後での根付き木を考えると,頂点集合は同じで根も等しいので)).これでサイクルが出来てしまわないことの証明は次.

帰納法.さっきまでOKだったとして,今あるBの辺を生やした後サイクルが出来たとする.サイクルに各辺がAのものかBのものか書いておいて,Aでの向き,Bでの向きをそのまま入れたものを考えると,ちゃんと有向サイクルになる(∵ある頂点から2本以上辺が出てることがありえないので).さっきまでOKだったので,そのサイクルの内一本にはBと書いてある.ここで,x→y→zという3頂点(2辺)で,「x→yがAかつy→zがB」なるものが存在しないことがわかる(yから生えている辺がBということは既にAでのdfs帰りがけが終了したということで,これはAの子孫xに関してもdfs帰りがけが終了したことを意味する,従ってx→yはAになるはず).このことからサイクル全部の辺がBになるしかないが,これはBが木なことに矛盾.よって(帰納法により)サイクルは出来ない.


結構証明がたいへん(まずあまり成り立つ空気を感じなかった) 全Bにならないといけない,ってとこの議論が面白い.

コード:
A:http://codeforces.com/contest/650/submission/16569600
B:http://codeforces.com/contest/650/submission/16572578
C:http://codeforces.com/contest/650/submission/16567681
D:http://codeforces.com/contest/650/submission/16578322
E:http://codeforces.com/contest/650/submission/16757704

なぜかEの実行時間がめっちゃ遅い O(NlogN)なのに まあNα(N)にすればはやくなるけど

range tree

Programming

とりあえず2次元で,クエリが点追加と矩形カウントできるデータ構造の話をします.まずある点(a,b)から左下にある点の数を数えられれば矩形カウントが出来ることに注意.
座標幅は縦横ともにL,クエリN個とします(当然点の数もN以下)

蟻本にも載ってる,マージソートの途中経過をそのまま保存したようなsegtreeを使えば,前計算O(Nlog^2N),クエリO(log^2N),全体でO(Nlog^2N),空間O(NlogN)で出来る(logが上に凸なので,まとめてlogとかにはならないことに注意(よくある木DPみたいな)) ただしこれは点追加ができない.

点追加ができなくていいなら計算量すら落とせて,点を左から順番に追加していったと考えて,クエリ(a,b)があれば,a以下までを追加したタイミングでで下に何個点があるか を普通の1次元segtreeを使って求めれば良い 時間空間ともにO(NlogN) 横方向を時間軸だと思ってsegtreeを左から進めていくイメージ.

点追加がしたい.
クエリが先読みできる場合.
蟻本のやつに+点追加ができればいいので,segtreeに持たせるのをvectorじゃなくてBITにすればよい.NlogN個のBIT全てで座標幅Nにしてたらアホなので,そこに出てくるとこを座圧(これはさっきのマージソートの途中経過を持っとけばできる)すれば,時間O(Nlog^2N),空間O(NlogN).

さっきまでのは座圧して座標幅をNだと思えたので計算量にLは出てこなかったが,先読みできないと話は違ってくる.

今L=1e9くらいのイメージで話してます
まず横幅が大きいと難しいので,O(N)だとしてください
さっきと同様横向きにsegtreeを持ちます.各ノードには平行二分探索木をのせます(あっ(察し))すると時間計算量はさっきと一緒で,空間も全体でO(NlogN)に出来る.

横幅も大きい時なんですが,横も自前平衡二分木にすればよくて,mergeがO(1)で出来ない(mergeする二つの木の大きさをnとしてO(nlogn))ためこれも計算量は全体でO(Nlog^2N) 空間がO(N)になってる・・・?(書いててびっくりした)

最後のは実装してないし計算量もほんとか怪しいので信じないでください

RUPC2016

Programming 参加記

RUPC2015だと思ってました.

day1
家で出る.Eまでやった後Fが多方向木DPっぽいなあと思った後,Gに手を付けてしまいコンテストが終了した.
A:やる
B:前から1に→後ろから0に
C:やる(はじめ制約読んでなくて不可能ってなってた)
D:ひとつのscannerは50*ceil(50/3)=850秒くらいしか使わないので,bool dp[51][851][851]をやれば間に合う
E:ニコニコ数みたいに全探索するだけ.88=2*2*22みたいなのが無駄なのはすぐわかるけど他にも最長でない経路がある(14441=11^4 と思ったけど11じゃなくて22だからこれは例になってないし嘘かもしれない)
じゃあ大丈夫かも(適当)
Nから割っていったほうが圧倒的に状態数が少ない.
F:実は木DP一発でできるっぽい(直径求めるDPに加え,キーとして既に一本選んだか? みたいなやつ)
G:問題不備があったが,正しいバージョンだとにぶたん+グラフ遷移でできると思う.

day2:
(すぬけの)家で出る.sugimさんとチームを組んだ(ssuiggimma).13問あってびっくりした.
A:指の運動練習
B:やってない.面倒
C:unionfind,間違えてsample試さずに出しちゃってWA.
D:やってない.真ん中で切ってそれぞれlineか判定するだけ
E:やってない ちょっと動かす→回すを探索すればよさそう.
F:殴らないだけ.逆から見てどいつに注目すればいいか求めた後やるだけ.
G:使う順番とかは無視して,dp[i][A][B]=i人目まで見て,所持うまかA本,所持ふがしB本の時の最大ブタメソ所持数 とする.最終的にBがまともな値であれば途中で負になっても大丈夫(a,bの交換を全て先にやったとして良いので)なので,これでDPできる.
H:8C2本に対し,どのペアがつなげるかわかるので面倒な連結成分DPをした けど高々7本しか使わないので全探索(28C7)で間に合う.確かに.
I:接線試して2^16どれができるか確かめた後全部を埋めるのにいくら必要かDPでO(3^N)
J:オートマトンの最小化.aとbが違うという情報を伝播させていく.ちゃんと必要なとこだけ見れば全体でO(N^2).
K:差として表れる値の分布はFFTで求まる.それの差も同様にFFT.
L:suffixたちを始まる位置順でならべると[l,r)が指定できて,SA順で並べると文字列が存在するかどうかはこれも連続した区間になる(愚直ににぶたんで調べられる)ので,結局
2次元平面上にN点ある.クエリとして長方形が来る.長方形内の点の個数を求めよ. になる.2次元データ構造があれば出来そうだけどよくわからなかったので,クエリを先読みして左から順に点を追加していった時に下に何個あるか求めといて答えた.
M:各クエリに対して,重ならない長方形の数を数えられればよい.上,右,下,左にあるやつは簡単に数えられて,右上にあるやつとかが二重に数えられてしまうのでそれを引けば良い.それには,Lと同様に長方形内の点の個数が求められればいいんだけどこっちはクエリ先読みが出来ないのでしかたなくkyuridenamida法をsugimさんが実装していた.

コンテスト後にyosupo,snukeに聞くと2次元BITで出来たっぽい なるほど

day3:
day2のあとCF,SRMとあったので余裕で開始時睡眠していた.yosupoとチームを組む.チーム名悩んだけどsugim,snukeペアがin_the_houseにしていたのでinthishouseにする.眠いので意思疎通が取れずログインに時間がかかった.

yosupoが後ろのほう読んでる間に簡単なのを埋めた.
A:明らかにこのセットの中でHを除いて一番難しい 起床直後にやる問題ではない.
B:寝てたら誤読した
C:やるだけ 写経ミスった
D:yosupoが解いてた 左から全部聞くだけ+右からBITにぶたんでいいけどyosupoがAAtreeで殴っていた(こっちの方がわかりやすいらしい)
E:フロー yosupoが解いてた
F:反転して引き算しとくと全0か判定するだけ starryskyでminとmaxを持つとできる yosupoが一瞬で書いてた
G:累乗したい→出来る→おしまい
H:二次元上に点がN個あって,横方向でこの範囲にある点に+1 っていうのと, 縦方向でsum っていうのができればいい.無理やんけってなってた.結局平方分割してsegtreeを持つとかでコンテスト後に通していた.stackoverflowにO(Nsqrt(N))解が書いてあった.NlogN系じゃできないのかなあ


運営の人お疲れ様でした。

そんなに重いセットはなかったけどday2と3の間にこどふぉとSRMがあったので疲れた・・・

Company Organization (AOJ1332)

Programming AOJ-ICPC

問題:
1~Nの番号がついた集合がある.集合間の制約が順にM個来るので,どこで最初に矛盾するか答えてください.
制約は5種類で,
1:A⊆B 2:A=B 3:A≠B 4:A∩B=∅ 5:A∩B≠∅
タイプとAとBの番号が制約として与えられる.
N≤100,M≤10000


頭1,実装1,ライブラリ1
簡単だけど注意力がいる







まずにぶたんすればはじめk個の制約で矛盾するかわかればよい.
まず1,2を処理して,包含関係によるposetをつくる(処理した後に推移閉包を取る)
基本的にA∩B=∅ かつ a⊆A かつ b⊆B かつ a∩b≠∅ みたいなペアがなければ矛盾しないから,推移閉包を取った後に4の情報を下に伝播させていく(O(N^4)) でそのあと3,5で矛盾するかどうか確かめる みたいな流れなんだけど,A=∅みたいな形が出てくるのでこれだけでは済まない.例えば,a⊆A b⊆B a∩A=∅ b∩B=∅ みたいなケースだと,a=∅かつb=∅がわかるのでa≠bとは矛盾してしまう.なので∅かどうか みたいなのも持たなければいけない.どういう時にX=∅になるかというと,X⊆A X⊆B A∩B=∅ のとき.これを4を処理するときにO(N)かけてやっておけば全体O(N^4 * log M)で解ける.

頑張ればもうちょっとオーダーよくなりそうだけどどうだろう

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int N,M,t[10000],v[10000],u[10000];
bool can(int M){
	bool e[100][100]={},emp[10000]={},no[100][100]={};
	rep(i,N) e[i][i]=1;
	rep(i,M){
		if(t[i]==1) e[u[i]][v[i]]=1;
		if(t[i]==2) e[u[i]][v[i]]=e[v[i]][u[i]]=1;
	}
	rep(i,N) rep(j,N) rep(k,N) e[j][k]|=(e[j][i]&&e[i][k]);
	rep(i,M){
		if(t[i]==4){
			int a=v[i],b=u[i];
			rep(c,N) if(e[a][c]&&e[b][c]) emp[c]=1;
			no[a][b]=no[b][a]=1;
		}
	}
	rep(i,N) if(emp[i]){
		rep(j,N) if(e[i][j]) emp[j]=1;
	}
	rep(i,N) rep(j,N) if(no[i][j]){
		rep(I,N) rep(J,N){
			if(e[i][I]&&e[j][J]){
				no[I][J]=1;
			}
		}
	}
	// puts("no");
	// rep(i,N){
	// 	rep(j,N) cout<<no[i][j]<<" ";
	// 	puts("");
	// }
	rep(i,M){
		int a=v[i],b=u[i];
		if(t[i]==3){
			if(emp[a]&&emp[b]) return 0;
			if(e[a][b]&&e[b][a]) return 0;
		}
		if(t[i]==5){
			if(emp[a]||emp[b]) return 0;
			if(no[a][b]) return 0;
		}
	}
	return 1;
}
int main(){
	while(true){
		cin>>N>>M;
		if(N==0) break;
		rep(i,M){
			cin>>t[i]>>v[i]>>u[i],v[i]--,u[i]--;
		}
		int ub=M+1,lb=0;
		while(ub-lb>1){
			int m=(ub+lb)/2;
			if(can(m)) lb=m;
			else ub=m;
		}
		cout<<lb<<endl;
	}
}