2013国内予選 D. 素数洞穴

解法

洞穴のマップを頑張って生成する

各洞穴への到達時の最適解は上の洞穴から順に確定させていける
- 最適解：pair(通った素数洞穴の数、最後に通った素数洞穴の番号) の最大値

全ての洞穴について到達時の最適解を確定させ、最も良かったものを答えれば良い

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};

bool isPrime(int p){
    if(p==1) return false;
    for(int i=2;i*i<=p;i++)
        if(p%i==0) return false;
    return true;
}

int main(){
    static int id[1000][1001];
    static int pt[1000][1001];
    vector< pair<int,int> > pos(1);
    memset(pt, -1, sizeof(pt));
    memset(id, -1, sizeof(id));
    id[500][500] = 1; pt[500][500] = 0; pos.push_back(make_pair(500, 500));
    id[500][501] = 2; pt[500][501] = 1; pos.push_back(make_pair(500, 501));
    int dir = 0;
    int curX = 500, curY = 501;
    for(int i=3;i<=1000000;++i){
        int ndir = (dir+1)%4;
        if(pt[curX+dx[ndir]][curY+dy[ndir]]!=-1) ndir = dir;
        curX += dx[ndir];
        curY += dy[ndir];
        id[curX][curY] = i;
        pt[curX][curY] = isPrime(i);
        pos.push_back(make_pair(curX, curY));
        dir = ndir;
    }
    int m, n;
    while(cin >> m >> n && n){
        pair<int, int> res = make_pair(isPrime(n), isPrime(n) ? n : 0);
        vector< vector< pair<int,int> > > dp(1000, vector< pair<int,int> >(1001, make_pair(-1, -1)));
        dp[pos[n].first][pos[n].second]  = res;
        for(int i=pos[n].first;i+1<1000;i++){
            for(int j=0;j<=1000;j++){
                if(dp[i][j].first == -1) continue;
                for(int k=-1;k<=1;k++){
                    if(j+k<0||1000<j+k) continue;
                    if(id[i+1][j+k] < 0 || m < id[i+1][j+k]) continue;
                    pair<int,int> next = dp[i][j];
                    if(pt[i+1][j+k]) next.first++, next.second = id[i+1][j+k];
                    dp[i+1][j+k] = max(next, dp[i+1][j+k]);
                    res = max(res, dp[i+1][j+k]);
                }
            }
        }
        cout << res.first << " " << res.second << endl;
    }
}