TopCoder SRM 788 : Div2 Hard SquareCityWalking

Div2 Hardにしては簡単。
https://community.topcoder.com/stat?c=problem_statement&pm=16140&rd=18085

問題

N*Nのグリッドがあり、各セルに1～100の範囲の整数値が書かれている。
左上のセルから右下のセルに向け、隣接マスをたどって最短経路を移動するパスを考える。

経路上の値のGCDとしてあり得る最大値を求めよ。

解法

セルの整数値の範囲が狭いので、解vを100から1まで降順に探索しよう。
その際、vが解となりうるならば、vの倍数の書かれたセルだけ通って移動可能となるので、それをDPで判定すればよい。

int dp[25][25];

class SquareCityWalking {
	public:
	int largestGCD(int N, vector <int> A) {
		for(int v=100;v>=1;v--) {
			ZERO(dp);
			dp[0][0]=1;
			int y,x;
			FOR(y,N) FOR(x,N) {
				if(A[y*N+x]%v) dp[y][x]=0;
				if(dp[y][x]) {
					if(x+1<N) dp[y][x+1]=1;
					if(y+1<N) dp[y+1][x]=1;
				}
			}
			if(dp[N-1][N-1]) return v;
		}
		
	}
}

まとめ

最短経路、の縛りなくてもいい気がするけど、なんでこれ入れたんだろ。