Learning Algorithms

アルゴリズムの勉強メモ

AOJ Prime Caves

AOJ Prime Caves

感想

実装がめんどくさい

解法

どう見てもDPするだけ。$\ m \leq 10^6\ $なので、$\ 1000 * 1000\ $の正方形のマスを用意して考えればよい。すごく面倒だが、各数を投げるとその配列上での位置を返す関数を作る。これは各正方形の左上の数が、偶数の二乗になっていることを考慮して実装した。ここに$\ 10^6\ $以下の素数をすべて投げてそこにフラグを立てておく。

あとは、$\ n\ $が表す位置から下に向かって三角形を広げるようにDPをする。下限は計算するのが面倒なので、一番下まで計算してしまって良い。これで前半の答えがわかり、さらにこの最大値をとるような位置の中で、その数が素数であるようなものの最大値をとれば、それが後半の答えである。このとき、位置からもとの数がなんだったのかを知る必要があるので、さっきの関数の中で、ついでに位置から数がわかるように配列に書き込んでおくとよい。$\ O(m)\ $。

実装
#include "bits/stdc++.h"
using namespace std;

int s[1000][1000];
int dp[1000][1000];
int p[1000][1000];

pair<int, int> get_pos(int n) {
        if (n == 1) return make_pair(500, 499);
        int top_left = 1;
        int k = 1;
        while (n > top_left) {
                top_left = (2 * k) * (2 * k);
                k ++;
        }
        k --;
        int top_right = top_left - 2 * k + 1;
        int bottom_right = top_right - 2 * k + 1;
        int bottom_left = bottom_right - 2 * k + 1;
        int y, x;
        if (n <= bottom_left) {
                y = 499 - k + 1 + (2 * k - 1 - (bottom_left - n));
                x = 499 - k + 1;
        } else if (n <= bottom_right) {
                y = 499 + k;
                x = 499 - k + 1 + (n - bottom_left);
        } else if (n <= top_right) {
                y = 499 - k + 1 + (top_right - n);
                x = 499 + k;
        } else { 
                y = 499 - k + 1;
                x = 499 - k + 1 + (top_left - n);
        }
        p[y][x] = n;
        return make_pair(y, x);
}

int N = 1000000;
vector<int> primes;
vector<bool> is_prime(N + 1, true);
void init() {
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i <= N; i ++) {
                if (is_prime[i]) {
                        primes.push_back(i);
                        for (int j = i + i; j <= N; j += i) is_prime[j] = false;
                }
        }
}

int main() {
        init();
        int m, n;
        while (scanf("%d%d", &m, &n) && n) {
                for (int i = 0; i < 1000; i ++) for (int j = 0; j < 1000; j ++) s[i][j] = 0;
                for (auto p : primes) {
                        if (p > m) break;
                        int y, x;
                        tie(y, x) = get_pos(p);
                        s[y][x] = 1;
                }
                int dp[1000][1000] = { 0 };
                int sy, sx;
                tie(sy, sx) = get_pos(n);
                dp[sy][sx] = s[sy][sx];
                for (int dy = 0; sy + dy + 1 < 1000; dy ++) {
                        for (int dx = -dy; dx <= dy && sx + dx < 1000; dx ++) {
                                dp[sy + dy + 1][sx + dx - 1] = max(dp[sy + dy + 1][sx + dx - 1], s[sy + dy + 1][sx + dx - 1] + dp[sy + dy][sx + dx]);
                                dp[sy + dy + 1][sx + dx]     = max(dp[sy + dy + 1][sx + dx]    , s[sy + dy + 1][sx + dx]     + dp[sy + dy][sx + dx]);
                                dp[sy + dy + 1][sx + dx + 1] = max(dp[sy + dy + 1][sx + dx + 1], s[sy + dy + 1][sx + dx + 1] + dp[sy + dy][sx + dx]);
                        }
                }
                int ans = 0;
                for (int i = 0; i < 1000; i ++) {
                        for (int j = 0; j < 1000; j ++) {
                                ans = max(ans, dp[i][j]);
                        }
                }
                if (ans == 0) { 
                        cout << 0 << ' ' << 0 << endl;
                        continue;
                }
                int res = -1;
                for (int i = 0; i < 1000; i ++) {
                        for (int j = 0; j < 1000; j ++) {
                                if (dp[i][j] == ans && s[i][j]) {
                                        res = max(res, p[i][j]);
                                }
                        }
                }
                cout << ans << ' ' << res << endl;
        }
        return 0;
}