No.12 限定された素数 - yukicoder
- 印象深かったのでメモ
- a[i] の出現が必要十分であることを確認するのに最初 map とかでカウントしようとしてコードがぐちゃぐちゃになっていた。
- a[i] が 0,...,9 までしかないなら bit フラグで管理すれば簡単じゃん。ってことですっきり書けた。
class LimitedPrimeNumber {
public:
void solve(void) {
int N;
cin>>N;
int bit = 0;
#define encode(A) (1<<((A)+1))
REP(i, N)
{
int a;
cin>>a;
bit |= encode(a);
}
const int upper = 5000000;
const auto primes = sieve(upper);
int n = primes.size();
vector<int> bits(n, 0);
REP(i, n)
{
int p = primes[i];
while (p)
{
bits[i] |= encode(p%10);
p /= 10;
}
}
int start = 0;
int KL = -1;
while (start < n)
{
if (bits[start] & ~bit)
{
++start;
continue;
}
int end = start;
int bit2 = 0;
while (end < n && !(bits[end] & ~bit))
{
bit2 |= bits[end];
++end;
}
if (start == end)
++end;
else if ((bit2 ^ bit) == 0)
{
int K = start>0? primes[start-1]+1 : 1;
int L = end<n? primes[end]-1 : upper;
KL = max(KL, L-K);
}
start = end;
}
cout<<KL<<endl;
}
};