AtCoder Grand Contest 044, B : Joker

問題文

　https://atcoder.jp/contests/agc044/tasks/agc044_b

問題概要

　$N \times N$ のグリッド状の盤面の各セルに人が $1$ 人ずつ，合計 $N^2$ 人いる．人は $1$ から $N^2$ の整数で，左上から row-oriented で番号付けされている．
　入力でサイズ $N^2$ の順列 $P$ が与えられ，この順序に従って人々は一人ずつ盤面の外に出ていく．このとき，他の人がいるセルを通った回数分のコストがかかる．人々がコストを最小化して移動したときのコストを求めよ．

制約

• $2 \leq N \leq 500$
• $1 \leq P_i \leq N^2$

解法

　宗教上の理由で，以下では座標を 0-indexed で扱い，$Y$ 座標を先に書きます．つまり，人 $i$ の座標は $\left( \frac i N, i \bmod N \right)$ です．また，初期状態で座標 $( y, x )$ から外平面へ到達するためには，現在地を含め $\min\{ y + 1, N - i, x + 1, N - x \}$ 個のセルを通る必要があり，これが外平面に到達する際の最適な戦略です．
　TL を気にせず答えを求めるだけであれば，盤面（どこに人がいるかの情報）とコスト情報を保持しつつ器物損壊！高橋君のような BFS の気持ちで，更新があった箇所からの BFS でコスト情報を更新することを繰り返せば達成できることは，（本問題と比べてという意味で）比較的容易に分かります．このアルゴリズムは一見，$O( N^2 )$ 箇所のそれぞれを始点として $O( N^2 )$ の広さの盤面を探索するので $O( N^4 )$ となって TLE するように見えます．しかし実は，解析の仕方を変えることで $O( N^3 )$ というよりよい上界を得られます．
　キューを使って BFS を実装した場合の while ループが回る回数について考えてみます．キューに新たな頂点を追加するタイミングというのは，着目頂点から隣接する頂点を見たときに暫定コストを更新できるときです．今回の問題では移動コストは移動先に人がいるか否かによって $0$ または $1$ の値をとるため各セルでから外平面へのコストは，初期状態でのコスト以下の整数値しかとりません．初期状態でのコストの最大値は盤面の中心付近にありますが，最も近い「辺」へ向かって移動することで $\frac N 2$ 程度を達成できるため，盤面全体での総和は $O( N^3 )$ 程度しかありません．したがって BFS の while ループが回る回数も $O( N^3 )$ と言うことができて，実は間に合うことが分かります．

コード

constexpr int dy[] = { 0, 1, 0, -1 };
constexpr int dx[] = { 1, 0, -1, 0 };

int main()
{
	IN( int, N );
	VI P( N * N );
	cin >> P;
	transform( ALL( P ), begin( P ), bind( minus< int >(), _1, 1 ) );

	static int distances[ 512 ][ 512 ];
	REP( i, N )
	{
		REP( j, N )
		{
			distances[i][j] = min( {
				i + 1, N - i,
				  j + 1, N - j } );
		}
	}

	static int occupied[ 512 ][ 512 ];
	fill( AALL( occupied ), 1 );
	
	LL res = 0;
	FOR( p, P )
	{
		const int pi = p / N;
		const int pj = p % N;

		occupied[ pi ][ pj ] = 0;

		if ( distances[ pi ][ pj ] == 0 )
		{
			continue;
		}

		res += distances[ pi ][ pj ] - 1;
		--distances[ pi ][ pj ];

		queue< PII > que;
		que.EM( pi, pj );

		const auto inside = [&]( const int y, const int x )
		{
			return 0 <= y && y < N && 0 <= x && x < N;
		};

		while ( !que.empty() )
		{
			const int y = que.front().fst;
			const int x = que.front().snd;
			que.pop();

			REP( d, 4 )
			{
				const int ny = y + dy[d];
				const int nx = x + dx[d];

				if ( inside( ny, nx ) && chmin( distances[ ny ][ nx ], distances[y][x] + occupied[ ny ][ nx ] ) )
				{
					que.EM( ny, nx );
				}
			}
		}
	}

	cout << res << endl;

	return 0;
}