from bisect import bisect_left
b,k,l,q=input(),0,2,[]
for i in b:
if l!=i:
l=i
q.append(k)
k+=1
print(q)
for t in range(eval(input())):
a=list(map(int,input().split()))
a.sort()
s,e=a
if s==e:
print('Yes')
else:
print(s, e)
m,n=bisect_left(q,s),bisect_left(q,e)
print(m,n)
if m >= len(q) or q[m] > s:
m-=1
if n >= len(q) or q[n] > e:
n-=1
if m == n:
print('Yes')
else:
print('No')
왜 타임아웃이 발생하는지 노이해염.
더 건드려 보고 싶지만 일단 지금 내가 컴을 떠나야 함 잼
이분들 신택스 하일라이터 안쓰시는분들 ㅠㅠ... 소스코드 보기 어려워..
발자국 남기기를 써봐.
발자국 남기기가 뭔가요? memoization인가요? 검색해봐도 잘안보이고..
int 배열을 똑같이 하나 더 만들고, 같은 동안 지나간 자취에 시작위치를 기록해 두는거야. 시작 위치에는 끝 위치를 기록해 두고.
그러니까 같았던 마지막 위치를 시작위치에 기록
그럼 캐싱이 되지.
몇번을 수행하든 O(n) 수준이지뭐.
두번째 읽을때 부턴 0이 아닌값이 발자취 배열에 들어 있으면 그녀석까지만 일치한다는걸 알 수 있으니 하이패스.
햐 뭔가 봤더니 별 ㅆ스잘데기 없는 문제를... ㅋㅋㅋ 이런걸 왜품?
누가 자꾸 떠들어서
내가 숏코드 순위로 링크해서 코세 낚음
156B 짜증난다.
인자 보고 이해감.. 이렇게 풀수도있구나.. 히익
발자국 남기는 법이 2가지야. 앞을 가리켜서 뒤로 가게하는 2스탭, 혹은 끝가지 갔다가 시작위치로 돌아오며 끝위치를 기록하는 방법. 후자는 2N 이 되는 셈이지만 다시 읽을땐 효율이 좋지.
바이너리 인덱스드 트리 보단 효율 좋을듯 이 문제에서 ㅋㄷㅋㄷ
배워둘게 하늘같이 많네요 ㅋㅋ..
뭐, 시작할때 아예 처음부터 쭈욱 같았던 시작 위치를 기록해 놓고, left right 중 min 범위인 l위치의 발자국을 읽어서 r 보다 큰지 작은지만 비교해도 되고
그러면 완전 O(n) 이지? ㅋㄷㅋㄷ
자료가 너무 너무 크면 발자국 테이블 다 만드는게 비싸니까 점진적으로 (앞에 말한) 방법들을 써도 되궁.
이거 초딩때 쓴 방법이라 내멋대로 이름 붙임.
이게 그 방법인거같아요 보니까
RLE 계열이징
RLE도들어는봤고 binary search도 분명 써보긴 꽤써봤는데 bit 밖에 생각이 안날뿐이고.. 으음
설명 이상하게 적어놨네. ㅋ. 시작할때 부터 일치했던 시작위치를 다 기록해놓고, r 위치의 발자국을 읽어서 l 위치랑 비교해서 l 보다 발자국이 작거나 같으면 같은거.
가령 0000011111 이면 0000055555 라고 맵을 기록해 놓고 l, r 을 4, 5 받으면 footprint[r] > l 이니 "No"
l, r 을 1, 4 받으면 footprint[r] <= l 니 "Yes"
음 그러면 바이너리 서치도 할필요가없네요 이제 완전히 이해가됬습니다 ㅋㅋ...
응 광속 알고리즘.
앞에 설명한 두 가지는 미리 안만들고 읽으면서 만드는 방법.
음... 코세 성님 방법도 재미있군요.
젤 빠른 방법이야. =_=
O(n) 이잖아.
난 숏코딩보단 타임킬이 좋은디.
제가 이 글에서 쓴 방법을 캐시화시킨 개념이로군요
footprint[l] != footprint[r] 면 NO footprint[l] == footprint[r] 면 YES로 해도되지않나요 쫌 헷갈리네요
네 그래서 재미있다고요. 미처 생각을 못함 ㅋㅋ 시간이 없어서 못떠올렸다는 변명을 대 봅니다.
아냐 기준을 어디두냐는 마음이지만, footprint[r] 은 l 이랑, footprint[l] 은 r 이랑 비교해야해.
역순으로 만들면 후자.
며칠전에 rapzzard 가 이미지 라벨링 알고리즘 광속을 원한대서 하나 고안해줌 ㅋㅋ 인터넷에서 찾을 수 있는것들 보단 빠를듯.
footprint끼리 해도 되긴 되겠지만 쓸데없이 배열 참조 한번 더하니 의미없음
왜냐하면, 점진적인 방법에선 둘 다 만들어져있기 힘들거덩.
그거야 그렇죠. 둘 다 풋프린트 보려면 사전에 다 만들어야하죠.
초딩때 미로같은 빌딩에서 도둑이 탈출하는 게임을 만들었거든
그 때 A* 따위를 알질 못해서 끽해야 좌수법 우수법 알던 시절이었는데
그래서 간수를 따돌리기 너무 쉬웠어 =_=
간수? 경비원.
그래서 맵에다 내 발자국을 적었지.(상하좌우)
그때부터 그런류의 알고리즘을 다 발자국이라고 부름 ㅡㅡㅋ
그렇군요 ㄷㄷ
http://dblack.tk
커뮤니티 사이트 입니다 많은 이용 부탁 드립니다.