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




*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
コンサート会場での満足度を求める問題。

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


 #include<stdio.h>
 #include<string.h>
 int ans[51][51][51][51];//ans[n曲目][折った本数][レベル２の本数][レベル１の本数]=満足度
 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はｎ曲目
 		scanf("%d %d %d",&a,&b,&c);
 		for(int j=0;j<=m;j++){
 			//jは折った数
 			for(int L2=0;L2<=j;L2++){
 				//前回折ったＬｅｖｅｌ２の数
 				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);
 }

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
平面上に家が１０万軒存在する。
ある２つの家を取った場合距離Ｒ以内にある家は必ず同じ表札を持ち、３Ｒ以上離れた家は違う表札を持つ。
家の座標が与えられるので何個の表札が存在するか答えよ。

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



 #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
コンサート会場での満足度を求める問題。

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


 #include<stdio.h>
 #include<string.h>
 int ans[51][51][51][51];//ans[n曲目][折った本数][レベル２の本数][レベル１の本数]=満足度
 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はｎ曲目
 		scanf("%d %d %d",&a,&b,&c);
 		for(int j=0;j<=m;j++){
 			//jは折った数
 			for(int L2=0;L2<=j;L2++){
 				//前回折ったＬｅｖｅｌ２の数
 				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);
 }