Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-02SRM390 (Practice)

2完ならず。 234/588位

問題結果ポイントその他
250ConcatenateNumberAccepted220.52数論ゲー
500PaintingBoardsOpened0.00DP
1000BuildCircuitUnopened0.00見てない

SRM 390 ConcatenateNumber

|  SRM 390 ConcatenateNumber - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 390 ConcatenateNumber - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8589

  • わぁい数論ゲー あかり数論ゲー大好き
  • 方針を検討
    • 同じ数を繋げるということは、10^桁数 * (元の数) を足すということだ
      • 愚直にシミュレーションし、0にならず同じ状態にたどり着いたら -1
      • 0になったらその数を返せばいい
    • kは最大でも100,000だから、シミュレーション回数も高々100,000のはず
      • 自信はないが、なんとなくそんな気がする
  • 実装
    • 特に問題なくサクサク
  • サンプル通った。
  • 追加ケーステスト。
  • 大丈夫だろう。提出

import java.util.HashSet;
import java.util.Set;

public class ConcatenateNumber {

	public int getSmallest(int number, int k) {
		int keta = 0;
		int nn = number;
		while (nn >= 1) {
			keta++;
			nn /= 10;
		}
		
		long current = number % k;
		long base = (long)Math.pow(10, keta);
		long now = (base % k);
		int cnt = 1;
		boolean[] done = new boolean[1000000];
		while (current % k != 0) {
			if (done[(int)(current % k)]) {
				cnt = -1;
				break;
			}
			done[(int)(current % k)] = true;
			current += (now * number) % k; 
			now = (now * base) % k;
			cnt++;
		}
		return cnt;
	}
}

SRM 390 PaintingBoards

|  SRM 390 PaintingBoards - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 390 PaintingBoards - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8516

  • 方針を検討
    • painterの人数が高々15ってところにbitDP臭がする
    • 次のような区間DPを考えた。
      • dp[a][b][ptn] = 板aから板bまでをptnたちが塗るときの最小時間
      • これだと 50 * 50 * (2^15) >= 26Mで、そもそもメモリ確保できない。却下
    • 前から順番に塗っていくことを考える。
      • dp[a][ptn] = 板aまで塗り、残り使える人がptnのときの最小時間
    • ・・・よさそう。
  • 実装
    • 途中。板と使った人のループ内部で、 (次に使う人 = 15) x (どこまで塗るか = 50) のループが発生することに気づく。
    • 嫌な予感。これ間に合わないんじゃないか・・・?
  • 実装終わり。サンプル通った。
    • 定数倍が効いて間に合うことを祈りつつ、最大ケースでテスト
      • やっぱりTLEした・・・ 500だしそんなに単純じゃないか
  • 更新の仕方を変えてみよう。
    • 蟻本の個数制限ナップザックの話みたいに、余計な更新を減らせばいいのでは
    • 板aに関するループの中では、板a+1についてしか考えない。
    • 最後に使った人をメモしておけば・・・
    • dp[a][b][ptn] = (板aまで塗り終わり、最後に使った人はbで、あとptnが使える時の最小時間)
      • 普通にやるとメモリが足りないので、板に関する部分は使いまわす。
  • 実装
    • あ・・・
      • 同じ人が連続で塗る時、幾つ前から塗っているかを知らないと更新ができない
    • これだとさっきの実装と本質的に変わらず、今度はメモリが足りなくなってしまう
  • 時間切れ。
    • いったいどうやるんだ・・・
    • ヒューリスティクス的な枝刈りが出来るとか?(この時間を超えることはない、というのを予め求めておくとか)
      • コーナーケース用意されて落ちそうだな

その後

  • しばらく自力で考える。
    • ひょっとして二分探索かも
    • mid秒で塗れるかという条件の判定ならばDPの部分で「時間の許す限り塗る」というGreedyな手法が使える
      • これなら探索すべき状態数を大幅に減らせる。
  • 実装
    • 最大ケースでテスト。手元で0.4s、本番サーバで1.0s これはいけるんじゃないか!?
    • TLE食らった・・・まだダメなのか
  • 降参して他の人のコードを読む。
    • maxでmid秒作業できる時、各人がどこまで塗れるか、というのを前計算しておくといいらしい
    • 二分探索までたどり着いておいてそこに気づかないとは・・・
  • 一筋縄ではいかない、いい問題。

import java.util.Arrays;

public class PaintingBoards {

	double INF = 100000000.0d;
	
	public double minimalTime(int[] boardLength, int[] painterSpeed) {
		int bl = boardLength.length;
		int pl = painterSpeed.length;
		double[] pn = new double[pl];
		double mspd = Double.MAX_VALUE;
		for (int i = 0 ; i < pl ; i++) {
			pn[i] = 1.0d / painterSpeed[i];
			mspd = Math.min(mspd, pn[i]);
		}
		
		int[] sum = new int[bl+1];
		for (int i = 0 ; i < bl ; i++) {
			sum[i+1] += sum[i] + boardLength[i];
		}
		
		double max = sum[bl] * mspd;
		double min = 0.0d;
		for (int cur = 0 ; cur < 35 ; cur++) {
			double mid = (max + min) / 2;
			
			int[][] canpaint = new int[15][51];
			for (int i = 0 ; i < pl ; i++) {
				for (int j = 0 ; j < bl ; j++) {
					int count = 0;
					for (int p = j+1 ; p <= bl ; p++) {
						double maxl = (sum[p] - sum[j]) * pn[i];
						if (maxl <= mid) {
							count++;
						}
					}
					canpaint[i][j] = count;
				}
			}
			
			boolean[][] dp = new boolean[51][1<<15];
			for (int i = 0 ; i < bl+1 ; i++) {
				Arrays.fill(dp[i], false);
			}
			dp[0][(1<<pl)-1] = true;

			for (int i = 0 ; i < bl ; i++) {
				for (int ptn = (1<<pl)-1 ; ptn >= 0 ; ptn--) {
					if (!dp[i][ptn]) {
						continue;
					}
					for (int p = 0 ; p < pl ; p++) {
						if (((1<<p) & ptn) == 0) {
							continue;
						}
						int nptn = ptn - (1<<p);
						dp[i+canpaint[p][i]][nptn] = true;
					}
				}
			}
			
			boolean isok = false;
			for (int p = 0 ; p < (1<<pl) ; p++) {
				if (dp[bl][p]) {
					isok = true;
				}
			}
			if (isok) {
				max = mid;
			} else {
				min = mid;
			}
		}
		return max;
	}

}

import java.util.Arrays;

/*
  はじめにサンプル通したコード。TLEする
*/
public class PaintingBoards {

	double INF = 100000000.0d;
	
	public double minimalTime(int[] boardLength, int[] painterSpeed) {
		int bl = boardLength.length;
		int pl = painterSpeed.length;
		double[] pn = new double[pl];
		for (int i = 0 ; i < pl ; i++) {
			pn[i] = 1.0d / painterSpeed[i];
		}
		
		int[] sum = new int[bl+1];
		for (int i = 0 ; i < bl ; i++) {
			sum[i+1] += sum[i] + boardLength[i];
		}
		
		
		double[][] dp = new double[51][1<<15];
		for (int i = 0 ; i < bl+1 ; i++) {
			Arrays.fill(dp[i], INF);
		}
		dp[0][(1<<pl)-1] = 0.0d;
		
		for (int i = 0 ; i < bl ; i++) {
			for (int ptn = (1<<pl)-1 ; ptn >= 0 ; ptn--) {
				if (dp[i][ptn] >= INF/2) {
					continue;
				}
				
				double now = dp[i][ptn];
				for (int p = 0 ; p < pl ; p++) {
					if (((1<<p) & ptn) == 0) {
						continue;
					}
					int nptn = ptn - (1<<p);
					for (int t = i+1 ; t <= bl ; t++) {
						int length = sum[t] - sum[i];
						double elp = pn[p] * length;
						dp[t][nptn] = Math.min(Math.max(now, elp), dp[t][nptn]);
					}						
				}
			}
		}
		
		
		double mintime = INF;
		
		for (int p = 0 ; p < (1<<pl) ; p++) {
			mintime = Math.min(mintime, dp[bl][p]);
		}
		return mintime;
	}
}