BottomCoder SRM 393 div2

TopCoder

SRM 393 div2

points result time
250 AC ?m(数分だが短くはない)
500 AC 6.5m
1000 AC 21m

DP・・もっと速く・・

250

長さjourneyLength(<=100000)の道を、speedLimit(||<=50)に記された速度パターンを繰り返して走るときの時間を求めよ。i番目では、1時間単位につき、speedLimit[i]だけ走る。

問題文を簡潔に書き起こしてもニュアンスが伝わりにくい・・問題文を理解するのに時間がかかった問題。
speedLimit[i]は1以上で、journeyLength<=100000なので、端折らなくてもループするだけで余裕で終わる。

import java.util.Arrays;

public class VariableSpeedLimit {

	public double journeyTime(int journeyLength, int[] speedLimit) {
		double time = 0;
		int n = speedLimit.length;
		while(true){
			for(int i = 0;i < n;i++){
				if(journeyLength >= speedLimit[i]){
					journeyLength -= speedLimit[i];
					time++;
				}else{
					time += (double)journeyLength / speedLimit[i];
					return time;
				}
			}
		}
	}

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

500

N(<=50)人のvotersがM(<=10)人の候補者に対し投票を行う。各votersは0〜M-1の置換の形で投票する候補者の優先順を決めている。投票の結果、過半数(半数は含まない)を獲得した候補者がいればその候補者の番号を返せ。そのような候補者が居ない場合は、最低得票数の候補者を全員ポアしたのち、再投票を行う。これを繰り返した結果、誰も当選せず全員ポアされた場合は-1を返せ。

実装ゲー。制約が小さいのでそのまま実装すればよい。候補者が10人しかいないのでbitでやってみました。
余談だけど、Java,AS3での演算子の優先順位ではどちらも
<<,>> > ==,!= > &
になっていたので、xのnビット目を調べるコードは括弧一つ減らして(x&1<

import java.util.Arrays;

public class InstantRunoffVoting {

	public int winner(String[] voters) {
		int n = voters.length;
		int m = voters[0].length();
		int b = (1<<m)-1;
		
		while(b != 0){
			int[] ct = new int[m];
			for(int i = 0;i < n;i++){
				for(int j = 0;j < m;j++){
					int c = voters[i].charAt(j) - '0';
					if((b&(1<<c))!=0){
						ct[c]++;
						break;
					}
				}
			}
			
			int mins = 0;
			int min = 99999;
			for(int i = 0;i < m;i++){
				if((b&(1<<i))!=0){
					if(ct[i] > n / 2){
						return i;
					}
					if(min > ct[i]){
						min = ct[i];
						mins = 1<<i;
					}else if(min == ct[i]){
						mins |= 1<<i;
					}
				}
			}
			b &= ~mins;
		}
		
		return -1;
	}

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

1000

N(<=50*2+16+1)頂点M(<=50)辺の有向グラフが与えられる。ある頂点vと頂点集合S(||<=16)が与えられ、vからSのすべての要素へのパスが存在するように辺を追加する。追加する辺の最小本数を求めよ。

文章題の皮を剥ぐとだいたいこんな感じ。問題文長い上に文字列処理めんどい。頂点集合の要素数が20より小さいのでbitです。

まず頂点同士がたどれるかどうかを調べるために、Warshall-Floydを有向グラフにかける。これに自分自身への対応を加えた後、各頂点からSの各要素に辿りつけるかどうかをbitで表す。これをstateと呼ぶことにする。
vからある頂点aへ辺を結ぶと、vから行けるstateはstate(v)|state(a)となる。vを介さない辺を新たに結んでも、全体の本数的には、vからその辺の両端にそれぞれ結ぶのと変わらないので、追加する辺はすべてvから出るとしてよく、辺のもう一方の端となる頂点の個数をできるだけすくなくして、state=(1<<|S|)-1となればよい。
vを0番目の頂点として、
dp[i][j]=(i番目の頂点まで見たときに、vのstateがjとなっているものの辺の最小本数)としてDPすればよい。漸化式は
dp[i+1][j|state[i+1] ]=min(dp[i+1][j|state[i+1] ],dp[i][j])と
dp[i+1][j]=min(dp[i+1][j],dp[i][j]).
後者の式があるので、dpの1項目を省いて使い回せば行ける？*1
初期化はdp[0][state[0] ]=0, dp[0][*]=INFTY
dp[N][(1<<|S|)-1]が答え。これはINFTYにはならない。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class PowerAdapters {

	public int needed(String[] adapters, String[] itinerary, String homeCountry) {
		Map<String, Integer> map = new HashMap<String, Integer>();
		int p = 0;
		if(!map.containsKey(homeCountry))map.put(homeCountry, p++);
		for(int i = 0;i < adapters.length;i++){
			String[] sp = adapters[i].split(" ");
			if(!map.containsKey(sp[0]))map.put(sp[0], p++);
			if(!map.containsKey(sp[1]))map.put(sp[1], p++);
		}
		for(String it : itinerary){
			if(!map.containsKey(it))map.put(it, p++);
		}
		boolean[][] g = new boolean[p][p];
		for(int i = 0;i < adapters.length;i++){
			String[] sp = adapters[i].split(" ");
			g[map.get(sp[0])][map.get(sp[1])] = true;
		}
		int[] its = new int[itinerary.length];
		for(int i = 0;i < itinerary.length;i++){
			its[i] = map.get(itinerary[i]);
		}
		
		for(int k = 0;k < p;k++){
			for(int i = 0;i < p;i++){
				for(int j = 0;j < p;j++){
					g[i][j] |= g[i][k] && g[k][j];
				}
			}
		}
		for(int i = 0;i < p;i++){
			g[i][i] = true;
		}
		
		bt = new int[p];
		for(int i = 0;i < p;i++){
			for(int j = 0;j < its.length;j++){
				if(g[i][its[j]])bt[i] |= 1<<j;
			}
		}
		
		int m = its.length;
		int[][] dp = new int[p][1<<m];
		for(int i = 0;i < p;i++){
			Arrays.fill(dp[i], 99999);
		}
		dp[0][bt[0]] = 0;
		
		for(int i = 0;i < p - 1;i++){
			for(int j = 0;j < 1<<m;j++){
				dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]);
				dp[i+1][j|bt[i+1]] = Math.min(dp[i+1][j|bt[i+1]], dp[i][j]+1);
			}
		}
		
		return dp[p-1][(1<<m)-1];
	}
	
	
	
	int[] bt;

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

*1:jを降順に走査してdp[j|state[i+1] ]=min(dp[j|state[i+1],dp[j])かな？