結果

問題 No.3121 Prime Dance
ユーザー AKI
提出日時 2025-04-20 13:09:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,805 bytes
コンパイル時間 2,841 ms
コンパイル使用メモリ 213,948 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-20 13:09:31
合計ジャッジ時間 4,221 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

/* ---------- 素数テーブル ---------- */
struct PrimeTable {
    int N;
    vector<int> primes;
    vector<char> isPrime;
    PrimeTable(int n = 20000) { build(n); }

    void build(int n) {
        N = n;
        isPrime.assign(N + 1, 1);
        isPrime[0] = isPrime[1] = 0;
        for (int i = 2; i * 1LL * i <= N; ++i)
            if (isPrime[i])
                for (int j = i * i; j <= N; j += i) isPrime[j] = 0;
        for (int i = 2; i <= N; ++i)
            if (isPrime[i]) primes.push_back(i);
    }
    bool operator()(int x) const { return 0 <= x && x <= N && isPrime[x]; }
} primeTbl(40000);               // 上限 4 万で十分

/* ---------- BFS で最短距離 ---------- */
const int INF = 1e9;
int bfsDist(const vector<string>& G, int sx, int sy, vector<vector<int>>& dist) {
    const int H = G.size(), W = G[0].size();
    dist.assign(H, vector<int>(W, INF));
    queue<pair<int,int>> q;
    dist[sx][sy] = 0; q.emplace(sx, sy);
    const int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
    while(!q.empty()){
        auto [x,y]=q.front(); q.pop();
        for(int dir=0;dir<4;++dir){
            int nx=x+dx[dir], ny=y+dy[dir];
            if(nx<0||nx>=H||ny<0||ny>=W) continue;
            if(G[nx][ny]=='#'||dist[nx][ny]!=INF) continue;
            dist[nx][ny]=dist[x][y]+1;
            q.emplace(nx,ny);
        }
    }
    return 0;            // 呼び出し側で dist[Gx][Gy] を見る
}
/* ---------- 2 ステップ縦(or 横)ループがあるか ---------- */
bool hasStraightLoop(const vector<string>& G,
                     const vector<vector<int>>& dist,
                     bool vertical){            // true→縦, false→横
    const int H = G.size(), W = G[0].size();
    int dx = vertical ? 1 : 0;
    int dy = vertical ? 0 : 1;
    for(int x=0;x<H;++x)for(int y=0;y<W;++y){
        if(dist[x][y]==INF) continue;           // 到達不能
        int nx=x+dx, ny=y+dy;
        if(nx<0||nx>=H||ny<0||ny>=W) continue;
        if(G[nx][ny]!='#'&&dist[nx][ny]!=INF) return true;
    }
    return false;
}
/* ---------- 差分 Δ に対する候補和列を作る ---------- */
vector<int> buildSumList(int diff, bool loopAble,
                         int maxPrime = 40000,
                         int maxExtra = 2000){
    vector<int> sums;
    const auto& isP = primeTbl.isPrime;
    const auto& primes = primeTbl.primes;

    if (diff >= 0){
        for(int q: primes){
            int p = q + diff;
            if(p>maxPrime) break;
            if(!isP[p]) continue;

            // k=0 は必ず
            sums.push_back(p+q);

            if(loopAble){
                int k = 1;
                while(2*k <= maxExtra){
                    if(p+k>maxPrime || q+k>maxPrime) break;
                    if(isP[p+k] && isP[q+k]) sums.push_back(p+q+2*k);
                    ++k;
                }
            }
        }
    }else{ // diff < 0
        for(int p: primes){
            int q = p - diff;        // q > p
            if(q>maxPrime) break;
            if(!isP[q]) continue;
            sums.push_back(p+q);
            if(loopAble){
                int k = 1;
                while(2*k <= maxExtra){
                    if(p+k>maxPrime || q+k>maxPrime) break;
                    if(isP[p+k] && isP[q+k]) sums.push_back(p+q+2*k);
                    ++k;
                }
            }
        }
    }
    sort(sums.begin(), sums.end());
    sums.erase(unique(sums.begin(), sums.end()), sums.end());
    return sums;
}
/* ---------- メイン ---------- */
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int H,W;  cin>>H>>W;
    int Sx,Sy,Gx,Gy;  cin>>Sx>>Sy>>Gx>>Gy;
    --Sx;--Sy;--Gx;--Gy;

    vector<string> G(H);
    for(auto& s:G) cin>>s;

    /* --- 最短距離 & 到達判定 --- */
    vector<vector<int>> dist;
    bfsDist(G,Sx,Sy,dist);
    int D = dist[Gx][Gy];
    if(D==INF){ cout<<-1<<"\n"; return 0; }

    int dx = Gx - Sx;
    int dy = Gy - Sy;

    /* --- ループ判定 --- */
    bool vLoop = hasStraightLoop(G,dist,true);
    bool hLoop = hasStraightLoop(G,dist,false);

    /* --- 差分ごとの候補和列 --- */
    auto vSums = buildSumList(dx, vLoop);
    auto hSums = buildSumList(dy, hLoop);

    if(vSums.empty() || hSums.empty()){
        cout<<-1<<"\n"; return 0;
    }

    /* --- 二列マージで最小和 ≥ D --- */
    int ans = INT_MAX;
    for(int sv: vSums){
        int need = D - sv;
        if(need <= 0){
            ans = min(ans, sv + hSums.front());
            continue;
        }
        auto it = lower_bound(hSums.begin(), hSums.end(), need);
        if(it!=hSums.end()){
            ans = min(ans, sv + *it);
        }
    }
    if(ans==INT_MAX) ans=-1;
    cout<<ans<<"\n";
    return 0;
}
0