AOJ 1156,2444

試験も近いのにAOJ。しかも簡単な問題。

1156
Dijkstraするだけ。

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int c[5];
int m[50][50];
int ijk[50][50][4];
int v[50][50][4];
int main(){
	int a,b;
	while(scanf("%d%d",&b,&a),a){
		for(int i=0;i<a;i++)
			for(int j=0;j<b;j++)
				scanf("%d",&m[i][j]);
		for(int i=0;i<4;i++)scanf("%d",c+i);
		priority_queue<pair<pair<int,int>,pair<int,int> > >Q;
		Q.push(make_pair(make_pair(0,0),make_pair(0,0)));
		for(int i=0;i<a;i++)
			for(int j=0;j<b;j++)
				for(int k=0;k<4;k++){
					ijk[i][j][k]=999999999;
					v[i][j][k]=0;
				}
		ijk[0][0][0]=0;
		while(Q.size()){
			int cost=-Q.top().first.first;
			int dir=Q.top().first.second;
			int row=Q.top().second.first;
			int col=Q.top().second.second;
			Q.pop();
			if(v[row][col][dir])continue;
			v[row][col][dir]=1;
			for(int i=0;i<4;i++){
				int val=cost;
				if(m[row][col]!=i){
					val+=c[i];
				}
				int tr=row;
				int tc=col;
				int td=dir;
				if(i==1)td=(td+1)%4;
				if(i==2)td=(td+2)%4;
				if(i==3)td=(td+3)%4;
				tr+=dx[td];
				tc+=dy[td];
				if(0<=tr&&tr<a&&0<=tc&&tc<b&&!v[tr][tc][td]&&ijk[tr][tc][td]>val){
					ijk[tr][tc][td]=val;
					Q.push(make_pair(make_pair(-val,td),make_pair(tr,tc)));
				}
			}
		}
		int ret=999999999;
		for(int i=0;i<4;i++)ret=min(ret,ijk[a-1][b-1][i]);
		printf("%d\n",ret);
	}
}

2444
数年ぶりにRolling Hashを書いたらいろいろハマった。ちなみに新しいほうのC++ではhashという配列でコンパイルエラーした。

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef unsigned long long wolf;
char str[1000000];
char tmp[16];
wolf key=1000000007;
wolf v[1000000];
wolf hash[1000000];
wolf pow[1000000];
int main(){
	int a,b;
	scanf("%d%d%s",&a,&b,str);
	wolf now=0;
	wolf val=1;
	for(int i=0;i<500000;i++){
		now+=str[i]*val;
		hash[i+1]=now;
		pow[i]=val;
		val*=key;
	}
	int L=0;
	int R=1;
	//for(int i=1;i<=a;i++)printf("%llu\n",hash[i]);
	for(int i=0;i<b;i++){
		scanf("%s",tmp);
		if(tmp[0]=='L'&&tmp[1]=='+')L++;
		if(tmp[0]=='L'&&tmp[1]=='-')L--;
		if(tmp[0]=='R'&&tmp[1]=='+')R++;
		if(tmp[0]=='R'&&tmp[1]=='-')R--;
		
		v[i]=(hash[R]-hash[L])*pow[a-L];
	//	printf("%d %d %llu %llu\n",L,R,hash[R]-hash[L],v[i]);
	}
	std::sort(v,v+b);
	int ret=1;
	for(int i=1;i<b;i++)if(v[i]!=v[i-1])ret++;
	printf("%d\n",ret);
}