kmjp's blog

競技プログラミング参加記です

KUPC2013 : E - すごろく

Dはスタックというヒントを目にしてしまったが、E・Fは自力で解けたぞ。
http://kupc2013.contest.atcoder.jp/tasks/kupc2013_e

問題

1~Mの1列に並んだMマスからなるすごろくがある。
また、サイコロ6面に書かれた数字が与えられる。

サイコロを振って出た目に対し、プレイヤーはその分左に進むか、右に進むか、その場にとどまるか選択することができる。
各マスには数値が書かれており、サイコロを振って左右に進んだ場合、その分さらに進む。

ここで、サイコロを最大3000回振ることができる。
サイコロを振るたびに出た目に対し、左右どちらに進むかまたは留まるかを答える、という処理を繰り返す。
開始マスと終了マスが与えられたとき、サイコロ3000回以内にゴールするよう進む方向を答えよ。

解法

まず、各マスにおいて6通りの目それぞれが出たときに左右に進んだ場合、どのマスに到達するかを求める。
また、その情報を元に終了マスまでの最低サイコロを振る回数を求める。

後は、M<=300のため、最悪でも299回理想の目が出れば終了マスにたどりつくことができる。
サイコロは3000回振るので、1/6の確率で理想の目が出れば十分ゴールできる。
後はサイコロの目に対し、終了マスまでのサイコロを振る回数が少なくて済むマスに移動していけばよい。

int M;
int A[6];
int S,G;
int GT[301][6][2],N[301];
int dist[301][301];

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	
	M=GETi();
	FOR(i,6) A[i]=GETi();
	S=GETi()-1;
	G=GETi()-1;
	FOR(i,M) N[i]=GETi();
	
	FOR(y,M) FOR(x,M) dist[y][x]=301;
	
	FOR(x,M) {
		FOR(y,6) {
			GT[x][y][0]=GT[x][y][1]=-1;
			if(x+A[y]<M) {
				GT[x][y][0]=x+A[y]+N[x+A[y]];
				dist[x][x+A[y]+N[x+A[y]]]=1;
			}
			if(x-A[y]>=0) {
				GT[x][y][1]=x-A[y]+N[x-A[y]];
				dist[x][x-A[y]+N[x-A[y]]]=1;
			}
		}
	}
	dist[G][G]=0;
	
	FOR(i,M) FOR(j,M) FOR(k,M) dist[j][k] = min(dist[j][k], dist[j][i]+dist[i][k]);
	
	for(i=0;i<3000 && S!=G;i++) {
		scanf("%d", &j);
		j--;
		k=S;l=0;
		if(GT[S][j][0]!=-1 && dist[GT[S][j][0]][G]<dist[k][G]) k=GT[S][j][0],l=1;
		if(GT[S][j][1]!=-1 && dist[GT[S][j][1]][G]<dist[k][G]) k=GT[S][j][1],l=-1;
		printf("%d\n",l);
		fflush(stdout);
		S=k;
	}
	return;
	
}

まとめ

先にサイコロの目がすべてわからない、という点がポイント。
幸いすんなりと答えが思いついた。