BottomCoder SRM 391 div2

SRM 391 div2

points	result	time
250	AC	1.2m
500	AC	5m
1050	- WA∞	3h?

1050は1050だった。

250

一本の道(||<=10000)のいくつかの区間が雪で埋まっている。雪で埋まった区間(重複あり, ||<=50)が与えられたとき、全体の埋められた道路の長さを求めよ。

Div2最速より速く解いた。
10000*50が現実的だとわかれば、JavaではBitSetで書くのが一番楽。C++でもstd::bitsetがいいんだろうか。これをビルトインクラスを使わないで実装するのはちょっと時間がかかる。(ソートして昇順に、か)

import java.util.Arrays;
import java.util.BitSet;

public class SnowyWinter {

	public int snowyHighwayLength(int[] startPoints, int[] endPoints) {
		int n = startPoints.length;
		BitSet bs = new BitSet();
		for(int i = 0;i < n;i++){
			bs.set(startPoints[i], endPoints[i]);
		}
		return bs.cardinality();
	}

	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

500

2つの同じ長さの文字列があるとき、ある全単射の文字対応関数があって一方の文字列に適用すると、他方の文字列になるような関係をisomorphicとする。N(<=50)個の同じ長さの文字列(||<=50)が与えられる。このうちの任意の異なる2つの文字列のペアで、isomorphicなものの個数を求めよ。

A,Bがisomorphicかどうかの判定は、対応を全くつくっていない写像fを用意して、文字列の前から同時に読んでいって、文字c(∈A), d(∈B)のとき、f(c)がすでに登録されていれば、f(c)!=dならout. 登録されていなければ、f(e)=dなるeが存在していたらout, いなければf(c)=dを登録する。こうして終端まで問題なければOK.
isomorphicの判定がO(N)でできたので、全探索でもO(N^3)で間に合う。

import java.util.Arrays;

public class IsomorphicWords {

	public int countPairs(String[] words) {
		int n = words.length;
		int m = words[0].length();
		int ct = 0;
		for(int i = 0;i < n;i++){
			outer:
			for(int j = i + 1;j < n;j++){
				char[] map = new char[128];
				int used = 0;
				for(int k = 0;k < m;k++){
					char a = words[i].charAt(k);
					char b = words[j].charAt(k);
					if(map[a] != 0){
						if(map[a] != b){
							continue outer;
						}
					}else{
						if((used&1<<(b-'a')) != 0){
							continue outer;
						}
						map[a] = b;
						used |= 1<<(b-'a');
					}
				}
				ct++;
			}
		}
		return ct;
	}

	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

1050

N*M(<=20*20)のマップがある。左上隅のマスからロボットが次の規則に従って動く。

ロボットはマップの外には出られない。
ロボットは#のついたマスには行けない。
ロボットは1マスずつ右か下に動ける。
Uとかいてあるマスではロボットは上にも動ける。
Lとかいてあるマスではロボットは左にも動ける。
ロボットは、数字の書いてあるマスを通ると、初めて通るときに限り、その数だけmarbleを集める。

ロボットが集められるmarbleの最大個数を求めよ。

残念ながら時間内に解けなかったばかりか、結構ひどいコードを書いていて、ACするまでも時間がかかった。でも方針はあってたみたい。

U,Lのマスがなければ、BFSで瞬殺である。U,Lがあると、たとえばLの左のセルが空いていたら、そのセルとLとの間で自由に移動できてしまうため、世界の調和が乱れる。じゃなくてマスを有向グラフのノード、ロボットの移動を有向辺とみなした場合、ループができてしまいトポロジカルソートできないのでDP的にmaxを求められない。
というわけでトポロジカルソートできるようにすればよい。さっきの例でいえば、Lと左隣のセルをひとつのノードとみなすことで、ループを解消できる。
LかUを見つけたら、そこから最終的に行けるマスを全列挙する。そして、その各マスから元のLまたはUに行けるかどうか調べる。もし行けるならそのLまたはUとループを組んでいるということになる。こうしてひとつの塊ができる。これをクラスタと呼ぶことにする。クラスタにロボットが足を踏み入れると、クラスタ内のmarbleは全て手に入れることができるので、クラスタ単位でスコアを計算する。
なおクラスタは他のクラスタに侵食されたりもするので、スコア計算はすべてのクラスタを見つけてからにしたほうがよい。
こうして多めに見積もってN*M+cls(clsはクラスタの全個数<=20*21)個のノードからなるトポロジカルソート可能な有向グラフができあがる。あとは、トポロジカルソートをして、DPで各ノードまでの最大個数を計算していき、[0][0]に相当するマスまたはクラスタから到達可能なノードで、最大のものを出力すれば良い。

オーダーは最悪O((NM)^3)で結構やばげだが、SystemTestは特に時間もかからず動いていた。

追記 クラスタを見つけるところは、まさに強連結成分分解でいけそうだね。今日連結成分に分解してしまうと必ずDAGになっちゃうしね。

import java.util.Arrays;
import java.util.BitSet;
import java.util.concurrent.ArrayBlockingQueue;

public class MarbleCollectionGame {

	public int collectMarble(String[] board) {
		int n = board.length;
		int m = board[0].length();
		char[][] b = new char[n][m];
		for(int i = 0;i < n;i++){
			b[i] = board[i].toCharArray();
		}
		int[][] z = new int[n][m];
		int cls = 1;
		for(int i = n - 1;i >= 0;i--){
			for(int j = m - 1;j >= 0;j--){
				if((b[i][j] == 'L' || b[i][j] == 'U') && z[i][j] == 0){
					BitSet bottom = new BitSet();
					{
						ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<Integer>(2000);
						q.add(i*m+j);
						bottom.set(i*m+j);
						while(!q.isEmpty()){
							int cur = q.poll();
							int r = cur/m;
							int c = cur%m;
							bottom.set(cur);
							{
								// down
								int nr = r+1;
								int nc = c;
								if(nr < n && b[nr][nc] != '#' && !bottom.get(nr*m+nc)){
									bottom.set(nr*m+nc);
									q.add(nr*m+nc);
								}
							}
							{
								// right
								int nr = r;
								int nc = c+1;
								if(nc < m && b[nr][nc] != '#' && !bottom.get(nr*m+nc)){
									bottom.set(nr*m+nc);
									q.add(nr*m+nc);
								}
							}
							if(b[r][c] == 'L' && c >= 1){
								// left
								int nr = r;
								int nc = c-1;
								if(b[nr][nc] != '#' && !bottom.get(nr*m+nc)){
									bottom.set(nr*m+nc);
									q.add(nr*m+nc);
								}
							}
							if(b[r][c] == 'U' && r >= 1){
								// up
								int nr = r-1;
								int nc = c;
								if(b[nr][nc] != '#' && !bottom.get(nr*m+nc)){
									bottom.set(nr*m+nc);
									q.add(nr*m+nc);
								}
							}
						}
					}
					
					for(int k = bottom.nextSetBit(0);k != -1;k = bottom.nextSetBit(k+1)){
						BitSet visited = new BitSet();
						{
							ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<Integer>(500);
							q.add(k);
							visited.set(k);
							while(!q.isEmpty()){
								int cur = q.poll();
								int r = cur/m;
								int c = cur%m;
								if(cur == i*m+j)break;
								{
									// down
									int nr = r+1;
									int nc = c;
									if(nr < n && b[nr][nc] != '#' && !visited.get(nr*m+nc)){
										visited.set(nr*m+nc);
										q.add(nr*m+nc);
									}
								}
								{
									// right
									int nr = r;
									int nc = c+1;
									if(nc < m && b[nr][nc] != '#' && !visited.get(nr*m+nc)){
										visited.set(nr*m+nc);
										q.add(nr*m+nc);
									}
								}
								if(b[r][c] == 'L' && c >= 1){
									// left
									int nr = r;
									int nc = c-1;
									if(b[nr][nc] != '#' && !visited.get(nr*m+nc)){
										visited.set(nr*m+nc);
										q.add(nr*m+nc);
									}
								}
								if(b[r][c] == 'U' && r >= 1){
									// up
									int nr = r-1;
									int nc = c;
									if(b[nr][nc] != '#' && !visited.get(nr*m+nc)){
										visited.set(nr*m+nc);
										q.add(nr*m+nc);
									}
								}
							}
							if(!visited.get(i*m+j)){
								bottom.andNot(visited);
							}
						}
					}
					
					for(int k = bottom.nextSetBit(0);k != -1;k = bottom.nextSetBit(k+1)){
						z[k/m][k%m] = cls;
					}
					cls++;
				}
			}
		}
		
		BitSet[] cluster = new BitSet[cls];
		for(int i = 1;i < cls;i++){
			cluster[i] = new BitSet();
		}
		int[] score = new int[cls];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				if(z[i][j] > 0){
					cluster[z[i][j]].set(i*m+j);
				}
				if(b[i][j] >= '0' && b[i][j] <= '9' && z[i][j] > 0){
					score[z[i][j]] += b[i][j] - '0';
				}
			}
		}
		
		boolean[][] g = new boolean[n*m+cls][n*m+cls];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				if(b[i][j] == '#')continue;
				int cur = z[i][j] > 0 ? n*m+z[i][j] : i * m + j;
				if(i+1 < n && b[i+1][j] != '#'){
					int nex = z[i+1][j] > 0 ? n*m+z[i+1][j] : (i+1) * m + j;
					if(cur != nex){
						g[cur][nex] = true;
					}
				}
				if(j+1 < m && b[i][j+1] != '#'){
					int nex = z[i][j+1] > 0 ? n*m+z[i][j+1] : i * m + j+1;
					if(cur != nex){
						g[cur][nex] = true;
					}
				}
			}
		}
		
		int[] sorted = sortTopologically(g);
		int[] dp = new int[n*m+cls];
		
		int o = z[0][0] > 0 ? n*m+z[0][0] : 0;
		int max = 0;
		BitSet oo = new BitSet();
		oo.set(o);
		for(int i = 0;i < n*m+cls;i++){
			if(oo.get(sorted[i])){
				if(sorted[i] > n*m){
					dp[i] += score[sorted[i]-n*m];
				}else if(sorted[i] < n*m){
					dp[i] += b[sorted[i]/m][sorted[i]%m]-'0';
				}
				for(int j = i + 1;j < n*m+cls;j++){
					if(g[sorted[i]][sorted[j]]){
						oo.set(sorted[j]);
						dp[j] = Math.max(dp[j], dp[i]);
					}
				}
				max = Math.max(max, dp[i]);
			}
		}
		
		return max;
	}
	
	public int[] sortTopologically(boolean[][] g)
	{
		int n = g.length;
		int[] ec = new int[n];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
				if(g[i][j])ec[j]++;
			}
		}
		int[] ret = new int[n];
		int p = 0;
		int q = 0;
		
		ost:
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
				if(g[j][i])continue ost;
			}
			ret[q++] = i;
		}
		
		for(;p < q;p++){
			int cur = ret[p];
			for(int i = 0;i < n;i++){
				if(g[cur][i]){
					ec[i]--;
					if(ec[i] == 0)ret[q++] = i;
				}
			}
		}
		for(int i = 0;i < n;i++){
			if(ec[i] > 0){
				return null;
			}
		}
		return ret;
	}
	

	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}