[Codeforces] 768B. Code For 1 (반례 및 테스트케이스 있음)

오늘 아침에 업무하던 중, 업무를 마치고 중간에 쉬는 시간에 우리 학교 에브리타임 IT게시판을 둘러보다가 발견한 문제이다. 3학년 과목의 '알고리즘연습' 수업의 과제라고 한다. 마침 내가 전역 후 복학하면 들을 수업이기도 해서 너무 궁금하기도 하고 매우 잘됐다 싶어서 급하게 풀어보았다. 이럴 때를 대비해서 codeforces 계정을 만들어놓길 잘했다. 나중에 복학하기 전에 영어독해 공부도 좀 하고 코드포스도 해보고싶다.

codeforces.com/problemset/problem/768/B

Problem - 768B - Codeforces

일단 난 영어 울렁증이 있어서 이 문제를 이해하는 데에 한참 걸렸다. 10분 정도 걸렸나.

대략적으로 해석을 해보자면 아래와 같다.

 

문제 (대략적인 번역 추가)

---

어떤 숫자 N (0<=N<=2^50)이 주어진다.

이 수를 N/2, N mod 2, N/2 순으로 재배치할 수 있다. 즉, 수가 n개 있다면 재배치를 하면 수가 2n+1개가 되는 것이다. 이 재배치는 모든 수들이 1 또는 0으로만 이루어져 있을 때까지 계속 진행한다.

입력으로 L, R이 주어지면 L번째 인덱스부터 R번째 인덱스까지 1이 몇 개인지 구하여라. (이 때, L, R은 1 이상, R-L<=10^5)

---

오... 뭔가 쉬워보이는데, 생각만큼 쉽지는 않다. 확실한건 N이 엄청 커서 웬만한 시간복잡도 풀이로는 불가능하다는 점이다. 처음엔 INT_128 범위까지도 나와야되나 싶었는데, 아니다. 그 이유는 밑에 서술하겠다.

의식의 흐름 및 해설

일단 N이 2^50이니까 생각나는 건 세그먼트 트리나 분할정복 정도가 되겠다.

딱히 세그먼트트리처럼 보이진 않아서 분할정복 아이디어를 생각하고 접근해봤다.

 

일단, x mod 2의 값은 무조건 0 또는 1이므로 생각할 필요가 없고,

양쪽의 x/2만 생각해주면 되므로 시간복잡도는 O(logN) 정도가 되겠다.

수가 계속 x/2가 되고, 1이 될 때 리턴해주면 되겠다고 생각했다.

 

그런데 문제는 L, R 범위 내의 1만 구해주는 문제여서 짜증났다.

cur이 현재 수, idx는 idx번 후 0, 1로만 이루어지는 경우를 뜻할 때,

단순히 solve(cur/2, idx-1)로만 하면 어차피 모든 범위에서 다시 수를 따져보므로 O(N)이나 다름없게 된다. (내 설명이 진짜 부족할 수 있다. 근데 뭐라 설명을 못하겠음...)

(참고로 idx는 log2(N)이다. 모든 수가 1 이하가 되려면 최대 N이 1이 될 때를 구하면 되기 때문이다)

 

따라서 왼쪽 x/2가 가능한 인덱스 범위, 오른쪽 x/2가 가능한 인덱스 범위를 따져서

세그먼트트리 아이디어처럼 L, R 내에 속할 때만 탐색해주면 된다. 이 조건문이 없으면 O(N)이 돼서 시간초과를 받을 것이다. 간능한 인덱스 범위를 따지는 방법은 왼쪽 x/2는 1 ~ (현재 인덱스) * (1LL<<idx) 까지이고, 오른쪽 x/2는 (현재인덱스)*(1LL<<idx)+1 ~ 끝까지가 되겠다.

 

 

테스트케이스 및 반례

0 1 1
ans: 0

19999999999999 1 20000
ans: 11368

66 4 100
ans: 50

1125899906842624 1002 101002
ans: 50000

1125899906842623 1002 101002
ans: 50001

N이 0일 때를 진행해주지 않으면 24번째 테스트케이스에서 오류가 난다.

코드

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll N, L, R;
ll solve(ll cur, int idx, ll l){
	ll ret=0;
	// idx가 0이면 재배치 완료(모든 수가 0, 1)
	// l은 cur이 존재하는 인덱스(위치)
	if(!idx && L<=l && l<=R)
		return ret+=cur;
	else if(!idx)
	    return ret=0;
	// 왼쪽 덩어리가 가능한 인덱스 범위가 L보다도 작으면 탐색 필요 x
	if(l*pow(2, idx)-1>=L)
	    ret+=solve(cur/2, idx-1, l*2-1);
	// cur mod 2는 어차피 1 이하이므로, 최종 범위만 확인해주면됨.
	ret+=solve(cur%2, 0, l*(ll)pow(2, idx));
	// 오른쪽 덩어리가 가능한 인덱스 범위가 R보다도 크면 탐색 필요 x
	if(l*pow(2, idx)+1<=R)
	    ret+=solve(cur/2, idx-1, l*2+1);
	return ret;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	
	cin>>N>>L>>R;
	if(!N){
		cout<<0<<"\n";
		return 0;
	}
	// 재배치는 log2(N)번 일어남.
	cout<<solve(N, log2(N), 1)<<"\n";
}

 

---

이 문제를 풀고 이 문제가 어느정도인지 궁금해서 레이팅을 봤는데 1600 정도라고 한다.

내가 codeforces를 안해서 1600이 어느정도인진 모르겠지만 solvedac 티어 기준 Gold III 정도에 속하는 문제일 듯 하다.

(참고로 문제 레이팅 1600 말고, 유저 레이팅 1600은 얼마나 대단한건지 잘 알고 있다. 이 문제를 10분~20분내에 빠르게 풀라 했으면 과연 난 잘 풀었을까? 난 푸는데 한 40분~50분 걸린 것 같다...)