「aoj2411~2420」の編集履歴(バックアップ)一覧に戻る

aoj2411~2420 - (2013/02/21 (木) 00:06:21) のソース

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415
リンク先問題はかなり難しい。
今のところ全く解法を思いついてない。
グラフとして見ると一千六百万本の辺をもつグラフみたいなものだな。
どう格闘しても計算量が落ちないのでとりあえず重さが均等に二分割になるように切っていけば近似解を出せると考えて試作品コードを書いたところで力尽きた。
どうやって解こうかな?

とりあえず切る位置を表すmemo[左側][右側]の4000*4000の配列を用意してい動的計画法で解けばいいのか?
端から攻めていくかな?
とにかくこの手の問題は当たり前に言えることを探し当てて、最後は貪欲法に持って行ければ一番いいパタンだけど?


一つ考えた。
右と左に切断した時、右の個数*右の重さの総計+左の個数*左の重さの総計が最大化される場所できればいいのではないだろうか?



 #include<stdio.h>
 #include<algorithm>
 #include<set>
 #define lli long long int
 struct B{
	lli w;
	int p;
	bool operator<(const B& b)const{
		return w<b.w;
	}
 }; 
 std::set<B> memo;
 lli sums[4002],ans; 
 lli saiki(int down,int up,lli herf){
	if(down+1>=up)return sums[up]-sums[down];
	B b;
	b.w=herf;
	std::set<B>::iterator it=memo.lower_bound(b);
	int p1=(*it).p;
	lli w1=(*it).w;
	lli wR=sums[up]-sums[p1-(herf!=w1)];//右側
	lli wL=sums[p1]-sums[down];//左側
	lli re=0;
	if(wL<wR){
		re=saiki(down,p1,wL/2+sums[down]);
		re+=saiki(p1,up,wR/2+sums[p1]);
	}else{
		re= saiki(p1-(herf!=w1),up,wR/2+sums[p1-(herf!=w1)]);
		re+=saiki(down,p1-(herf!=w1),wL/2+sums[down]);
	}
	ans+=re;
	return re;
 }
 int main(){
	int n;
	lli w;
	std::set<B> body;
	B b;
	b.w=0;
	b.p=0;
	scanf("%d",&n);
	//memo.insert(b);//0番の番兵
	for(int i=1;i<=n;i++){
		scanf("%lld",&w);
		b.p=i;
		b.w+=w;
		sums[i]=b.w;
		memo.insert(b);
	}
	ans=0;
	saiki(0,n,sums[n]/2);
	printf("%lld\n",ans);
 }





*2412 Village
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2412
平面上に家が10万軒存在する。
ある2つの家を取った場合距離R以内にある家は必ず同じ表札を持ち、3R以上離れた家は違う表札を持つ。
家の座標が与えられるので何個の表札が存在するか答えよ。

解法
左端から右端へ精査していきます。
ある家のy座標より上下r以内で、x座標の距離がrまでの家との接続を検証すれば答えが出ます。
このために、x座標が左にある家からソートし、これを一つずつ調べていきます。
接続できるか調べる家の集合はy座標を優先してソートし今検証している家よりr左にある家は消去しながら家を追加していきます。
つながりを表す木構造はどの家もr以内にあるトいうことを利用して一つでも接続が見つかればそれを1本繋げるだけでR以内にある全部の家が木構造でつながります。
この問題最初ずっと前に問題を読んで解を全く思いつかず、何の脈絡もなく今日突然答えを思いついた次第です。



 #include<stdio.h>
 #include<vector>
 #include<map>
 #include<set>
 #include<algorithm>
 #include<math.h>
 
 struct House{
 	double x,y;
 	int no;
 };
 
 class xSorter {
 	public:
 	bool operator()(const House& l, const House& r) const {
 		if(l.x!=r.x)return l.x<r.x;
 		return l.y<r.y;
   	}
 };
 class ySorter {
 	public:
 	bool operator()(const House& l, const House& r) const {
 		if(l.y!=r.y)return l.y<r.y;
 		return l.x<r.x;
   	}
 };
 
 
 
 House hs[200001];
 std::vector<int> cons[200001];
 int spents[200001]={0};
 
 void saiki(int no){
 	spents[no]=1;
 	for(int i=0;i<cons[no].size();i++){
 		if(spents[cons[no][i]]==0){
 			saiki(cons[no][i]);
 		}
 	}
 }
 
 int main(){
 	int n;
 	double r;
 	scanf("%d %lf",&n,&r);
 	for(int i=0;i<n;i++){
 		scanf("%lf %lf",&hs[i].x,&hs[i].y);
 		hs[i].no=i;
 	}
 	std::sort(hs,hs+n,xSorter());
 	std::set<House,ySorter> sHouse;
 	std::set<House,ySorter>::iterator itD,itU,it;
 	House h,hD,hU,h2;
 	int p=0;
 	for(int i=0;i<n;i++){
 		h=hs[i];
 		hD.y=h.y-r-1;
 		hD.x=-10000000;
 		hU.y=h.y+r+1;
 		hU.x=h.x;
 		itD=sHouse.lower_bound(hD);
 		itU=sHouse.upper_bound(hU);
 		for(it=itD;it!=itU;it++){
 			h2=(*it);
 			if(r*1.001>=hypot(h.x-h2.x,h.y-h2.y)){
 				cons[h.no].push_back(h2.no);
  				cons[h2.no].push_back(h.no);
 				break;
 			}
 		}
 		while(h.x-hs[p].x>r*1.001){
 			sHouse.erase(hs[p]);
 			p++;
 		}
 		sHouse.insert(h);
 	}
 	int ans=0;
 	for(int i=0;i<n;i++){
 		if(spents[i]==0){
 			saiki(i);
 			ans++;
 		}
 	}
 	printf("%d\n",ans);
 }








*2417 Flick Input
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2417
スマフォの入力結果をローマ字で表示する問題。

解法
簡単すぎるので特に解法なし。
そのまま手前から処理していくだけです。

 #include<stdio.h>
 
 int main(){
 	char text[1010],c,c1;
	char out2[6]={"aiueo"};
  	char out1[20]={"w kstnhmyrw"};
 	int no;
 	scanf("%s",&text);
 	for(int i=0;text[i]!='\0';i+=2){
 		c=text[i];
 		c1=text[i+1];
 		if(c1=='T')no=0;
 		if(c1=='L')no=1;
 		if(c1=='U')no=2;
 		if(c1=='R')no=3;
 		if(c1=='D')no=4;
 		if(c=='0'){
 			if(c1=='U')printf("nn");
 			if(c1=='T')printf("wa");
 			if(c1=='D')printf("wo");
 		}else if(c=='8'){
 			if(c1=='U')printf("yu");
 			if(c1=='T')printf("ya");
 			if(c1=='D')printf("yo");
 		}else{
 			if(c!='1')printf("%c",out1[c-'0']);
 			printf("%c",out2[no]);
 		}
 	}
 	printf("\n");
 }






*2419 Acrophobia
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2419
マス目に区切られたマップにいる忍者が巻物を集めてゴールまで辿りつく最短タイムを答える問題。

解法
とりあえず何も考えず集めた巻物のセットと現在位置とタイムを基準にダイクストラ法の応用でアセプト。
多分解き方としては教科書的。

 #include<stdio.h>
 #include<map>
 #include<string.h>
 #include<algorithm>
 #include<queue>
 struct P{
 	int x,y,perm,time;
 	bool operator<(const P& p)const{
 		return time>p.time;
 	}
 };
 int timeMemo[32][101][101];
 
 
 int main(){
 	char board[101][101];
  	int timeBoard[101][101];
 	int makimono[101][101];
 	int timeTable[4][4]={	{10000,3,2,1},
 				{3,3,2,1},
 				{2,2,2,1},
 				{1,1,1,1}};
 	int n,m,gx,gy,mNo=1,all=0,w,h;
 	scanf("%d %d",&w,&h);
 	memset(timeBoard,0,sizeof(timeBoard));
 	memset(makimono,0,sizeof(makimono));
 	P p,nextP;
 	
 	for(int i=0;i<h;i++){
 		scanf("%s",board[i]);
 		for(int j=0;board[i][j]!='\0';j++){
 			char c=board[i][j];
 			if(c=='S'){
 				p.x=j;
 				p.y=i;
 				p.perm=0;
 				p.time=0;
  				
 			}else if(c=='G'){
 				gx=j;
 				gy=i;
 			}else if(c=='.'){
 				
 			}else if(c=='#'){
 				for(int dx=0;dx<=3;dx++){
 					for(int dy=0;dy<=3;dy++){
 						if(i+dy<h &&j+dx <w)timeBoard[i+dy][j+dx]=std::max(timeBoard[i+dy][j+dx],timeTable[dy][dx]);
 						if(i+dy<h &&j-dx>=0)timeBoard[i+dy][j-dx]=std::max(timeBoard[i+dy][j-dx],timeTable[dy][dx]);
 						if(i-dy>=0&&j+dx <w)timeBoard[i-dy][j+dx]=std::max(timeBoard[i-dy][j+dx],timeTable[dy][dx]);
 						if(i-dy>=0&&j-dx>=0)timeBoard[i-dy][j-dx]=std::max(timeBoard[i-dy][j-dx],timeTable[dy][dx]);
 					}
 				}
 			}else if(c=='M'){
 				makimono[i][j]=mNo;
 				all+=mNo;
 				mNo*=2;
 			}
 			if(timeBoard[i][j]<1)timeBoard[i][j]=1;
 		}
 	}
 	memset(timeMemo,-1,sizeof(timeMemo));
 	int dxs[]={1,0,-1,0};
 	int dys[]={0,1,0,-1};
 	std::priority_queue<P> qu;
 	qu.push(p);
 	while(qu.empty()==false){
 		p=qu.top();
 		qu.pop();
 		//printf("(%d %d %d %d)",p.perm,p.x,p.y,p.time);
 		if(p.perm==all&&p.x==gx&&p.y==gy)break;
 		if(timeMemo[p.perm][p.y][p.x]!=-1&&timeMemo[p.perm][p.y][p.x]<=p.time)continue;
 		timeMemo[p.perm][p.y][p.x]=p.time;
 		for(int i=0;i<4;i++){
 			nextP.y=p.y+dys[i];
 			nextP.x=p.x+dxs[i];
 			if(nextP.x<0||w<=nextP.x||nextP.y<0||h<=nextP.y)continue;
 			nextP.perm=(p.perm|makimono[nextP.y][nextP.x]);
 			nextP.time=p.time+timeBoard[p.y][p.x];
 			if(timeMemo[nextP.perm][nextP.y][nextP.x]!=-1&&timeMemo[nextP.perm][nextP.y][nextP.x]<=nextP.time)continue;
 			qu.push(nextP);
 		}
 	}
 	printf("%d\n",p.time);
 }








*2420 Anipero 2012
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2420
コンサート会場での満足度を求める問題。

解法
とりあえずベーシックに4次元の動的計画法で解いてみたけど、なんかメモリを大量使用してしまった。
考えるのが難しいから4次元はあまりすきではないな。
何かで次元数を下げることが出来るのかな?


 #include<stdio.h>
 #include<string.h>
 int ans[51][51][51][51];//ans[n曲目][折った本数][レベル2の本数][レベル1の本数]=満足度
 bool calcOK[51][51][51][51];//同上 計算可能のメモ
 int main(){
 	int n,m;
 	int a,b,c;
 	scanf("%d %d",&n,&m);
 	memset(ans,0,sizeof(ans));
 	memset(calcOK,false,sizeof(calcOK));
 	for(int i=0;i<=m;i++){
 		calcOK[0][i][i][0]=true;
 	}
 	
 	int lastAns=-100000000;
 	for(int i=1;i<=n;i++){
 		//iはn曲目
 		scanf("%d %d %d",&a,&b,&c);
 		for(int j=0;j<=m;j++){
 			//jは折った数
 			for(int L2=0;L2<=j;L2++){
 				//前回折ったLevel2の数
 				for(int L1=0;L1+L2<=j;L1++){
 					if(calcOK[i-1][j][L2][L1]==false)continue;
 					int mMax;
 					for(int a1=0;a1<=8&&a1<=L2;a1++){
 						for(int b1=0;b1+a1<=8&&b1<=L1;b1++){
 							if(a1==0&&b1==0)mMax=c;
 							else if(mMax<a*a1+b*b1)mMax=a*a1+b*b1;
 						}
 					}
 					
 					for(int nowL2=0;nowL2+j<=m;nowL2++){
 						if(calcOK[i][j+nowL2][nowL2][L2]==false){
 							ans[i][j+nowL2][nowL2][L2]=ans[i-1][j][L2][L1]+mMax;
 							calcOK[i][j+nowL2][nowL2][L2]=true;
 						}
 						if(ans[i][j+nowL2][nowL2][L2]<ans[i-1][j][L2][L1]+mMax){
 							ans[i][j+nowL2][nowL2][L2]=ans[i-1][j][L2][L1]+mMax;
 						}
 						if(i==n&&lastAns<ans[i][j+nowL2][nowL2][L2])lastAns=ans[i][j+nowL2][nowL2][L2];
 					}
 				}
 			}
 		}
 	}
 	printf("%d\n",lastAns);
 }