1759-Garland

問題（外部リンク）

1759 -- Garland

実装の概要

計算式のみで正確な値を求めるのは困難なので、二分探索を用いて値を絞り込みます。正しい解の条件は「いかなる点においても座標が0以上であること」です。
両端の座標を初期値として漸化式を解くと、i番目の座標はと表すことができます。これが全ての点で0以上となるかについてはある解につきで検証でき、全体としても十分間に合います。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] tmpArray = br.readLine().split(" ");
		
		int n = Integer.parseInt(tmpArray[0]);
		double a = Double.parseDouble(tmpArray[1]);
		
		System.out.printf("%.2f", solve(n, a));
	}
	
	static boolean check(int n, double a, double b){
		for(int i = 2; i < n; i++){
			double tmp = ((n - i)*a +(i - 1)*b + (n - 1)*i*i - i*n*n + i - n + n*n)/(n - 1);
			if(tmp < 0){
				return false;
			}
		}
		
		return true;
	}
	
	static double solve(int n, double a){
		double lb = 0;
		double ub = 10000000;
		
		for(int i = 0; i < 100 ; i++){
			double mid = (lb+ub)/2;
			
			if(check(n, a, mid)){
				ub = mid;
			}
			else {
				lb = mid;
			}
		}
		
		return Math.round(ub*100)/100.0;
	}
}

1703-Fine them, Catch them

問題（外部リンク）

1703 -- Find them, Catch them

実装の概要

グループ分けの問題で、Union-Find木が非常に有効です。ですが、所属している組織でグループ分けをしようとするとうまく行きません。
そこで今回はA, Bという事実がそれぞれ共存するなら同じグループと考えます。
例えば、問題の実行例にあるように「D 1 2」と入力されたとします。このとき、「1がドラゴンに所属」と「2がスネークに所属」という2つの事実は共存できるので同じグループです。同時に、「1がスネークに所属」と「2がドラゴンに所属」という2つの事実もこれはこれで共存できるので同じグループです。そのため両方の可能性を考えそれぞれ別個にunionします。
情報が揃うまではunionが必要なだけ行われていないのでNot sure yet.と出力され、十分に情報が揃えば同じグループか異なるグループかを決定できます。
なお、N人についてそれぞれスネークまたはドラゴンに所属という2つの可能性を考えるため、Union-Find木の要素数は2*Nとなることに注意してください。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		String[] tmpArray ;
		for(int i = 0; i < t; i++){
			System.gc();

			tmpArray = br.readLine().split(" ");
			int n = Integer.parseInt(tmpArray[0]);
			int m = Integer.parseInt(tmpArray[1]);

			solve(n, m, br);

		}
	}

	static void solve(int n, int m, BufferedReader br) throws IOException{

		//前半をドラゴン、後半をスネークに割り振る
		DisjointSet set = new DisjointSet(2*n);

		String[] tmpArray;
		for(int i = 0; i < m; i++){
			tmpArray = br.readLine().split(" ");

			int gang1 = Integer.parseInt(tmpArray[1]);
			int gang2 = Integer.parseInt(tmpArray[2]);

			if(tmpArray[0].equals("A")){
				if(set.isSameSet(gang1, gang2)){
					System.out.println("In the same gang.");
				}
				else if(set.isSameSet(gang1, gang2+n) ){
					System.out.println("In different gangs.");
				}
				else {
					System.out.println("Not sure yet.");
				}
			}
			else {
				set.union(gang1, gang2+n);
				set.union(gang1 + n, gang2);
			}
		}

		System.gc();
	}

}

class DisjointSet {
    private int n;
    private int[] p;
    private int[] rank;

    public DisjointSet(int n){
        this.n = n;

        p = new int[n + 1];
        rank = new int[n + 1];

        for(int i = 1; i <= n; i++){
            makeSet(i);
        }
    }

    private void makeSet(int x){
        p[x] = x;
        rank[x] = 0;
    }

    public void union(int x, int y){
        link (findSet(x), findSet(y));
    }

    private int findSet(int x){
        if(x != p[x]){
            p[x] = findSet( p[x]);
        }
        return p[x];
    }

    public boolean isSameSet(int x, int y){
        return findSet(x) == findSet(y);
    }

    private void link(int x, int y){
        if(rank[x] > rank[y]){
            p[y] = x;
        }
        else {
            p[x] = y;
            if(rank[x] == rank[y]){
                rank[y]++;
            }
        }
    }
}

1631-Bridging signals

問題（外部リンク）

1631 -- Bridging signals

実装の概要

信号が交差しないための条件は行き先の数字が単調増加することです。問題の1つ目の入力例では行き先が{4,2,6,3,1,5}となっており、できるだけ要素数が大きくなるように増加数列を作ると{2,3,5}となります。
このような増加部分列は動的計画法を利用して求めることができます。特に、蟻本にも書いてあるように二分探索と組み合わせることで効率よく計算することが可能です。

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		for(int i = 0; i < n; i++){
			int p = Integer.parseInt(br.readLine());

			int dest[] = new int[p];
			for(int j = 0; j < p; j++){
				dest[j] = Integer.parseInt(br.readLine());
			}

			System.out.println(solve(dest));
		}
	}

	static int solve(int dest[]){
		int n = dest.length;
		//dp[i] : 長さがi+1である増加部分列における最終要素の最小値
		int dp[] = new int[n];

		Arrays.fill(dp, Integer.MAX_VALUE);
		for(int i = 0; i < n; i++){
			int index = Arrays.binarySearch(dp, dest[i]);
			if(index < 0){
				index = -index - 1;
			}
			dp[index] = dest[i];
		}

		//INFじゃないものが答え
		int result = -1;
		for(int i = n - 1; i >= 0; i--){
			if(dp[i] != Integer.MAX_VALUE){
				result = i + 1;
				break;
			}
		}
		return  result;
	}

}

1222-EXTENDED LIGHTS OUT

問題（外部リンク）

1222 -- EXTENDED LIGHTS OUT

実装の概要

30マスあるので全てのマスについてボタンを押すかどうかを考えると2^30パターンとなり、それで全部0になったかどうかのチェックも含めると間に合いません。
ですが、一番上の行だけであれば2^6=64パターンなので全パターン試すことができます。
二行目以降は順次「上のマスが1ならそのマスを中心に十字状に反転する」という処理を行えば解くことができます。もし上のマスに1があった場合、後戻りはできないという制約上必ずその1つ下のマスを基準として反転しないと上のマスを最終的に0にできないからです。
64パターンの中で、最終的に全てのマスが0になっていることが確認できればそれが答えです。

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int matrix[][] = new int[5][6];
		
		for(int k = 0; k < n; k++){
			for(int i = 0; i < 5; i++){
				for(int j = 0; j < 6; j++){
					matrix[i][j] = sc.nextInt();
				}
			}
			
			solve(matrix, k + 1);
		}

	}

	static void solve(int[][] mat, int id){
		int matrix[][] = new int[5][6];
		int record[][];
		//極端な話、1行目の返し方を32パターン全て試せば解ける
		for(int i = 0; i <= 63 ; i++){
			//配列をコピーする
			copyMatrix(mat, matrix);
			record = new int[5][6];
			
			//1行目の返し方を決め打ちしてやる
			flipFirstLine(matrix, i, record);
			
			for(int j = 1; j < 5; j++){
				for(int k = 0; k < 6; k++){
					if(matrix[j - 1][k] == 1){
						flipCross(matrix, j, k, record);
					}
				}
			}
			
			if(allTurnedOff(matrix)){
				System.out.println("PUZZLE #"+id);
				showMatrix(record);
				return;
			}
		}
		
		System.out.println("ERROR");
	}
	
	static void copyMatrix(int[][] from, int[][] to){
		for(int j = 0; j < 5 ; j++){
			for(int k = 0; k < 6; k++){
				to[j][k] = from[j][k];
			}
		}
	}
	
	static void showMatrix(int[][] matrix){
		for(int j = 0; j < 5 ; j++){
			for(int k = 0; k < 6; k++){
				System.out.print(matrix[j][k]);
				if(k != 5){
					System.out.print(" ");
				}
			}
			System.out.println();
		}
	}
	
	static boolean allTurnedOff(int[][] mat){
		for(int i = 0; i < mat.length; i++){
			for(int j = 0; j < mat[0].length ; j++){
				if(mat[i][j] == 1){
					return false;
				}
			}
		}
		
		return true;
	}
	static void flipFirstLine(int[][] mat, int seed, int record[][]){
		int[] pow = {1,2,4,8,16,32};
		
		for(int i = 0; i < 6; i++){
			if((seed&pow[i]) != 0){
				flipCross(mat, 0, i, record);
			}
		}
		
	}
	
	static void flipCross(int[][] matrix, int y, int x, int[][] record){
		int h = matrix.length; int w = matrix[0].length;
		
		record[y][x] = 1;
		flip(matrix, y, x);
		if(y != 0){
			flip(matrix, y - 1, x);
		}
		if(y != h - 1){
			flip(matrix, y + 1, x);
		}
		if(x != 0){
			flip(matrix, y, x - 1);
		}
		if(x != w - 1){
			flip(matrix, y, x + 1);
		}
	}
	
	static void flip(int[][] matrix, int y, int x){
		matrix[y][x] = (matrix[y][x] + 1)%2;
	}
}

1017-Packets

問題（外部リンク）

1017 -- Packets

実装の概要

使用できる箱の大きさが6*6と決まっているので、まずはサイズが6*6である荷物の数だけ小包が増えます。
同様に5*5の場合も荷物と同じ数だけ小包が増えますが、こちらは隙間の各11マスも活用することができます。ただしここに入れることができるのはサイズが1*1のもののみです。
以降もこのようになるべく大きい荷物を入れて余ったスペースに小さい荷物を入れますが、終わりに近づくほど分岐が複雑になるので注意です。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true){
			String input = br.readLine();
			if(input.equals("0 0 0 0 0 0")){
				break;
			}

			String[] tmpArray = input.split(" ");

			int num[] = new int[6];

			for(int i = 0; i < 6; i++){
				num[i] = Integer.parseInt(tmpArray[i]);
			}

			System.out.println(solve(num));
		}
	}

	static int solve(int num[]){
		int packets = 0;

		//6*6
		packets += num[5];

		//5*5
		packets += num[4];
		if(num[0] > num[4] * 11){
			num[0] -= num[4] * 11;
		}
		else {
			num[0] = 0;
		}

		//4*4
		packets += num[3];
		int cap2 = num[3] * 5;
		int cap1 = num[3] * 20;

		int pack2 = Math.min(num[1], cap2);
		num[1] -= pack2;
		cap1 -= pack2*4;

		int pack1 = Math.min(num[0], cap1);
		num[0] -= pack1;

		//3*3
		packets += num[2] / 4;
		if(num[2] % 4 == 1){
			cap2 = 5;
			cap1 = 27;
		}
		else if(num[2] % 4 == 2){
			cap2 = 3;
			cap1 = 18;
		}
		else if(num[2] % 4 == 3){
			cap2 = 1;
			cap1 = 9;
		}

		if(num[2] % 4 > 0){
			packets++;
			pack2 = Math.min(num[1], cap2);
			num[1] -= pack2;
			cap1 -= pack2*4;

			pack1 = Math.min(num[0], cap1);
			num[0] -= pack1;
		}

		//2*2 || 1*1
		packets += Math.ceil((num[1]*4 + num[0])/36.0);


		return packets;
	}

}

3104-Drying

問題（外部リンク）

3104 -- Drying

実装の概要

最大値を最小化する問題です。二分探索を利用して解を絞り込みます。
「x分で全ての洗濯物を乾燥させられるか」についてですが、直感的には最も時間がかかる洗濯物を毎分ごとに選んで乾燥機を使えばできそうですが毎回ソートをしていたら間に合いません。
重要なこととして、どの洗濯物もx分経てばその分だけは自然乾燥できます。それでも乾かなかった洗濯物についてはそれぞれ回乾燥機を使う必要があります。この判定はでできます。kではなく(k - 1)としているのは、乾燥機使用中は自然乾燥は無視されるためです。
なお、テストケースに存在するかは不明ですが仕様上はk=1もあり得るのでそれは別の処理にします（自然乾燥しかしないのと同じ考え方です）。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int time[] = new int[n];

		String tmpArray[] = br.readLine().split(" ");
		for(int i = 0; i < n; i++){
			time[i] = Integer.parseInt(tmpArray[i]);
		}

		int k = Integer.parseInt(br.readLine());

		System.out.println(solve(time, k));
	}

	static int solve(int time[], int k){
		int n = time.length;

		Arrays.sort(time);

		int left = 0;
		int right = 1000000001;

		//解を仮定して二分探索
		while(right - left > 1){
			int mid = (left + right)/2;

			if(check(time, k, mid)){
				right = mid;
			}
			else {
				left = mid;
			}
		}

		return right;
	}

	//limit以内の時間で全て乾かせるか
	static boolean check(int time[], int k, int limit){
		int n = time.length;

		//k == 1のときはつまり自然乾燥と同じ
		if(k == 1){
			for(int i = n - 1; i >= 0 ; i--){
				if(time[i] > limit){
					return false;
				}
			}
			return true;
		}
		int tmpSum = 0;
		for(int i = n - 1; i >= 0; i--){
			//乾燥機を使わなくても乾く場合
			if(time[i] <= limit){
				break;
			}

			//乾燥機を使う必要がある時間を加算
			tmpSum += Math.ceil((double)(time[i] - limit)/(k - 1));

			if(tmpSum > limit){
				return false;
			}
		}

		return true;
	}

}

3273-Monthly Expense

問題（外部リンク）

3273 -- Monthly Expense

実装の概要

1期間あたりの予算の下限を求める問題です。解を仮定して二分探索で絞り込む方法で解きます。蟻本では「最小値の最大化」として紹介されていますが、実際には「最大値の最小化」なので絞り込みの部分などは適宜書き換える必要があります。
判定法についてですが、「1期間あたりの予算をlimitとした上で、期間をm以下にできるか」とします。mとちょうど等しくなる必要はありません。期間が余ったなら適当なところを分割しても構わないからです。
これについてはループを回して「合計金額がオーバーしたら期間が切り替わる」と考えれば1回あたりで判定できます。なお、1日だけでオーバーする場合は論外なのでその時点でfalseを返します（そうならないようにleftをmoneyの最大値-1などにするのもありかもしれません）

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String tmpArray[] = br.readLine().split(" ");

		int n = Integer.parseInt(tmpArray[0]);
		int m = Integer.parseInt(tmpArray[1]);

		int money[] = new int[n];

		for(int i = 0; i < n; i++){
			money[i] = Integer.parseInt(br.readLine());
		}

		System.out.println(solve(money, m));
	}

	static int solve(int money[], int m){
		int n = money.length;

		int left = 0;
		int right = 10000*100000 + 1;

		//解を仮定して二分探索
		while(right - left > 1){
			int mid = (left + right)/2;

			if(check(money, m, mid)){
				right = mid;
			}
			else {
				left = mid;
			}
		}

		return right;
	}

	//毎月limit以内の出費に収めることができるか
	static boolean check(int money[], int m, int limit){
		int n = money.length;

		int tmpSum = 0;
		for(int i = 0; i < n; i++){
			//1日だけでオーバーする場合は不可
			if(money[i] > limit){
				return false;
			}
			//i日目を加えても予算に収まる場合
			if(tmpSum + money[i] <= limit){
				tmpSum += money[i];
			}
			//予算オーバー
			else {
				m--;
				if(m <= 0){
					return false;
				}
				tmpSum = money[i];
			}
		}
		return true;
	}
}