読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Ants (PKU No.1852)

Ants (PKU No. 1852)

長さLcmの竿の上をn匹のありが毎秒1cmのスピードで歩いている。アリが竿の端に到達すると竿の下に落ちていく。また、竿の上は狭くてすれ違えないので、2匹のアリが出会うと、それぞれ反対を向いて戻っていく。各アリについて、現在の竿の左端からの距離x_iは分かるが、どちらの方向を向いているかは分からない。全てのアリが傘から落ちるまでにかかる最小の時間と最大の時間をそれぞれ求める。
制約
1\leq L \leq 10^6
1\leq n \leq 10^6
0\leq x_i \leq L

アルゴリズム

ナイーブに全ての組み合わせ(各アリについて、初期の向き(左or右))を考えると2^n=2^{10^6}となり、現実的ではない。アリの速さが全部同じなのがポイントで、アリを区別しなければ、アリ同士が出会ったとき、素通りしていると考えても良い。なので、まず、各アリについて、両端までの時間(距離)を求める(A_i \leq B_i)。そして、最終的に求める時間は、
MAX = \max_{i}\{B_i\}
MIN = \max_{i}\{A_i\}

コード

import java.util.*;

public class pku1852 {
	static Scanner scanner;
	public static void main(String[] args) {
		scanner = new Scanner(System.in);
		new pku1852();
	}
	pku1852(){
		int c;
		int L,n;
		
		c = scanner.nextInt();
		while( c > 0 ){
			c--;
			L = scanner.nextInt();
			n = scanner.nextInt();
			int[] x = new int[n];
			for(int i = 0; i < n; i++)
				x[i] = scanner.nextInt();
			solve(L, n, x);
		}
	}
	
	void solve(int L, int n, int[] x){
		int MAX,MIN;
		MAX = MIN = 0;
		for(int i = 0; i < n; i++){
			int A = Math.min(x[i], L - x[i]);
			int B = Math.max(x[i], L - x[i]);
			MIN = Math.max(MIN, A);
			MAX = Math.max(MAX, B);
		}
		System.out.println(MIN + " " + MAX);
	}
}