acmicpc.net 1509,2079(DP, 팰린드롬), 13275(Manacher's Algorithm, 팰린드롬), 1990(소수,팰린드롬)

https://www.acmicpc.net/problem/1509, https://www.acmicpc.net/problem/2079

1. 글자들을 팰린드롬 이 가능한지 나눠준다. [x,y]범위에서 팰린드롬이 가능한지 설정해준다.

이것을 dp리스트에 저장해둔다.

2. 나눠진 팰린드롬을 나눈다. 이게 dp2리스트의 일이다. 

# -*- encoding: cp949 -*-
import sys
sys.setrecursionlimit(1000000)
dp = [[0 for i in xrange(2502)] for j in xrange(2502)]
dp2 = [0 for i in xrange(2502)]

def divide(p):
    if p<0:
        return 0
    if dp2[p]!=0:
        return dp2[p]

    dp2[p] = 9999999999
    for i in xrange(p,-1,-1):
        if dp[i][p]==1:
            dp2[p] = min(dp2[p],1+divide(i-1))
    return dp2[p]

s=raw_input()
n = len(s)
for i in xrange(n-1,-1,-1):
    for j in xrange(i,n):
        if i==j: dp[i][j] = 1
        elif i+1==j and s[i]==s[j]: dp[i][j] = 1
        elif dp[i+1][j-1]==1 and s[i]==s[j]: dp[i][j] = 1

print divide(n-1)

https://www.acmicpc.net/problem/13275

앞에서 Manacher's Algorithm에 대해 글을 썼었다. http://qkqhxla1.tistory.com/743

저 알고리즘은 모든 부분 팰린드롬을 구하는데, 해당 코드를 조금 변경하면 가장 '긴' 팰린드롬을 구하는

것도 가능하다.

# -*- encoding: cp949 -*-
s = list(raw_input())
n = len(s)
s += [0 for i in xrange(200000)]
r = [0 for i in xrange(200000)]

for i in xrange(2*n-2,-1,-1):
    if i%2==0:
        s[i] = s[i/2]
    else:
        s[i] = '#'

ans = 0
p = rmax = -1
n = 2*n-1
for i in xrange(n):
    if i <= rmax:
        r[i] = min(rmax - i, r[2*p - i])
    j = r[i]+1
    while i-j>=0 and i+j<n:
        if s[i-j]==s[i+j]:
            r[i] += 1
        else:
            break
        j += 1
    if rmax < i+r[i]:
        p = i
        rmax = p+r[p]

#print s[:n]
for i in xrange(n):
    if i%2==0:
        if r[i]/2*2 + 1 > ans: #변경한 부분
            ans = r[i]/2*2 + 1 #변경한 부분
    else:
        if (r[i]+1)/2*2 > ans: #변경한 부분
            ans = (r[i]+1)/2*2
#print r[:n+1]
print ans

https://www.acmicpc.net/problem/1990

소수와 팰린드롬을 구하는 문제이다. 근데 범위가 1억까지이다. 일반적인 에라토스테네스의 체를 쓰면

시간초과가 난다. 구글링 등을 해서 엣킨의 체나, 아니면 개선된 에라토스테네스의 체 등 빠른걸

찾아서 쓰면 된다.

# -*- encoding: cp949 -*-
def primes(n):
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n/3)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)/3)      ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
        sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
    return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]

p = primes(100000002)
a,b=map(int,raw_input().split())
for i in p:
    if str(i)==str(i)[::-1] and i>=a and i<=b:
        print i
print -1