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; }