Factorial: 階乗

解法

• nを素因数分解して
• p1^e1*p2^e2*p3^e3*......pr^erとなったとき、 m1!%p1^e1==0,m2!%p2^e2,m3!%p3^e3,.....となる
• 最小のm1,m2,m3...を求めて
• m1,m2,m3....の中で最も大きな値が答え

#include <stdio.h>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
vector<pair<LL,int> > primeFactor(LL num){ //first->prime,second->pow{
	if(num==1){
		vector<pair<LL,int> > r;
		r.push_back(make_pair(1,1));
		return r;
	}
	else{
		vector<pair<LL,int> > r;
		for(LL i=2;i*i<=num;i++){
			if(num%i==0){
				int p=0;
				while(num%i==0)
					num/=i,p++;
				r.push_back(make_pair(i,p));
			}
		}
		if(num!=1)
			r.push_back(make_pair(num,1));
		return r;
	}
}
int main(){
	LL n;
	scanf("%lld",&n);
	vector<pair<LL,int> > ps=primeFactor(n);
	LL res=0;
	for(int i=0;i<(int)ps.size();i++){
		LL a=0,b=ps[i].second;
		while(0<b){
			a+=ps[i].first;
			for(LL t=ps[i].first;a%t==0;t*=ps[i].first)
				b--;
		}
		res=max(res,a);
	}
	printf("%lld\n",res);
	return 0;
}

AOJ 1203

• 問題文要約

記号を含む文字列が与えられるので、記号を除いて小文字を大文字に変換した後その文字列が含む回文を列挙せよ。ただしcXcとなる回文が存在した場合Xを出力してはならない。

• 解法

dp[i][j]=(i文字目からj文字目までが回文となっているかどうか) でDPする。

#include <string>
#include <iostream>
#include <set>
#include <string.h>
using namespace std;
int dp[1030][1030];
int main(){
	string s;
	while(getline(cin,s)){
		string in;
		for(int i=0;i<(int)s.size();i++)
			if('A'<=s[i]&&s[i]<='Z')	in+=s[i];
			else if('a'<=s[i]&&s[i]<='z')	in+=s[i]-'a'+'A';
		int n=in.size();
		memset(dp,0,sizeof(dp));
		set<string> ans,ng;
		for(int i=0;i<n;i++)
			dp[i][i]=1,dp[i][i+1]=1;
		for(int l=2;l<=n;l++)
			for(int i=0;i+l<=n;i++)
				if(dp[i+1][i+1+l-2]==1&&in[i]==in[i+l-1]){
					dp[i+1][i+l-2]=0;
					ng.insert(in.substr(i+1,l-2));
					dp[i][i+l]=1;
					ans.insert(in.substr(i,l));
				}
		for(set<string>::iterator it=ans.begin();it!=ans.end();it++)
			if(3<=(*it).size()&&ng.find(*it)==ng.end())
				cout<<*it<<" ";
		cout<<endl;
	}
	return 0;
}

AOJ 1204

• 解法

最後のnクロックの状態と次にpipelineに入れられる仕事の番号を使って拡張ダイクストラをする。int dist[21][1<<20]とかやるとMLEするのでsetを使う。

//AOJ1204
#include <stdio.h>
#include <vector>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <set>
#define INF (1<<20)
#define W 10
using namespace std;
struct State{
	int time,next,line;
};
State makeS(int t,int nn,int l){
	State s;
	s.time=t,s.next=nn,s.line=l;
	return s;
}
bool operator < (const State &s,const State &t){
	return s.time>t.time;
}
int n;
int used[5];
char as[5][30];
int pi[30];
int check(int line){
	memset(used,0,sizeof(used));
	for(int i=n-1;0<=i;i--)
		if(line&(1<<i))
			used[pi[n-1-i]]++;
	for(int i=0;i<5;i++)
		if(1<used[i])
			return 0;
	return 1;
}
int main(){
	while(1){
		scanf("%d",&n);
		if(n==0)	break;
		for(int i=0;i<5;i++)scanf("%s",as[i]);
		for(int i=0;i<n;i++)for(int j=0;j<5;j++)if(as[j][i]=='X')pi[i]=j;
		int ans;
		priority_queue<State> que;
		set<pair<int,int> > se;
		que.push(makeS(0,0,0));
		se.insert(make_pair(0,0));
		while(!que.empty()){
			State s=que.top();que.pop();
			if(s.next==10&&s.line==1){ans=s.time;break;}
			int l=s.line>>1,ok=check(l);
			if(!ok)	continue;
			if(s.next==W){
				if(se.find(make_pair(W,l))==se.end()){
					se.insert(make_pair(W,l));
					que.push(makeS(s.time+1,W,l));
				}
			}else{
				int ll=l|(1<<(n-1));
				if(check(ll)){
					if(se.find(make_pair(s.next+1,ll))==se.end()){
						se.insert(make_pair(s.next+1,ll));
						que.push(makeS(s.time+1,s.next+1,ll));
					}
				}
				if(se.find(make_pair(s.next,l))==se.end()){
					se.insert(make_pair(s.next,l));
					que.push(makeS(s.time+1,s.next,l));
				}
			}
		}
		printf("%d\n",ans);
	}
}

JOI2012本選5番

ダイクストラして最大全域木求めてLCAする全部入り問題。

#include <vector>
#include <queue>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
#define MAX_V 100000+10
#define MAX_Q 100000+10
#define INF (1<<28)
#define ROOT 1
using namespace std;
struct Edge{
	int to,cost;
};
Edge makeE(int t,int c){
	Edge e;e.to=t,e.cost=c;
	return e;
}
bool operator < (const Edge &e,const Edge &f){
	return e.cost>f.cost;
}
struct Biedge{
	int a,b,cost;
};
Biedge makeB(int aa,int bb,int c){
	Biedge e;e.a=aa,e.b=bb,e.cost=c;
	return e;
}
bool operator < (const Biedge &e,const Biedge &f){
	return e.cost>f.cost;
}
class Unionfind{
	public:
		vector<int> data;
		Unionfind(int n){
			for(int i=0;i<n;i++)
				data.push_back(i);
		}
		int root(int a){
			//printf("root(%d)\n",a);
			if(data[a]==a)	return a;
			else		return data[a]=root(data[a]);
		}
		void set(int a,int b){
			if(root(a)==root(b))
				return;
			else
				data[root(a)]=root(b);
		}
};
int fest[MAX_V],dist[MAX_V],qa[MAX_Q],qb[MAX_Q],qr[MAX_Q],depth[MAX_V],score[32][MAX_V],parent[32][MAX_V];
vector<Biedge> biedge;
vector<Edge> G[MAX_V];
vector<Edge> MG[MAX_V];
void dfs(int v,int p,int s,int d){
	parent[0][v]=p;
	score[0][v]=s;
	depth[v]=d;
	for(int i=0;i<(int)MG[v].size();i++)
		if(MG[v][i].to!=p)
			dfs(MG[v][i].to,v,MG[v][i].cost,d+1);
}
void init(int n){
	dfs(ROOT,-1,dist[ROOT],0);
	for(int k=0;k+1<32;k++)
		for(int i=0;i<n;i++){
			if(parent[k][i]<0)	parent[k+1][i]=-1;
			else{
				score[k+1][i]=min(score[k][parent[k][i]],score[k][i]);
				parent[k+1][i]=parent[k][parent[k][i]];
			}
		}
}
int lca(int u,int v){
	int res=INF;
	if(depth[u]>depth[v])	swap(u,v);
	for(int k=0;k<32;k++)
		if((depth[v]-depth[u])>>k&1){
			res=min(res,score[k][v]);
			v=parent[k][v];
		}
	//printf("lca-m\n");fflush(stdout);
	if(u==v)	return res;
	for(int k=31;0<=k;k--)
		if(parent[k][u]!=parent[k][v]){
			res=min(res,score[k][u]);
			u=parent[k][u];
			res=min(res,score[k][v]);
			v=parent[k][v];
		}
	res=min(res,score[0][u]);
	res=min(res,score[0][v]);
	return res;
}
int main(){
	int n,m,k,q;
	scanf("%d%d%d%d",&n,&m,&k,&q);
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		G[a].push_back(makeE(b,c));
		G[b].push_back(makeE(a,c));
		biedge.push_back(makeB(a,b,0));
	}
	for(int i=0;i<k;i++)
		scanf("%d",fest+i);
	for(int i=0;i<q;i++)
		scanf("%d%d",qa+i,qb+i);
	for(int i=0;i<MAX_V;i++)
		dist[i]=INF;
	priority_queue<Edge> que;
	for(int i=0;i<k;i++){
		que.push(makeE(fest[i],0));
		dist[fest[i]]=0;
	}
	while(!que.empty()){
		int t=que.top().to,c=que.top().cost;
		que.pop();
		if(dist[t]<c)
			continue;
		for(int i=0;i<(int)G[t].size();i++){
			int tt=G[t][i].to,cc=c+G[t][i].cost;
			if(cc<dist[tt]){
				que.push(makeE(tt,cc));
				dist[tt]=cc;
			}
		}
	}
	for(int i=0;i<m;i++)
		biedge[i].cost=min(dist[biedge[i].a],dist[biedge[i].b]);
	sort(biedge.begin(),biedge.end());
	memset(qr,-1,sizeof(qr));
	Unionfind un(n+1);
	for(int i=0;i<m;i++){
		if(un.root(biedge[i].a)!=un.root(biedge[i].b)){
			un.set(biedge[i].a,biedge[i].b);
			MG[biedge[i].a].push_back(makeE(biedge[i].b,biedge[i].cost));
			MG[biedge[i].b].push_back(makeE(biedge[i].a,biedge[i].cost));
		}
	}
	init(n+1);
	for(int i=0;i<q;i++)
		printf("%d\n",lca(qa[i],qb[i]));
	return 0;
}

JOI2012本選４番

講義資料 - いもす研 (imos laboratory)
↑参照。
累積和を使ったコード

#include <stdio.h>
int nails[5010][5010];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b,x;
		scanf("%d%d%d",&a,&b,&x);
		nails[a][b]++,nails[a][b+1]--;
		nails[a+x+1][b]--,nails[a+x+2][b+1]++;
		nails[a+x+1][b+x+2]++,nails[a+x+2][b+x+2]--;
	}
	for(int i=0;i<5010;i++){
		int a=0;
		for(int j=0;j<5010;j++){
			a+=nails[i][j];
			nails[i][j]=a;
		}
	}
	for(int i=0;i<5010;i++){
		int a=0;
		for(int j=0;j<5010;j++){
			a+=nails[j][i];
			nails[j][i]=a;
		}
	}
	for(int i=0;i<5010;i++){
		int a=0;
		for(int j=0;i+j<5010;j++){
			a+=nails[i+j][j];
			nails[i+j][j]=a;
		}
	}
	int ans=0;
	for(int i=0;i<5010;i++)
		for(int j=0;j<5010;j++)
			if(0<nails[i][j])
				ans++;
	printf("%d\n",ans);
	return 0;
}

最大値の伝搬を使ったコード（ただし後ろから）。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int nails[5010][5010];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	memset(nails,0,sizeof(nails));
	for(int i=0;i<m;i++){
		int a,b,x;
		scanf("%d%d%d",&a,&b,&x);
		nails[a+x][b+x]=max(nails[a+x][b+x],x+1);
	}
	int ans=0;
	for(int y=n;0<=y;y--)
		for(int x=n;0<=x;x--){
			if(0<nails[y][x])
				ans++;
			if(0<x)
				nails[y][x-1]=max(nails[y][x-1],nails[y][x]-1);
			if(0<x&&0<y)
				nails[y-1][x-1]=max(nails[y-1][x-1],nails[y][x]-1);
		}
	printf("%d\n",ans);
	return 0;
}

JOI2012本選3番

時間がSにかぶるときだけ気をつけてdpすればOK。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n,S,T;
int A[3010],B[3010];
int dp[3010][3010];
int rec(int store,int time){
	if(store==n)
		return 0;
	else if(dp[store][time]!=-1)
		return dp[store][time];
	else{
		int res=rec(store+1,time);
		if(time<S&&S<time+B[store]){
			if(S+B[store]<=T){
				res=max(res,rec(store+1,S+B[store])+A[store]);
			}
		}else{
			if(time+B[store]<=T){
				res=max(res,rec(store+1,time+B[store])+A[store]);
			}
		}
		return dp[store][time]=res;
	}
}
int main(){
	scanf("%d%d%d",&n,&T,&S);
	for(int i=0;i<n;i++)
		scanf("%d%d",A+i,B+i);
	memset(dp,-1,sizeof(dp));
	int ans=rec(0,0);
	printf("%d\n",ans);
	return 0;
}

JOI2012本選2番

dp[ap=Aの何枚目か][bp=Bの何枚目か]でDPした。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[5010][5010];
int ac[5010],bc[5010];
int rec(int ap,int bp){
	if(ap<0||bp<0)
		return 0;
	else if(dp[ap][bp]!=-1)
		return dp[ap][bp];
	else{
		int r=rec(ap-1,bp);
		if(ac[ap]==bc[bp])
			r=max(r,rec(ap-1,bp-1)+1);
		return dp[ap][bp]=r;
	}
}
int main(){
	int an,bn;
	scanf("%d%d",&an,&bn);
	for(int i=0;i<an;i++)
		scanf("%d",ac+i);
	for(int i=0;i<bn;i++)
		scanf("%d",bc+i);
	memset(dp,-1,sizeof(dp));
	int ans=0;
	for(int i=0;i<an;i++)
		for(int j=0;j<bn;j++)
			ans=max(ans,rec(i,j));
	printf("%d\n",ans);
	return 0;
}