BottomCoder SRM 400 div2

TopCoder

SRM 400 div2

Uターンのため参加しませんでした。

point result time
250 AC 3m
500 WA1 4m
1000 AC 27m

500一回解いたことあるのにこれだよ。

250

(0,0)から出発してゴール(gX,gY)へ、y軸またはx軸に平行に移動して行きたい。ゴールへは直接歩いてもいけるが、n(<=50)個のタクシー乗り場があり、そこへ歩いて行って、タクシーでゴールに向かうこともできる。座標1だけ歩いて進むのにwalkTime,タクシーで進むのにtaxiTimeだけかかるとき、最短時間を求めよ。

n+1通りしかないので全シミュレーション。Math.absを多用するのでimport static 〜Mathしたほうがいいのかな。

public class GrabbingTaxi {

	public int minTime(int[] tXs, int[] tYs, int gX, int gY, int walkTime, int taxiTime) {
		int n = tXs.length;
		int min = (Math.abs(gX) + Math.abs(gY)) * walkTime;
		for(int i = 0;i < n;i++){
			min = Math.min(min, (Math.abs(tXs[i]) + Math.abs(tYs[i])) * walkTime + (Math.abs(tXs[i] - gX) + Math.abs(tYs[i] - gY)) * taxiTime);
		}
		return min;
	}

}

500

自然数N(2<=N<=10^18)が与えられる。N=p^q(p:prime, q>=2)と書けるとき、NはStrong Prime Powerという。NがStrong Prime Powerのとき、{p,q}を求めよ。そうでない場合、空配列を返せ。

ひどい問題。
powの誤差は高々10^9^(10^9*2^-53)=2E-6程度。実際には2つの10^9が両立することはないのでずっと低い。これをバイアスとしてpow(N,1/q)の結果に足したものを少数切り捨てしてpの候補とする。
次にp^q=Nかどうかの確認だが、ここでpowを使うと、double(53bit), long(64bit)の精度の差で情報落ちしてしまうので、自力でp^qを計算しなければならない。
(p,q)の組は1通りしかない((p,q),(p',q')があったとしてp^qの素因数の構成とp'^q'の素因数の構成は明らかに違う)ので成立した最初のものを出力して終わり。

public class StrongPrimePower {

	public int[] baseAndExponent(String n_) {
		long n = Long.parseLong(n_);
		for(int q = 2;q <= 60;q++){
			int p = (int)(Math.pow(n, 1.0 / q)+1E-6);
			long b = 1;
			long mul = p;
			for(int u = q;u > 0;u >>= 1, mul *= mul){
				if(u%2 == 1)b *= mul;
			}
			if(b == n && isPrime(p)){
				return new int[]{p, q};
			}
		}
		return new int[0];
	}
	
	boolean isPrime(int n)
	{
		for(int p = 2;p * p <= n;p++){
			if(n % p == 0)return false;
		}
		return true;
	}

}

1000

自身と周囲8セルに影響を及ぼすようなn*m(<=8*8)のライツアウトがある。これを初期状態からすべて点灯している状態にするための最小手数を求めよ。

2^(2*8)*8が現実的な数値なので、2行の押した押さない情報を1状態として行ごとにDPすればよい。
ライツアウトはビット演算で書ける。行iの点灯状態を2進数で表してptn[i]とし、行iの押し倒さない情報を2進数で表してp[i]とするとき、0〜m-1ビットでの範囲で
ptn[i]^(p[i]^(p[i]<<1)^(p[i]>>1))^(p[i-1]^(p[i-1]<<1)^(p[i-1]>>1))^(p[i+1]^(p[i+1]<<1)^(p[i+1]>>1))=(1<>1))&((1<

import java.util.Arrays;

public class LightedPanels {

	public int minTouch(String[] board) {
		int n = board.length;
		int m = board[0].length();
		int[] ptn = new int[n];
		for(int i = 0;i < n;i++){
			int b = 0;
			for(int j = 0;j < m;j++){
				if(board[i].charAt(j) == '*')b |= 1<<j;
			}
			ptn[i] = b;
		}
		
		int[][] dp = new int[n+1][1<<(2*m)];
		Arrays.fill(dp[0], 99999);
		for(int i = 0;i < 1<<m;i++){
			dp[0][i] = Integer.bitCount(i);
		}
		
		int mask = (1<<m) - 1;
		int[] ct = new int[1<<m];
		for(int i = 0;i < 1<<m;i++){
			ct[(i ^ (i>>1) ^ (i<<1)) & mask]++;
		}
		int[][] orig = new int[1<<m][];
		for(int i = 0;i < 1<<m;i++)orig[i] = new int[ct[i]];
		for(int i = 0;i < 1<<m;i++){
			int v = (i ^ (i>>1) ^ (i<<1) ^ mask) & mask;
			orig[v][--ct[v]] = i;
		}
		
		for(int i = 1;i < n;i++){
			for(int j = 0;j < 1<<(2*m);j++){
				int up = j >> m;
				int low = j & mask;
				int rest = (ptn[i-1] ^ low ^ (low>>1) ^ (low<<1) ^ up ^ (up>>1) ^ (up<<1)) & mask;
				int min = 9999;
				for(int r : orig[rest]){
					min = Math.min(min, dp[i-1][(r<<m)|up]);
				}
				dp[i][j] = min + Integer.bitCount(low);
			}
		}
		for(int j = 0;j < 1<<(2*m);j++){
			int up = j >> m;
			int low = 0;
			int rest = (ptn[n-1] ^ low ^ (low>>1) ^ (low<<1) ^ up ^ (up>>1) ^ (up<<1)) & mask;
			int min = 9999;
			for(int r : orig[rest]){
				min = Math.min(min, dp[n-1][(r<<m)|up]);
			}
			dp[n][j] = min;
		}
		
		int gmin = 9999;
		for(int i = 0;i < 1<<(2*m);i++){
			gmin = Math.min(gmin, dp[n][i]);
		}
		
		return gmin == 9999 ? -1 : gmin;
	}

}