問題

問題URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1232
提出ソースコード: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1357423
- 解答なので閲覧注意
- 言語はJava

問題文訳

1974年12月16日の土曜日、プエルトリコのアレシボ天文台に、地球外知的生命体から人類にメッセージが送られてきた。メッセージは1679ビットで、これは 23 x 73 の長方形の図に変換される。23と73はともに素数であり、面積が1679になり、かつ1辺が1より長い唯一の長方形である。ただし、メッセージはぴったり長方形の図に変換できるとは限らない。

我々は小さなプロジェクトを計画している。このプロジェクトにおけるあなたの仕事は、"最も適した"長方形を探すことだ。整数 m (m > 4) と、正の分数 a/b (a/b <= 1) が与えられるので、幅と高さがともに素数で、面積はmを超えず、幅と高さの比がa/b以上1以下になる長方形の中で、最も面積が最大になるような長方形を探せ。

言い換えると、 m (m > 4), a/b (a/b <= 1) が与えられるので、 pq <= m かつ a/b <= p/q <= 1 となるような素数の対p, qの中で、 pqが最大となるようなものを探せ。

入力は、一行にm, p, qが空白区切りが与えられ、m, p, q の組み合わせが最大2000行ある。入力の最後は "0 0 0" で表される。 4 < m < 100000, 1 <= a <= b <= 1000 である。

出力は、ひとつの m, p, q の組み合わせに対して、幅と高さの対を空白区切りで1行で出力せよ。

(訳注: 入出力は入出力例を見たらわかりやすいと思う)

ソースコード解説

Primeクラス

素数問題の時に使う自作クラス。

/**
 * 整数を数え上げたりするクラス
 */
class Prime{
    static boolean[] isPrime;
    static int[] count;
    static ArrayList<Integer> list = new ArrayList<Integer>();
    
    /**
    * nまでの計算をエラトステネスの篩で行う
    */
    static void init(int n){
        isPrime = new boolean[n+1];
        isPrime[0] = false; isPrime[1] = false;
        for(int i = 2; i <= n; i++) isPrime[i] = true;
        // ふるい
        for(int i = 2; i < (n - 3) / 2; i++){
            if(isPrime[i]){
                for(int j = 2; j * i <= n; j++){
                    isPrime[j * i] = false;
                }
            }
        }
 
        // 数え上げと集合の作成
        count = new int[n+1];
        count[0] = 0;
        for(int i = 1; i <= n; i++){
            int gain = 0;
            if(isPrime[i]){
                gain = 1;
                list.add(i);
            }
            count[i] = count[i-1] + gain;
        }
    }
    /**
    * 入力されたiに対して、素数かどうか判定をして返す
    * @return true: iが素数である    false: iが素数でない
    */
    static boolean calcPrime(int i){
        if(i <= 1) return false;
        if(i == 2) return true;
        if(i % 2 == 0) return false;
        for(int j = 3; j <= Math.sqrt(i); j+=2){
            if(i % j == 0) return false;
        }
        return true;
    }
}

このクラスは Prime.init(n) とすることで、nまでの整数までの配列を作成し、エラトステネスの篩を行います。Prime.isPrine(i) で i (i <= n) が素数かどうかを調べることができます。また、Prime.list にはn以下の素数のListが作成されます。

回答本体部分

class Main extends MyUtil{
    // public static Graph g;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // prime の準備
        Prime.init(100000);
        
        while(true){
            // 入力
            String[] in = br.readLine().split(" ");
            int m = Integer.parseInt(in[0]);
            int a = Integer.parseInt(in[1]);
            int b = Integer.parseInt(in[2]);
            if(m == 0 && a == 0 && b == 0) break;
            
            int pointer_p = 0, pointer_q = Prime.list.size() - 1;
            int ans_m = 0, ans_p = 0, ans_q = 0;
            
            while(pointer_p <= pointer_q){
                int p = Prime.list.get(pointer_p);
                int q = Prime.list.get(pointer_q);

                if(p*Prime.list.get(pointer_q) > m){
                    pointer_q--;
                    continue;
                }
                
                for(int i = pointer_p; i <= pointer_q; i++){
                    int qq = Prime.list.get(i);
                    if((double)a/b <= (double)p/qq){
                        if(ans_m < p*qq){
                            ans_m = p*qq;
                            ans_p = p;
                            ans_q = qq;
                        }
                    }
                }
                pointer_p++;
            }
            
            System.out.println(ans_p + " " + ans_q);
        }
    }
}

まず、100000までのPrime.listを作成する
pointer_p と pointer_q を用意する。pointer_pは最初にリストの左端を、pointer_qは最初にリストの右端を指している
pointer_p に対して、pointer_qが、p*qがmを超えない最大のqの場所を指すようにする。（pointer_qを左に動かしていく）
p = list[pointer_p] *1 , q = list[pointer_q] として、qqをpからqの間で変化させる。
p*qqで、a/b <= p/qq を満たすp,qqのうち、面積がこれまでの最大値を超える場合はそれらの値を記録する
- pointer_p <= pointer_q が保たれている限り、p < qq すなわち p/qq <= 1 は保証されているのでここではチェックしていない
最終的に面積が最大になった p, q を出力する。

はまりどころ

pointer_pとpointer_qを左右から近づけていくだけだと、a/b <= p/q <= 1 を満たすようなものがうまく見つけられないことがあるので、しっかりと探索する必要がある。
100000以下の素数の数は9592個 ≒ 10⁴個とすると、素数だけに絞って全探索すると 10⁴ * 10⁴ = 10⁸ となってしまい、これではおそらく間に合わないので、pとqを左右から近づけていく感じで枝刈りをする必要がある。

*1:説明のためにlist.get(pointer_p)を簡易的に表記している