「aoj2411～2420」の編集履歴（バックアップ）一覧はこちら

aoj2411～2420 - (2013/01/19 (土) 18:25:40) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

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

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