글 읽기 - 파이썬으로는 못 푸나요?

ahmg1216 2년 전 0

제목 그대로입니다

한 테케에 대해 O(lgN) 정도의 시간복잡도인것 같지만 여전히 시간초과가 납니다

파이썬으로 맞으신 분이 한분도 없는 걸 보면 애초에 파이썬이 안되나 싶기도 합니다

개선할 사항이 있다면 알려주세요

memoization=[]
dp=[[0]*61for _ in range(3601)]
dp[0][0]=1
for _ in range(60):
    ndp=[[0]*61for _ in range(3601)]
    for s in range(_**2+1):
        for combo in range(_+1):
            if dp[s][combo]!=0:
                ndp[s+combo*2+1][combo+1]+=dp[s][combo]
                ndp[s][0]+=dp[s][combo]
    dp=ndp
    l=[]
    s=0
    for coml in dp[:(_+1)**2+1]:
        s+=sum(coml)
        l.append(s)
    l.extend([s]*(3601-(_+1)**2-1))
    memoization.append(l)
def cnt(N,K):
    t=N+1
    if N==-1:
        return 0
    N=bin(N)
    combo=0
    s=0
    for digit in range(len(N)-2,1,-1):
        if N[-digit]=='1':
            t-=memoization[digit-2][K-s]
            s+=combo*2+1
            combo+=1
            if s>K:break
        else:
            combo=0
    t-=int(s<=K)+int(N[-1]=='1' and s+combo*2+1<=K)
    return t
def score(C):
    C=bin(C)[2:]
    combo=0
    s=0
    for r in C:
        if r=='1':
            combo+=1
        else:
            s+=combo**2
            combo=0
    s+=combo**2
    return s
import sys;input=lambda:sys.stdin.readline()
for _ in range(int(input())):
    a,b,c=map(int,input().split())
    n=score(c)
    sys.stdout.write(str(cnt(b,n)-cnt(a-1,n)+1)+'\n')

cozyyg 1년 전 1

추가 시간이 없어서 파이썬으로 풀기는 좀 어렵게 되긴 했지만, PyPy3로 풀 수 있습니다. 제 코드는 1620ms에 통과했습니다.

제 코드에 비추어 팁을 드리자면 bin보다는 bitwise operator(&, >>, << 등)를 사용하는 것이 좋고, 전처리가 너무 오래 걸리지 않도록 하는 것도 중요합니다. 메모리를 너무 많이 사용하는 것도 시간이 오래 걸리는 원인이 될 수 있으니, 가급적이면 60*3600 정도 스케일의 배열 딱 한 개 정도만 써서 푸는 방법을 찾는 것이 좋습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬으로는 못 푸나요?

ahmg1216 2년 전 0

cozyyg 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말