SRM583 Div2 hard GameOnABoard

topcoder

問題
AさんとBさんがゲームしてます。
Aさんはスコアを小さくしたくて、Bさんはスコアを大きくしたいです。

グリッド上の盤面の各マスには０か１かの数字が振ってあります。
あるパスのコストは、そのパスがたどるマス（始点と終点を含む）の数字の和になります。

Aさんが先にマス目の１マス目を決め、
Bさんが次に２マス目を決めます。

その２マスを始点と終点とするパスのなかでコストが最少なもののコストをスコアとします。
AさんとBさんが最適な戦略を取ってマスを選んだ時、スコアはどうなるでしょう？


解法
全点間の最小距離を求めます。
ところが入力のグリッドサイズが最大40*40で1600頂点あるので、愚直にワーシャルフロイド法ではTLEしてしまいます。

で、なんで間に合うのかまだかっちり分かってないんですが、枝刈りBFS的な感じでコスト更新できる隣接点どんどんキューに突っ込んでいくと間に合いました（というか効率的探索方法がわからなくて解いた人のコード見たら大体そんな感じでした）。

プログラム

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

#define li			long long int
#define rep(i,to)	for(int i=0;i<((int)(to));i++)
#define repp(i,start,to)	for(int i=(int)(start);i<((int)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define allof(v)	(v).begin(),(v).end()
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl

li table[1600];
li dp[1600][1600];
li w,h;

class GameOnABoard {
	public:
	
	bool adj(li a,li b){
		li ah=a/w;
		li aw=a%w;
		li bh=b/w;
		li bw=b%w;
		return (abs(ah-bh)+abs(aw-bw)==1);
	}
	
	int optimalChoice(vector <string> cost) {
		w=sz(cost[0]);
		h=sz(cost);
		rep(y,sz(cost)){
			rep(x,sz(cost[0]))table[y*w+x]=cost[y][x]-'0';
		}
		
		li n=w*h;
		rep(i,n)rep(j,n)dp[i][j]=50000;
		rep(i,n)dp[i][i]=table[i];
		
		li dx[4]={-1,1,0,0};
		li dy[4]={0,0,-1,1};
		rep(i,n){
			queue<li> q;
			q.push(i);
			rep(j,n)visited[j]=false;
			visited[i]=true;
			while(!q.empty()){
				li v=q.front();
				q.pop();
				li tx=v%w;
				li ty=v/w;
				li ti=ty*w+tx;
				
				rep(k,4){
					li nx=tx+dx[k];
					li ny=ty+dy[k];
					li ni=ny*w+nx;
					if(min(nx,ny)>=0  && nx<w && ny<h && dp[i][ni] > dp[i][ti]+table[ni]){
						q.push(ni);
						dp[i][ni]=dp[i][ti]+table[ni];
					}
				}
				
			}
		}
		
		rep(i,n){
			repp(j,i+1,n){
				//p3(i,j,adj(i,j));
				if(adj(i,j))dp2[i][j]=dp2[j][i]=table[i]+table[j];
				else dp2[i][j]=dp2[j][i]=50000;
			}
		}
		
		li res=50000;
		rep(i,n){
			li tres=0;
			rep(j,n){
				if(i!=j)tres=max(tres,dp[i][j]);
			}
			res=min(res,tres);
		}
		return res;
	}
};


雑感
900なので通せるかと思った（時間も1時間くらいあった）のにまずワーシャルフロイドのTLE解を書くに至るまで40分くらいかかったので死ぬしかないって感じでした。
そして枝刈り高速化ではなく入力が０１だけだったりエッジの張られ方が特殊だから特殊な解放があるのかとうんうん悩んでいる間に終了しました。
経験値が足りていないことを痛感しました。