2014-12-09

AOJ 0524 - Searching Constellation

AOJ joi 全探索

問題 : Searching Constellation | Aizu Online Judge

JOI 2007 問題4

解法: 全探索

与えられる星の座標を一点ずつ星座の一つ目の座標であると仮定して矛盾(次の星が見つからない)が起きるまで繰り返す(dfs)。
矛盾なく最後の点まで辿り着けばそれが求める星座である。
あとは与えられた星座と求めた星座との相対的な座標を求めればよい。

#include<iostream>
#include<set>
using namespace std;
typedef pair<int,int> P;

set<P> data;
set<P>star;

bool dfs(set<P>::iterator d,set<P>::iterator s){
	if(d==data.end())return false;
	if(s==--star.end())return true;
	set<P>::iterator tmp=++s;
	--s;
	P now=P((*tmp).first-(*s).first,(*tmp).second-(*s).second);
	P next=P((*d).first+now.first,(*d).second+now.second);
	
	return dfs(data.find(next),++s);
}

int main(){
	int n;
	while(cin>>n && n){
		data.clear();
		star.clear();
		for(int i=0;i<n;i++){
			P a;
			cin>>a.first>>a.second;
			star.insert(a);
		}
		int m;
		cin>>m;
		for(int i=0;i<m;i++){
			P a;
			cin>>a.first>>a.second;
			data.insert(a);
		}
		P ans;
		for(set<P>::iterator itr=data.begin();itr!=data.end();itr++){
			if(dfs(itr,star.begin()))ans=P((*itr).first-(*star.begin()).first,(*itr).second-(*star.begin()).second);
		}
		
		cout<<ans.first<<" "<<ans.second<<endl;
	}
}

個人的にはゴツゴツした全探索といった印象。
なんとなく抵抗がある。

イテレータが乱雑で冗長なコードになってしまったのも一つ原因である気がする。

2014-12-08

AOJ 0568 - Pasta

AOJ dp joi

問題 : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0568

解法: DP

dp[i][j][k]:=i日目にj-1番目のパスタをk日連続で使ったとした時の通りの数。
ただし $(1\le i\le n,1\le j\le 3,1\le k\le2)$

漸化式は
dp[i][j][1]=dp[i-1][a][1]+dp[i-1][a][2]+dp[i-1][b][1]+dp[i-1][b][2] ただし $(a,b\neq j)$
dp[i][j][2]=dp[i-1][j][1] $\cdots$ ※

と出来る。

※ (2日連続で使うのは前日に(1日だけ)同じパスタを選んでいた場合のみであるから)

あとは条件に従いパスタが決まっている日はそのパスタだけを使うようにすれば良い。

#include<iostream>
#include<map>

#define MOD 10000

using namespace std;

map<int,int>data;

int dp[200][3][3]={0};

int main(){
	int n,k;
	cin>>n>>k;
	for(int i=0;i<k;i++){
		int a,b;
		cin>>a>>b;
		data[a]=b;
	}
	
	for(int i=1;i<=n;i++){
		map<int,int>::iterator pa;
		bool it=false;
		if(data.find(i)!=data.end()){
			pa=data.find(i);
			it=true;
		}
		
		if(i==1){
			if(it){
				dp[i][pa->second-1][1]=1;
			}
			else {
				for(int j=0;j<3;j++){
					dp[i][j][1]=1;
				}
			}
		}
		else {
			if(it){
				for(int j=0;j<3;j++){
					if(j!=pa->second-1)dp[i][pa->second-1][1]+=dp[i-1][j][1]+dp[i-1][j][2];
					dp[i][pa->second-1][1]%=MOD;
				}
				dp[i][pa->second-1][2]=dp[i-1][pa->second-1][1];
			}
		
			else {
				for(int k=0;k<3;k++){
					for(int j=0;j<3;j++){
						if(j!=k)dp[i][k][1]+=dp[i-1][j][1]+dp[i-1][j][2];
						dp[i][k][1]%=MOD;
					}
					dp[i][k][2]=dp[i-1][k][1];
				}
				
			}
		}
		
	}
	
	int ans=0;
	for(int i=0;i<3;i++){
		ans+=dp[n][i][1]+dp[n][i][2];
	}
	cout<<ans%MOD<<endl;
}

2014-11-24

CF #279(Div2) D - Chocolate

CodeForces Div2

問題 : Problem - 490D - Codeforces

概要 :

二本のチョコバーの縦と横の長さがそれぞれ整数で与えられる。
それらを(水平方向もしくは垂直方向に) $\frac{1}{2}$ を食べるか, $\frac{1}{3}$ を食べるかしてそれらの面積を等しくしたい。この時かかる最小の手数(問題では時間だがここでは手数としておく)を求める。また、最終的な二本の縦と横の長さも出力する。

解法 :
二本のチョコバーの面積をそれぞれ $S_1,S_2$ ,縦、横の長さを $x_1,y_1,x_2,y_2$ とすると
$S_1=x_1 \times y_1=2^a\times 3^b\times n$
$S_2=x_2 \times y_2=2^c\times 3^d\times m$
と表せる。
この時に $n\neq m$ であったならどのような操作をしても同じ面積にはならない。
逆に $n=m$ ならば必ず同じ面積にすることが出来る。

ここでそれぞれの操作について
操作(1): $\frac{1}{2}$ 食べる -> $S$ の因数から2を1つ取り除く
操作(2): $\frac{1}{3}$ 食べる -> $S$ の因数の中の3を2に変える
と言い換えることができるので
まず, $b=d$ になるまで(2)を繰り返し
その後 $a=c$ になるまで(1)を繰り返す

これで最終的に $S_1=S_2$ となる。

#include<iostream>
#include<set>
#include<vector>
using namespace std;


int main(){
	long long x1,y1,x2,y2;
	cin>>x1>>y1;
	cin>>x2>>y2;
	long long ma=max(x1,max(x2,max(y1,y2))); 
	vector<int> s1,s2;
	int n1[2]={0,0},n2[2]={0,0};
	
	long long tmp1=x1,tmp2,tmp;
	while(tmp1%2==0){tmp1/=2;n1[0]++;}
	while(tmp1%3==0){tmp1/=3;n1[1]++;}
	
	tmp2=y1;
	while(tmp2%2==0){tmp2/=2;n1[0]++;}
	while(tmp2%3==0){tmp2/=3;n1[1]++;}
	
	tmp=tmp2*tmp1;
	
	 tmp1=x2;
	while(tmp1%2==0){tmp1/=2;n2[0]++;}
	while(tmp1%3==0){tmp1/=3;n2[1]++;}
	 tmp2=y2;
	while(tmp2%2==0){tmp2/=2;n2[0]++;}
	while(tmp2%3==0){tmp2/=3;n2[1]++;}
	
	
	int co=0;
	if(tmp!=tmp1*tmp2){
		cout<<-1<<endl;
		return 0;
	}

	while(n1[1]>n2[1]){
		n1[1]--;
		n1[0]++;
		co++;
		if(x1%3==0)x1=(x1*2)/3;
		else y1=(y1*2)/3;
	}
	while(n1[1]<n2[1]){
		n2[1]--;
		n2[0]++;
		co++;
		if(x2%3==0)x2=(x2*2)/3;
		else y2=(y2*2)/3;
	}
	while(n1[0]>n2[0]){
		n1[0]--;
		co++;
		if(x1%2==0)x1/=2;
		else y1/=2;
	}
	while(n2[0]>n1[0]){
		n2[0]--;
		co++;
		if(x2%2==0)x2/=2;
		else y2/=2;
	}
	cout<<co<<endl;
	cout<<x1<<" "<<y1<<endl;
	cout<<x2<<" "<<y2<<endl;
}

2014-11-22

AOJ 0557 - A First Grader

AOJ dp joi

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557

JOI 2010予選問題4

解法 :

dp[i][j]:=i番目の数まで使って(足すか引くかして)jを作ることが出来る通りの数

※dp[0][0]=1で初期化した場合以下のコードではdp[1][0]=2となってしまうので注意

#include<iostream>

using namespace std;

long long dp[110][22]={0};

int main(){
	int n;
	cin>>n;
	int a;
	cin>>a;
	dp[1][a]=1;  //初期化
	for(int i=2;i<n;i++){
		int x;
		cin>>x;
		for(int j=0;j<21;j++){
			if(j+x<21)dp[i][j+x]+=dp[i-1][j];
			if(j-x>=0)dp[i][j-x]+=dp[i-1][j];
		}
	}
	int c;
	cin>>c;
	cout<<dp[n-1][c]<<endl;
}

2014-11-22

AOJ 0168 - Kannondou

AOJ dp pck

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0168

解法 :

一つ前の状態を考える。
i段目にいるためには
i-1段目から1段,
i-2段目から2段,
i-3段目から3段
登る場合のみである。

トリボナッチ数を作る
$dp_i=dp_{i-1}+dp_{i-2}+dp_{i-3}$

#include<iostream>

using namespace std;

int dp[35];

int main(){
	dp[0]=1;
	dp[1]=1;
	dp[2]=2;
	for(int i=3;i<31;i++){
		dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
	}
	
	int n;
	while(cin>>n && n){
		cout<<dp[n]/3650+(dp[n]%3650!=0)<<endl;
	}
}

2014-11-10

poj 3616 - Milking Time

poj dp 蟻

問題 : http://poj.org/problem?id=3616

解法 :
DP(動的計画法)
dp[i][j]:=i回目にj番目の $interval$ (?)を行った時の最大値

dp[i][j]= $\max\{dp_{i-1,k}|0\le k< M\}+efficiency_j$ (kのあとr時間後にjが実行できれば)

TLEの関係でstartの時間でソートして適当に実行時間を削っています。

#include<iostream>
#include<algorithm>
using namespace std;

struct milk{
	int start;
	int end;
	int ef;
};

bool gre(const milk l,const milk r){
	return l.start<r.start;
}

milk data[2000];
int dp[2000][2000];
int main(){
	int n,m,r;
	cin>>n>>m>>r;
	
	for(int i=0;i<m;i++){
		cin>>data[i].start>>data[i].end>>data[i].ef;
	}
	sort(data,data+m,gre);
	for(int i=0;i<m;i++){
		dp[0][i]=data[i].ef;
	}
	
	
	
	int ans=0;
	for(int i=1;i<=m;i++){
		bool e=true;
		for(int j=i;j<m;j++){
			int ma=0;
			for(int k=i-1;k<m;k++){
				if(data[j].start>=data[k].end+r && dp[i-1][k]>ma)ma=dp[i-1][k];
			}
			if(ma>0){
				dp[i][j]=ma+data[j].ef;
				if(dp[i][j]>ans)ans=dp[i][j];
				e=false;
			}
			else dp[i][j]=-1;
		}
		if(e)break;
	}
	
	cout<<ans<<endl;
}

2014-11-07

AOJ 0269 - EastWind

プログラミング AOJ 幾何 pck

問題 : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0269

平面幾何の参考にしたサイト : http://www.deqnotes.net/acmicpc/2d_geometry/

解法 :

点とそれぞれの扇型とを全て判定する。
扇型と点との判定
[1] : 点が半径内にあるかどうか
[2] : 扇内に点があるかどうか
扇の境界の二本のベクトル(v1,v2)と扇の中心から点へのベクトル(vとする)との外積を用いて判定する
(w+d/2)度のベクトルをv1,(w-d/2)とのベクトルをv2,外積の関数をcrossとすると
cross(v1,v)がCW(ClockWise|外積の符号が-)且つcross(v2,v)がCCW(CounterClockWise|外積の符号が+)

上記の[1][2]を満たせばその点は扇内にある

#include<iostream>
#include<vector>
#include<math.h>
#include<complex>

#define EPS 1e-4

#define PI 3.141592
#define EQ(a,b) (abs((a)-(b))<EPS)
using namespace std;

typedef complex<double> P;

vector<P> house;
vector<P> ume,sak,mo;

double cross(P v1,P v2){
	return v1.real()*v2.imag()-v1.imag()*v2.real();
}

bool che(P h,P t,double d,double w,double a){
	P v=h-t;
	if(!(abs(v)<a))return false;
	
	P v1=P(a*cos((w+d/2)/180*PI),a*sin((w+d/2)/180*PI));
	P v2=P(a*cos((w-d/2)/180*PI),a*sin((w-d/2)/180*PI));
	
	if(cross(v1,v)<0 && cross(v2,v)>0)return true;
	else return false;
}

int main(){
	int h,r;
	
	while(cin>>h>>r && h&&r){
		house.clear();
		ume.push_back(P(0,0));
		for(int i=0;i<h;i++){
			int x,y;
			cin>>x>>y;
			house.push_back(P(x,y));
		}
		
		int U,M,S,du,dm,ds;
		cin>>U>>M>>S>>du>>dm>>ds;
		for(int i=0;i<U;i++){
			int x,y;
			cin>>x>>y;
			ume.push_back(P(x,y));
		}
		for(int i=0;i<M;i++){
			int x,y;
			cin>>x>>y;
			mo.push_back(P(x,y));
		}
		for(int i=0;i<S;i++){
			int x,y;
			cin>>x>>y;
			sak.push_back(P(x,y));
		}
		
		
		int data[120];
		for(int i=0;i<120;i++)data[i]=0;
		for(int z=0;z<r;z++){
			int w,a;
			cin>>w>>a;
			
			for(int i=0;i<house.size();i++){
				bool ok=false;
				if(che(house[i],ume[0],du,w,a))ok=true;
				else continue;
				for(int j=1;j<=U;j++){
					if(che(house[i],ume[j],du,w,a))ok=false;
				}
				for(int j=0;j<M;j++){
					if(che(house[i],mo[j],dm,w,a))ok=false;
				}
				for(int j=0;j<S;j++){
					if(che(house[i],sak[j],ds,w,a))ok=false;
				}
				
				if(ok)data[i]++;
			}
		}
		
			int ans=0;
			int tmp=-1;
			for(int i=0;i<h;i++){
				if(ans<=data[i]){
					ans=data[i];
					tmp=i;
				}
			}
			if (ans==0)cout<<"NA"<<endl;
			else {
				for(int i=0;i<h;i++){
					if(i==tmp)cout<<i+1;
					else if(data[i]==ans)cout<<i+1<<" ";
					
				}
				cout<<endl;
			}
			
		
	}
}

ゴリラ系情報系男子大学生の日記

八割備忘録

AOJ 0524 - Searching Constellation

AOJ 0568 - Pasta

CF #279(Div2) D - Chocolate

AOJ 0557 - A First Grader

AOJ 0168 - Kannondou

poj 3616 - Milking Time

AOJ 0269 - EastWind