BottomCoder SRM 371 div2

SRM 371 div2

points	result	time
250	AC	6.5m
500	AC	5m
1000	AC	21m

SRMの有向グラフの問題はどうして方針を間違えまくるのだろう。

250

n(<=50)人の投票者がm人の候補者について嗜好順序？を持っている。ある候補者Aが候補者Bより好ましい(preferred)とは、BよりもAを嗜好する人の数が、AよりもBを嗜好する人の数より多いことと定義するとき、他の誰と比べても好ましい候補者1人を求めよ。そのような候補者が存在しない場合は-1を出力せよ。

問題文をよく読む問題。嗜好順序がabc順になってもいないし重複もするかもしれない。問題文さえ読めれば、全探索で問題文のとおり比較していけば良い。

import java.util.Arrays;

public class CondorcetVoting {
	public int winner(String[] votes) {
		int n = votes.length;
		int m = votes[0].length();
		boolean[][] win = new boolean[m][m];
		for(int i = 0;i < m;i++){
			for(int j = 0;j < m;j++){
				if(i != j){
					int w = 0;
					int l = 0;
					for(int k = 0;k < n;k++){
						if(votes[k].charAt(i) < votes[k].charAt(j)){
							w++;
						}
						if(votes[k].charAt(i) > votes[k].charAt(j)){
							l++;
						}
					}
					if(w > l){
						win[i][j] = true;
					}
				}
			}
		}
		
		outer:
		for(int i = 0;i < m;i++){
			for(int j = 0;j < m;j++){
				if(i != j && !win[i][j]){
					continue outer;
				}
			}
			return i;
		}
		return -1;
	}

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

500

width*height(<=5000*5000)の格子があり、左下隅のマスを(0,0)とする。左下のマスから反時計回りに渦を巻いて全てのマスを通ることを考えるとき、最後に着くマスの座標を求めよ。

1マスずつ進めても間に合うらしいが25Mは心臓に悪い。O(width*height).
最終座標を(X,Y)とおく。1周して、左下隅のマスの右上のマスに来る時を考えると、残った格子はちょうど(width-2)*(height-2)になっていて、右上のマスを(0,0)とすると最終座標は(X-1,Y-1)になっている。つまり、width>2かつheight>2のときはこのやり方でwidth,heightを2ずつ削っていける。
残る可能性はwidth,heightのどちらかが1or2の場合。width=1のときは(0,height-1)が最終座標、height=1のときは(width-1,0)が最終座標。それ以外でwidth=2またはheight=2のときは(0,1)が最終座標になる。O(min(width,height)).

import java.util.Arrays;

public class SpiralRoute {
	public int[] thronePosition(int width, int length) {
		return rec(width, length);
	}
	
	int[] rec(int w, int h)
	{
		if(w > 2 && h > 2){
			int[] ret = rec(w-2, h-2);
			ret[0]++; ret[1]++;
			return ret;
		}else if(h == 1){
			return new int[]{w-1, 0};
		}else if(w == 1){
			return new int[]{0, h-1};
		}else{
			return new int[]{0, 1};
		}
	}

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

1000

マップheights(<=50*50)が与えられる。それぞれのマスには高さが与えられる。今雨が全マスに降り、マップ内四方のより低いまたは高さが同じマスに流れるとする。マップ内のいくつかの点にポンプをおいてすべての雨水を処理したいとき、ポンプの最小個数を答えよ。

流れる方向と逆方向に辺を張った頂点数<=50*50, 辺数<=50*50*4の有向グラフの、どのマスもあるポンプからたどれるような・・というのを探せばいいのかな。

はじめよくやり方がわからなかったので、同じ高さのを除けばいいよねと思って強連結成分分解をしてできたクラスタ間のDAGのノードのうち、入力辺がないものの個数を求めたんだけど、これだと答えは出るけど結構手間だし、現在持っている強連結成分分解のライブラリは隣接リストバージョンのはないので、O(N^4)になっていてかなりやばかった。
終わった後、Matsuのやり方を見て考え直した。マークの付いていないマスのうち高さが最も低いマスを見つけて、そこから行けるマスすべてを訪ねてマークをつける。というのを繰り返すだけで良い。DAGにしたところで訪れていない最低点が入力辺を持たない点になっているのは明らかだから・・か。

綺麗な方のコード

import java.util.Arrays;
import java.util.BitSet;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

public class FloodRelief {
	public int minimumPumps(final String[] heights) {
		int n = heights.length;
		final int m = heights[0].length();
		
		Integer[] ord = new Integer[n*m];
		for(int i = 0;i < n*m;i++){
			ord[i] = i;
		}
		Arrays.sort(ord, new Comparator<Integer>(){
			public int compare(Integer x, Integer y)
			{
				return heights[x/m].charAt(x%m) - heights[y/m].charAt(y%m);
			}
		});
		
		BitSet marked = new BitSet();
		int[] dr = {1,0,-1,0};
		int[] dc = {0,1,0,-1};
		int ct = 0;
		for(int i = 0;i < n*m;i++){
			if(!marked.get(ord[i])){
				ct++;
				Queue<Integer> q = new LinkedList<Integer>();
				q.add(ord[i]);
				while(!q.isEmpty()){
					int cur = q.poll();
					int r = cur / m;
					int c = cur % m;
					for(int j = 0;j < 4;j++){
						int nr = r+dr[j];
						int nc = c+dc[j];
						if(nr >= 0 && nr < n && nc >= 0 && nc < m && !marked.get(nr*m+nc) && heights[nr].charAt(nc) >= heights[r].charAt(c)){
							marked.set(nr*m+nc);
							q.add(nr*m+nc);
						}
					}
				}
			}
		}
		return ct;
	}
	
	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

汚れた方のコード

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

public class CopyOfFloodRelief {
	public int minimumPumps(String[] heights) {
		int n = heights.length;
		int m = heights[0].length();
		
		boolean[][] g = new boolean[n*m][n*m];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				if(i+1 < n && heights[i].charAt(j) <= heights[i+1].charAt(j)){
					g[i*m+j][(i+1)*m+j] = true;
				}
				if(i-1 >= 0 && heights[i].charAt(j) <= heights[i-1].charAt(j)){
					g[i*m+j][(i-1)*m+j] = true;
				}
				if(j+1 < m && heights[i].charAt(j) <= heights[i].charAt(j+1)){
					g[i*m+j][i*m+j+1] = true;
				}
				if(j-1 >= 0 && heights[i].charAt(j) <= heights[i].charAt(j-1)){
					g[i*m+j][i*m+j-1] = true;
				}
			}
		}
		
		int[] ret = cutSCC(g);
		int max = 0;
		for(int i = 0;i < n*m;i++){
			max = Math.max(max, ret[i]);
		}
		max++;
		
		boolean[][] dag = new boolean[max][max];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;j++){
				if(i+1 < n && heights[i].charAt(j) <= heights[i+1].charAt(j)){
					dag[ret[i*m+j]][ret[(i+1)*m+j]] = true;
				}
				if(i-1 >= 0 && heights[i].charAt(j) <= heights[i-1].charAt(j)){
					dag[ret[i*m+j]][ret[(i-1)*m+j]] = true;
				}
				if(j+1 < m && heights[i].charAt(j) <= heights[i].charAt(j+1)){
					dag[ret[i*m+j]][ret[i*m+j+1]] = true;
				}
				if(j-1 >= 0 && heights[i].charAt(j) <= heights[i].charAt(j-1)){
					dag[ret[i*m+j]][ret[i*m+j-1]] = true;
				}
			}
		}
		
		int ct = 0;
		outer:
		for(int i = 0;i < max;i++){
			for(int j = 0;j < i;j++){
				if(dag[j][i]){
					continue outer;
				}
			}
			ct++;
		}
		
		return ct;
	}

	public int[] cutSCC(boolean[][] g)
	{
		int n = g.length;
		BitSet visited = new BitSet();
		int[] po = new int[n];
		int pop = 0;
		
		for(int i = visited.nextClearBit(0);i < n;i = visited.nextClearBit(i+1)){
			pop = dfsPostOrder(i, g, visited, po, pop);
		}
		
		int[] ret = new int[n];
		visited.clear();
		int clus = 0;
		for(int i = n - 1;i >= 0;i--){
			if(!visited.get(po[i])){
				BitSet q = new BitSet();
				q.set(po[i]);
				while(!q.isEmpty()){
					visited.or(q);
					BitSet nq = new BitSet();
					for(int j = q.nextSetBit(0);j != -1;j = q.nextSetBit(j+1)){
						ret[j] = clus;
						for(int k = visited.nextClearBit(0);k < n;k = visited.nextClearBit(k+1)){
							if(g[k][j]){
								nq.set(k);
							}
						}
					}
					q = nq;
				}
				clus++;
			}
		}
		
		return ret;
	}
	
	public int dfsPostOrder(int cur, boolean[][] g, BitSet visited, int[] po, int pop)
	{
		visited.set(cur);
		int n = g.length;
		for(int i = visited.nextClearBit(0);i < n;i = visited.nextClearBit(i+1)){
			if(g[cur][i]){
				pop = dfsPostOrder(i, g, visited, po, pop);
			}
		}
		po[pop++] = cur;
		return pop;
	}
	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}