3258-River Hopscotch

問題（外部リンク）

3258 -- River Hopscotch

実装の概要

最小値を最大化する問題です。どのm個の石を取り除くかを全探索で考えようとすると間に合いません。
そこで、最大値を仮定し二分探索を利用して絞り込みます。
仮定した解をaとすると、今回の問題は「毎回距離a以上を保ちながら次の石に移動し続けることができるか。途中、合計m回まで石をスキップできる」と読み替えることができます。チェックの条件もこれに基づいて実装します。このチェックは1回あたりでできます。
二分探索なので最初の探索の範囲も重要ですが、rightの初期値は十分大きい値であればint型の上限の必要はありません。もっとも数回しか探索回数が変わらないのでそれほど問題ではありません。
なお、N=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 l = Integer.parseInt(tmpArray[0]);
		int n = Integer.parseInt(tmpArray[1]);
		int m = Integer.parseInt(tmpArray[2]);

		int stones[] = new int[n + 1];

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

		stones[n] = l;

		System.out.println(solve(stones, l, m));
	}

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

		int left = 0;
		int right = l + 1;

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

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

		return left;
	}

	//interval以上の距離を開けつつ移動することはできるか
	static boolean check(int stones[], int l, int m, int interval){
		Arrays.sort(stones);
		int n = stones.length;

		//途中に石が1つもない場合
		if(n == 0){
			if(interval >= l){
				return true;
			}
			else {
				return false;
			}
		}
		int position = 0;
		int index = 0;
		while(position < l){
			//どこに飛べば良いかを探す
			for(int i = index; i < n; i++){
				//十分に遠い場合
				if(stones[i] - position >= interval){
					position = stones[i];
					index = i + 1;
					break;
				}
				else {
					m--;
					//スキップ回数がmを超えたら失敗
					if(m < 0){
						return false;
					}
				}
			}
		}

		return true;
	}

}

1995-Raising Modulo Numbers

問題（外部リンク）

1995 -- Raising Modulo Numbers

実装の概要

問題文ではやや難しい表現を使っていますが、出力の仕様に書いてある計算式の通り累乗したものを加算してmodを求めることで解くことができます。
その際、指数部が大きく普通にループを回すと計算が間に合わないので繰り返し二乗法を用います。
Mの値がそれほど大きくないので数回足したくらいではオーバーフローにはなりませんが、途中でmodを計算しても同じ結果になるのでその都度modを求めた方が安全です。

public class Main {

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

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

		for(int i = 0; i < z; i++){
			int m = Integer.parseInt(br.readLine());
			int h = Integer.parseInt(br.readLine());

			int result = 0;
			for(int j = 0; j < h ; j++){
				String[] tmpArray = br.readLine().split(" ");

				int a = Integer.parseInt(tmpArray[0]);
				int b = Integer.parseInt(tmpArray[1]);

				result += repeatablePow(a, b, m);
				result %= m;
			}

			System.out.println(result);
		}
	}

	static long repeatablePow(int x, int n, int mod){
		if(n == 0){
			return 1;
		}
		long result = repeatablePow((int)((long)x*x%mod), n/2, mod);
		if(n % 2 == 1){
			result = result*x%mod;
		}
		return result;
	}

}

3641-Pseudoprime numbers

問題（外部リンク）

3641 -- Pseudoprime numbers

実装の概要

となっているかを判断する問題ですが、注意点がいくつかあります。
まず、pの値が大きいので乗算を普通のループで計算すると間に合いません。そのためここでは繰り返し二乗法を使います。
また、この問題で問われているのがpがaに対する"pseudoprime"かということです。pが素数の場合はa>1である限り上記の式を満たしますが、それは普通のprimeなので除外しなければなりません。
そこで乗算の前にまずpが素数かどうかを判定する必要がありますが、入力されうる全てのpに対してテーブルを作ってしまうとメモリが足りません。
そのためテーブル作成は途中までで妥協して、ある程度より大きい値の判定には「割れる値がないか順番にひたすら探す」という方法に切り替える必要があります（ある値がnならまで確認すれば重要なので間に合います）

public class Main {

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


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

        	int p = Integer.parseInt(tmpArray[0]);
        	int a = Integer.parseInt(tmpArray[1]);

        	if(p == 0 && a == 0){
        		break;
        	}

        	//片方が素数ならno
        	if(pg.isPrime(p)){
        		System.out.println("no");
        		continue;
        	}
        	long result = repeatablePow(a, p, p);
        	if(result == a){
        		System.out.println("yes");
        	}
        	else {
        		System.out.println("no");
        	}
        }

	}

	static long repeatablePow(int x, int n, int mod){
        if(n == 0){
            return 1;
        }
        long result = repeatablePow((int)((long)x*x%mod), n/2, mod);
        if(n % 2 == 1){
            result = result*x%mod;
        }
        return result;
    }

}

class PrimeNumberGenerator {
	int N = 10000001;
    private boolean[] isPrime= new boolean[N];

    public PrimeNumberGenerator() {
        Arrays.fill(isPrime, true);

        isPrime[0] = false;
        isPrime[1] = false;
        isPrime[2] = true;

        int limit = (int)Math.sqrt(isPrime.length);
        for(int i = 3; i <= limit; i+=2){
            if(isPrime[i] == false){
                continue;
            }

            for(int j = i * 2; j <= isPrime.length - 1; j += i){
                isPrime[j] = false;
            }
        }
    }

    public boolean isPrime(int index){
    	//ある程度以上大きいものについてはその都度ループを回して判定
    	if(index >= N){
    		int limit = (int)Math.sqrt(index);

    		if(index%2 == 0){
    			return false;
    		}
    		for(int i = 3; i <= limit ; i += 2){
    			if(index%i == 0){
    				return false;
    			}
    		}

    		return true;
    	}

    	else if(index % 2 == 0 && index != 2){
            return false;
        }
        return isPrime[index];
    }
}

3292-Semi-prime H-numbers

問題（外部リンク）

3292 -- Semi-prime H-numbers

実装の概要

この問題では数字はの形で表されるH-numberしか現れません。
H-primeかどうかの判定は通常の整数に対するエラトステネスの篩を改修することで実現できますが、H-semi-primeかどうかの判定は困難です。この篩では掛ける数まで素数かどうかは考慮していないからです。
そのため、この実装ではやや強引ですが2回篩にかけます。即ち、1回目はH-numberがH-primeかどうかを、2回目はH-compositeの中にH-semi-primeが存在するかを判断するためにループを回します。
なお、もともとH-numberしか考えないので1,000,001までの全ての値について配列を用意する必要はありません。

public class Main {

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

		//-1: unit 0 : prime 1 : semi-prime 2 : other-composite
		int type[] = new int[250001];
		type[0] = -1;

		//素数かどうかを判定するための初期化
		for(int i = 1; i < type.length ; i++){
			if(type[i] == 0){
				for(int j = 5; (4*i + 1)*j <= 1000001 ; j += 4){
					int tmpN = ((4*i + 1)*j - 1)/4;
					type[tmpN] = 2;
				}
			}
		}

		//こちらではsemi-primeかどうかを判定
		for(int i = 1; i < type.length ; i++){
			if(type[i] == 0){
				for(int j = 5; (4*i+1)*j <= 1000001 ; j += 4){
					int tmpN = ((4*i+1)*j - 1)/4;
					//素数と掛けたものならsemi-prime
					if(type[j/4] == 0){
						type[tmpN] = 1;

					}
					else {
						type[tmpN] = 2;
					}
				}
			}
		}

		while(true){

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

			if(n == 0){
				break;
			}

			int result = 0;
			//semi-primeならresult加算
			for(int i = 1; i*4+1 <= n ; i++){
				if(type[i] == 1){
					result++;
				}
			}

			System.out.println(n+" "+result);
		}
	}

}

3421-X-factor Chains

問題（外部リンク）

3421 -- X-factor Chains

実装の概要

例えばX=100であれば条件を満たす数列は
1,2,4,20,100
1,5,25,50,100
など計6パターンが有りえますが、ポイントとなるのはXを素因数分解した結果です。であることを考えると2つの2と2つの5をどの順番で掛けるかによってパターンが決まります（掛けてさえいれば必ず前の数で次の数を割り切れるような数列になります）。
問題では最長にすることが目標になっているので、そのためには合成数は使わずに素数のみを掛け続ければ求められます。
そのため、「Xは何回素数で割れるか」と「それぞれの素数で何回割ったか」を記録しておけばあとは順列の問題と同様に階乗を求めることで計算できます。
なお、素数テーブルは特に準備しなくても大丈夫です。

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 == null){
				break;
			}

			solve(Integer.parseInt(input));
		}
	}

	static void solve(int n){

		int divisor = 2;

		//どの素数で何回割ったかを記録する
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

		int totalNum = 0;
		while(n > 1){
			//divisorで割り切れた場合
			if(n%divisor == 0){
				n /= divisor;
				totalNum++;

				if(map.containsKey(divisor)){
					map.put(divisor, map.get(divisor) + 1);
				}
				else {
					map.put(divisor, 1);
				}

				continue;
			}

			//割り切れなかったならdivisor更新
			divisor++;
		}

		Set<Integer> set = map.keySet();
		Iterator<Integer> it = set.iterator();

		long patterns = fact(totalNum);
		//それぞれの素数の個数の階乗で割る
		while(it.hasNext()){
			int tmp = it.next();

			patterns /= fact(map.get(tmp));
		}

		System.out.println(totalNum+" "+patterns);
	}

	//階乗を求める
	static long fact(int n){
		long result = 1;

		for(int i = n; i >= 1 ; i--){
			result *= i;
		}

		return result;
	}

}

3126-Prime Path

問題（外部リンク）

3126 -- Prime Path

実装の概要

それぞれの素数をグラフの頂点と考え、ある特定の桁だけ数字を変えれば良い場合は距離を1として初期化します。
その後はある頂点から別の頂点までの最短距離を求める問題と考えることができます。ワーシャルフロイド法では流石に間に合わないこと、テストケースが100個しかないことからその都度ダイクストラ法を用いて計算します。
優先度付きキューを用いたダイクストラ法であれば十分間に合います。
なお、今回の問題では入力だけでなく途中の数字も4桁と仮定して構いません。

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		@SuppressWarnings("unchecked")
        ArrayList<Edge> edges[] = new ArrayList[10000];

		for(int i = 0; i < 10000; i++){
            if(edges[i] == null){
                edges[i] = new ArrayList<Edge>();
            }
        }

		PrimeNumberGenerator pg = new PrimeNumberGenerator();

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for(int i = 1000; i < 10000; i++){
			if(!pg.isPrime(i)){
				continue;
			}
			//iから1の位だけを変えたもののパスを作る
			for(int j = 1 ; j <= 9 - i%10; j++){
				int tmp = i + j;
				if(pg.isPrime(tmp)){
					edges[i].add( new Edge(tmp, 1));
					edges[tmp].add( new Edge(i, 1));
				}
			}

			//iから10の位だけを変えたもののパスを作る
			for(int j = 1 ; j <= 9 - (i/10)%10; j++){
				int tmp = i + j*10;
				if(pg.isPrime(tmp)){
					edges[i].add( new Edge(tmp, 1));
					edges[tmp].add( new Edge(i, 1));
				}
			}

			//iから100の位だけを変えたもののパスを作る
			for(int j = 1 ; j <= 9 - (i/100)%10; j++){
				int tmp = i + j*100;
				if(pg.isPrime(tmp)){
					edges[i].add( new Edge(tmp, 1));
					edges[tmp].add( new Edge(i, 1));
				}
			}

			//iから1000の位だけを変えたもののパスを作る
			for(int j = 1 ; j <= 9 - (i/1000)%10; j++){
				int tmp = i + j*1000;
				if(pg.isPrime(tmp)){
					edges[i].add( new Edge(tmp, 1));
					edges[tmp].add( new Edge(i, 1));
				}
			}
		}

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

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

			int a = Integer.parseInt(tmpArray[0]);
			int b = Integer.parseInt(tmpArray[1]);

			int[] result = dijkstra(edges, a, 10000);

			if(result[b] != INF){
				System.out.println(result[b]);
			}
			else {
				System.out.println("Impossible");
			}
		}

	}

	static final int INF = Integer.MAX_VALUE;
	//ダイクストラ法
    static int[] dijkstra(ArrayList<Edge>[] edges, int s, int n){

        PriorityQueue<Distance> que = new PriorityQueue<Distance>();
        int[] dist = new int[n];

        Arrays.fill(dist, INF);
        dist[s] = 0;
        que.add(new Distance(0, s));

        while(!que.isEmpty()){
            Distance tmpDist = que.poll();
            int tmpV = tmpDist.id;

            if(dist[tmpV] < tmpDist.dist){
                continue;
            }
            for(int i = 0; i < edges[tmpV].size() ; i++){
                Edge e = (Edge) edges[tmpV].get(i);
                if(dist[e.to] > dist[tmpV] + e.cost){
                    dist[e.to] = dist[tmpV] + e.cost;
                    que.add(new Distance(dist[e.to], e.to));
                }
            }
        }

        return dist;
    }

}

//ダイクストラ法に用いるためのクラス
class Distance implements Comparable<Distance>{
    int dist;
    int id;

    Distance(int dist, int id){
        this.dist = dist;
        this.id = id;
    }

    @Override
    public int compareTo(Distance d) {
        return this.dist - d.dist;
    }
}

//ダイクストラ法に用いるためのクラス
class Edge {
    int to;
    int cost;

    Edge(int to, int cost){
        this.to = to;
        this.cost = cost;
    }
}

//素数テーブルを生成するためのクラス
class PrimeNumberGenerator {
    private boolean[] isPrime= new boolean[10000];

    public PrimeNumberGenerator() {
        Arrays.fill(isPrime, true);

        isPrime[0] = false;
        isPrime[1] = false;
        isPrime[2] = true;

        for(int i = 3; i <= 9999 ; i++){
            if(i % 2 == 0){
                isPrime[i] = false;
                continue;
            }

            if(isPrime[i] == false){
                continue;
            }

            for(int j = i * 2; j <= 9999; j += i){
                isPrime[j] = false;
            }
        }
    }

    public boolean isPrime(int index){
        return isPrime[index];
    }
}

2429-GCD & LCM Inverse

問題（外部リンク）

2429 -- GCD & LCM Inverse

実装の概要

与えられた最大公約数（GCD）と最小公倍数（LCM）からもともとの2つの整数を逆算する問題。
入力値がlong型なので全パターン試そうとすると間に合いません。また、a+bが最小になるようにという条件にも注意が必要です。
そこで、（ただしは互いに素）とすると、と表せることを利用します。するとa,bではなく適切なp,qを探せばよいのでこの時点で探す範囲が1からに限定されます。
そしてこのp,qも1から探していく必要はありません。からpの値を小さくし、条件を満たす（つまりp,qが互いに素な）pとqの組み合わせが見つかればそこで処理を終えても大丈夫です。
理由をざっくりと説明すると、pの値を小さくしてしまうと（もちろんqが整数になるような値にします）qがその分だけ大きくなるだけでは済まず、和が最小という条件を満たすことができないからです。
そしてa<=bという条件からp<=qであり、pとして有り得る値の最大値はp=q、すなわちとなります。
実際、問題ページの例であればまずとなり、なのでp=4から順に検証すれば良いということになります。

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 == null){
				break;
			}
			String[] tmpArray = input.split(" ");

			long gcd = Long.parseLong(tmpArray[0]);
			long lcm = Long.parseLong(tmpArray[1]);
			
			long pq = lcm/gcd;
			
			long p = 0;
			long q = 0;
			for(int i = (int)Math.sqrt(pq) ; i >= 1; i--){
				if(pq%i == 0){
					p = i;
					q = pq/i;
					
					//互いに素であるかチェック
					if(GCD(p, q)== 1){
						break;
					}
				}
			}
			
			System.out.println(p*gcd+" "+q*gcd);
		}
	}
	
    static long GCD (long a, long b){
	    long c = a;
	    while (b % a != 0) {
	      c = b % a;
	      b = a;
	      a = c;
	    }
	    return c;
	}

}