Hatena::Grouptopcoder

skyaozoraの日記

|

2015-01-31

幾何問題用ビジュアライザ

16:23

imosさんの幾何ビジュアライザを使ったのだけど、この記事はjavascriptド素人の自分にはやや説明不足で、追加でちょっと調べる必要があった。多分みなさんは普通に使えると思うけど、一応どうすれば見れるかメモ。

まず、

<html>
<head>
<script>
function line(x,y,a,b){c.b();c.moveTo(x,y);c.lineTo(a,b);c.s();}
function circle(x,y,r){c.b();c.arc(x,y,r,0,7,0);c.s();}
window.onload=function(){d=document;d.i=d.getElementById;c=d.i('c').getContext('2d');c.b=c.beginPath;c.s=c.stroke;d.i('s').src='data.js?';};
</script>
</head>
<body><canvas id="c" width="500" height="500" style="border:1px solid #000;"></canvas>
<script id="s"></script></body>
</html>

というコードを書いて(1,2,8,11行目が追加)、vis.htmlとかのhtmlファイルとして保存する。で、元記事に書いてあるようにdata.jsというファイルにどういう直線や円を書くかという指定を記述して、このhtmlファイルをブラウザで開けば図が見られる。

他にも方法はあると思うけど、とりあえずこの方法をやれば見れるっていうメモってことで。

AOJ1171 レーザー光の反射

15:28

2010年の国内予選のG問題。光が逆行するのを許してしまっていて答えが合わず苦しんだ。

//10ICPC国内予選G レーザー光の反射 (AOJ1171)
//include、ライブラリ略
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
seg se[8][8];
int zyo[8][8];
double cal(vector<int> a,int n,Pt ta,Pt le){
	int m=a.size();
	rep(i,m-1){
		if(a[i]==a[i+1]) return inf;
	}
	rep(i,m) rep(j,n){
		if(j!=a[i]) se[i+1][j]=seg(ref(se[i][a[i]].s,se[i][a[i]].t,se[i][j].s),ref(se[i][a[i]].s,se[i][a[i]].t,se[i][j].t));
		else se[i+1][j]=se[i][j];
	}
	rep(i,m) ta=ref(se[i][a[i]].s,se[i][a[i]].t,ta);
	vector<Pt> p;p.pb(le);
	rep(i,m){
		if(!iSSstrict(ta,p[i],se[i][a[i]].s,se[i][a[i]].t)) return inf;
		p.pb(pLL(ta,le,se[i][a[i]].s,se[i][a[i]].t));
	}
	p.pb(ta);
	rep(i,p.size()-1){
		rep(j,n){
			if(iSSstrict(p[i],p[i+1],se[i][j].s,se[i][j].t)) return inf;
		}
	}
	return (le-ta).abs();
}
int main()
{
	Pt ta,le;
	rep(i,7){
		zyo[i][0]=1;
		rep(j,7) zyo[i][j+1]=zyo[i][j]*i;
	}
	int px,py,qx,qy,n;
	while(cin>>n,n){
		double ret=inf;
		rep(i,n){
			cin>>px>>py>>qx>>qy;
			se[0][i]=seg(Pt(px,py),Pt(qx,qy));
		}
		cin>>px>>py;ta=Pt(px,py);
		cin>>px>>py;le=Pt(px,py);
		rep(i,6) rep(j,zyo[n][i]){
			vector<int> a;int b=j;
			rep(k,i){a.pb(b%n);b/=n;}
			double ca=cal(a,n,ta,le);
			ret=min(ret,ca);
		}
		printf("%.12f\n",ret);
	}
}

2015-01-13AOJ2345 NetworkReliability

問題概要

23:32

14頂点以下のグラフが与えられる。それぞれの辺は(独立に)p%の確率で消滅する時、残ったグラフが連結である確率を求めよ。

解法

23:32

ある頂点集合が連結である確率をbitDPで求める。求め方は、「その集合の中のindexが最小の要素を含む連結成分が集合より小さい」確率を求めて1から引く。その確率は、全ての(最小の要素を含み、元の集合よりは小さい)部分集合における「部分集合が連結である確率」*「部分集合が補集合と繋がっていない確率」の和。O(N^3*N)

//11年度冬コンテストF NetworkReliability (AOJ2345)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
double dp[(1<<14)+10];
double pr[16][(1<<14)+10];
double gr[16][16];
int main()
{
	int n,m,p,a,b;
	rep(i,16) rep(j,16) gr[i][j]=0.0;
	cin>>n>>m>>p;
	rep(i,m){
		cin>>a>>b;a--;b--;gr[a][b]=gr[b][a]=0.01*(100-p);
	}
	rep(i,n) rep(j,(1<<n)){
		pr[i][j]=1.0;
		rep(k,n){
			if((j&(1<<k))) pr[i][j]*=1.0-gr[i][k];
		}
	}
	REP(i,1,(1<<n)){
		int lo;
		while(!(i&(1<<lo))) lo++;
		dp[i]=1.0;
		for(int j=i;j>0;j=((j-1)&i)){
			if(j==i || !(j&(1<<lo))) continue;
			double t=dp[j];
			rep(k,n){
				if((j&(1<<k)) || !(i&(1<<k))) continue;
				t*=pr[k][j];
			}
			dp[i]-=t;
		}
	}
	printf("%.12f\n",dp[(1<<n)-1]);
}

2015-01-07AOJ1197 サイコロ職人

去年の国内予選で引退に追い込まれた憎き問題。

最初vectorで書いてたらTLE喰らった。やっぱりvectorの代入って重いんだな・・・。

//ICPC国内予選14F サイコロ職人(AOJ1197)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
string inf="impossible";
int t[6],u[6],w[6];
bool ok(void){
	rep(i,6){
		if(u[i]<0) return false;
	}
	int a=u[0]+u[5],b=u[1]+u[3],c=u[2]+u[4];
	if(a>b+c || b>a+c+1 || c>a+b+1) return false;
	return true;
}
string cal(int a,int b){
	rep(j,6) u[j]=w[j];
	if(!ok()) return inf;
	int d,n=0;rep(i,6) n+=w[i];
	string ret="";
	rep(i,n){
		//E
		rep(j,6) u[j]=w[j];
		d=u[0];u[0]=u[1];u[1]=u[5];u[5]=u[3];u[3]=d;
		u[5]--;
		if(ok()){rep(j,6) w[j]=u[j];ret+='E';continue;}
		//N
		rep(j,6) u[j]=w[j];
		d=u[0];u[0]=u[2];u[2]=u[5];u[5]=u[4];u[4]=d;
		u[5]--;
		if(ok()){rep(j,6) w[j]=u[j];ret+='N';continue;}
		//S
		rep(j,6) u[j]=w[j];
		d=u[0];u[0]=u[4];u[4]=u[5];u[5]=u[2];u[2]=d;
		u[5]--;
		if(ok()){rep(j,6) w[j]=u[j];ret+='S';continue;}
		//W
		rep(j,6) u[j]=w[j];
		d=u[0];u[0]=u[3];u[3]=u[5];u[5]=u[1];u[1]=d;
		u[5]--;
		if(ok()){rep(j,6) w[j]=u[j];ret+='W';continue;}
	}
	return ret;
}
int main()
{
	int a,b;
	while(cin>>t[0]>>t[1]>>t[2]>>t[3]>>t[4]>>t[5],t[0]+t[1]+t[2]+t[3]+t[4]+t[5]){
		sort(t,t+6);
		string ret=inf;
		cin>>a>>b;a--;
		while(1){
			rep(j,6) w[j]=t[j];
			string s=cal(a,b);
			if(ret==inf) ret=s;
			else if(ret>s) ret=s;
			if(!next_permutation(t,t+6)) break;
		}
		if(ret==inf) cout<<ret<<endl;
		else cout<<ret.substr(a,b-a)<<endl;
	}
}

2014-12-16競技プログラミングでたまに使われる名前の付いてないテクニックにつ

Competitive Programming Advent Calendar 2014の16日目の記事です。この記事では、プログラミングコンテストにおいてたまに出題されるものの、特に名前が付いてないしそこまで有名ではないかもしれないとあるテクニックを、個人的には割と面白いと感じたので紹介させていただきます。今までの中でも輪をかけて誰に得なのか分からない記事ですが、よろしければお付き合い下さい。

問題

まず、2013年のICPCアジア地区予選会津大会のG問題として出題された以下の問題をご覧下さい

Longest Chain

この問題をざっくりと説明すると、3次元空間上に点がたくさん存在するので、x座標もy座標もz座標もstrictlyに昇順となるような出来るだけ長い列を求めてくださいというものです。点の数は30万個以下です。

とりあえず、この手の問題の良くあるやり方として、まずz座標で昇順にソートして問題をx,yの2次元に落とします。すると、その状態でのx,y共に狭義単調増加となる最長部分増加列 (Longest Increase Sequence, LIS)を求めればいいことになります。LISは二分探索を使うことでO(nlogn)で解く手法が存在します。なので、元の問題が2次元の場合は一つの座標でソートすることでLISを求める問題に帰着することが出来ますが、3次元の場合はx座標もy座標も増加する部分列を求めなければいけません。LISにおいては、

  • ある長さのLISの末尾要素が今見ている要素より小さいかを判定する
  • ある長さのLISの末尾要素を更新する

という二つの処理が必要です。今回は値が2次元な場合で、そしてサイズを考えるとO(logn)くらいでこれらの処理を行わなければいけません。そこで、以下に説明するテクニックを用います。

テクニックの説明

まず、2次元で考える場合は、ある長さのLISの末尾要素は一意に定まりません。何故なら(1,6)と(5,2)のような2つの値はどちらが大きいか決められないためです(順序関係が定まらない)。ただ、x_i<=x_j,y_i<=y_jとなるような要素i,jは同時には存在し得ない(明らかにjの方はいらない)ので、ある長さのLISの末尾要素は下の図のようにxに関してはstrictlyに降順でyに関してはstrictlyに昇順となる要素の集合となります。

20141215225700

これを、(y,x)といったpair<int,int>型を作ってsetで管理しておくと、setの中でyの昇順かつxの降順に並ぶようになり処理が楽です(C++を想定しているので他の言語の場合は適宜脳内変換をお願いします)。

末尾要素が今見ている要素より小さいかを判定する

今見ている要素よりx,yともに小さい要素が一つでも存在するかどうかを判定する必要があります。下の図では今見ている要素が赤い点だとすると、その左下の領域に要素が一つでも存在するかどうかを判定するということです。

20141213234124

この場合は、「今見ている要素よりもyが小さい要素の中で最もyが大きい要素(下の図の黄色の点)」のxが今見ている要素のxより小さいかどうかを見ればいいです。もしその要素のxが今見ている要素のx以上だったら、それよりyの小さい要素はxは大きくなるので、「今見ている要素よりx,yともに小さい要素」は一つも存在しないことが分かるためです。

この、「今見ている要素よりもyが小さい要素の中で最もyが大きい要素」は、setで今見ている要素をキーにlower_boundをかけて見つかった要素(下の図の緑の点)の一つ前の要素となります。

20141213234125

もし、そのような要素のyが今見ている要素のyと同じであったら、さらに一つ前の要素が「今見ている要素よりもyが小さい要素の中で最もyが大きい要素」となります(下の図の黄緑の点)。

20141213234126

この処理の1回辺りの計算量はO(logn)となります。

末尾要素を更新する

以下のように、ある長さのLISの末尾要素の集合に新たな要素を加える場合、上で述べた処理を行うために「yの昇順かつxの降順に並んでいる」という条件を満たしている必要があります。よって、以下の図の赤い点を新たな要素として加える場合、その右上の部分の要素は全て消去しなければいけません。

20141213234129

これを行うためには、新たな要素をキーにlower_boundをかけて見つかった要素(下の図の緑の点)から一つずつ先の要素を見て行きながらその要素を消していきます(下の図の黄色の点)。そして、xが新たな要素より小さくなったところで消去を止めます。

20141215224911

すると更新後の末尾要素の集合は下の図のようになり、少々見づらいですが「yの昇順かつxの降順に並んでいる」という条件を満たしているのでまた判定や更新の処理が行えるようになります。

20141213234131

要素の消去全体で合わせて高々n回しか行われないのでならし計算量はO(1)となるので、この処理1回辺りの計算量はO(logn)となります。

これにより、この問題が計算量O(nlog^2n)で解けるようになりました。

ソースコード

私がこの問題に通したソースコードを置いておきます

#define fi first
#define se second
typedef pair<int,int> pint;
typedef pair<int,pint> tint;
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int A,B,C=~(1<<31),M=(1<<16)-1;
int ran(){
	A=36969*(A&M)+(A>>16);
	B=18000*(B&M)+(B>>16);
	return (C&((A<<16)+B))%1000000;
}

set<pint> s[364364];
vector<tint> v;

//ここで末尾要素の集合を更新しています
void ins(int a,pint p){
	set<pint>::iterator it=s[a].lower_bound(p),it2=it;it2--;
	if(it2->se<=p.se) return;
	while(it->se>=p.se) s[a].erase(it++);
	s[a].insert(p);
}

//ここで末尾要素の集合に今見ている要素より小さい要素が存在するかをを判定しています
bool ok(int a,pint p){
	set<pint>::iterator it=s[a].lower_bound(p);
	while(it->se<p.se){
		if(it->fi<p.fi) return true;it--;
	}
	return false;
}

int main()
{
	int n,m,x,y,z,inf=1145141919;
	while(cin>>m>>n>>A>>B,m+n){
		rep(i,3+n+m) s[i].clear();
		s[0].insert(mp(-1,-1));
		REP(i,1,3+n+m){
			s[i].insert(mp(inf,-1));s[i].insert(mp(-1,inf));
		}
		v.clear();
		rep(i,m){
			cin>>x>>y>>z;v.pb(mp(-z,mp(y,x)));
		}
		rep(i,n){
			x=ran();y=ran();z=ran();v.pb(mp(-z,mp(y,x)));
		}
		sort(rAll(v));
		int out=0;
		rep(i,n+m){
			int lo=0,hi=out;
			while(hi>lo){
				int mi=(hi+lo+1)/2;
				if(ok(mi,v[i].se)) lo=mi;else hi=mi-1;
			}
			out=max(out,lo+1);ins(lo+1,v[i].se);
		}
		cout<<out<<endl;
	}
}

ここで、今回の記事で紹介したテクニックとは関係無いですがもう一つちょっとした実装上のテクニックを紹介すると、

v.pb(mp(-z,mp(y,x)));

といった形で要素の配列を作ることで、zに関しては昇順であるがy,xに関しては降順にソートしているという点です。もし全てに関して昇順にソートすると、例えば(z,y,x)=(8,1,0)となる要素の後に(8,9,3)となる要素が来ますが、この2つの要素はzが等しいので両方ともLISに含めることは出来ないにもかかわらず、(y,x)=(1,0)となる要素が長さ1のLISの末尾要素に入ってしまっていると2つ目の要素が長さ2のLISの末尾要素になると判定されてしまうため、答えが変わってしまいます。

これを避けるためには判定と更新を別のタイミングで行う(zが切り替わるタイミングで更新を行う)必要がありますが、「zに関しては昇順であるがy,xに関しては降順」にソートすると、(8,9,3)という要素を見る時は、(8,1,0)などといった「zは同じだがx,yは共に小さい」要素はまだ見ていないので、特に判定と更新を別のタイミングで行わなくても正しい答えが出るようになります。

なお、この「ソートの基準を少し変える」テクニックは、会津大会の本番中にこのG問題を担当していたチームメイトが使っていたものです。私は当時はこのテクニックを知らず、デバッグの際に印刷されたコードを見て「この部分が間違ってるんじゃないの?」といって説明させて無駄な時間を消費してしまいました・・・

参考問題

このようなテクニックを用いる問題として、他には以下のような問題が存在します

特に前者のFishはJOI勢にとって有名らしいので、この記事で紹介したテクニックはJOI勢には「Fishで使うやつ」といった感じで広まっているようです(「StarrySky木」ほどメジャーではないみたいですが)。

また、このテクニックが想定解ではない問題に関しても、このテクニックを知ってると無理やり通すことができることがあります。CatchTheBeat(SRM623DIV1Medium)は、しっかり考察を行えば計算量をO(nlogn)にできるみたいですが、サイズが微妙だったためこのテクニックを用いてO(nlog^2n)でも通すことが出来ました(setのlower_boundなのでlognといってもSegmentTreeよりは春香に速いはずです)。

まとめ

ここに書いた以外でもこのテクニック(名前が付いてないので最後まで微妙な言い回しですみません)を使えば解ける問題があるかもしれませんし、このテクニックを知ることでまた違った景色が見えてくるかもしれません。

今年1年も様々なコンテストが開催されて数多くの問題に出会うことが出来ました。来年もまた素晴らしい問題たちに出会えることを祈りつつ、良いお年を!

2014-05-02WorldFinal12L Takeover Wars

最適戦略は「敵の最も大きいのを潰す」か「自分の大きい方2つを合併する」のどちらか。

ただし、敵の最も大きいのを潰せた時は、敵は自分の最も大きいのを潰せないので、最初の2手だけ調べればいい。(練習会では潰して潰して…とずっと繰り返せると思ってた。頭弱い)

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
lint a[100010],b[100010],c[100010];
bool cal(){
	lint x=a[0],y=b[0];
	rep(i,100005){
		x+=a[i+1];if(y>x) return false;
		y+=b[i+1];if(x>y) return true;
	}
}
int main()
{
	int n,m;
	for(int i=1;cin>>n>>m;i++){
		memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));
		rep(i,n) cin>>a[i];rep(i,m) cin>>b[i];
		sort(a,a+n);reverse(a,a+n);sort(b,b+m);reverse(b,b+m);
		cout<<"Case "<<i<<": ";
		if(cal()){
			cout<<"Takeover Incorporated"<<endl;
		}
		else{
			if(a[0]<b[0]) cout<<"Buyout Limited"<<endl;
			else{
				rep(i,m-1) c[i]=b[i+1];
				memcpy(b,a,sizeof(a));memcpy(a,c,sizeof(c));
				if(cal()) cout<<"Buyout Limited"<<endl;
				else cout<<"Takeover Incorporated"<<endl;
			}
		}
	}
}
|