Codeforces Global Round 4 풀이

https://codeforces.com/contest/1178

 

A번

 

1번 원소 >= x번 원소 * 2 인 지점을 다 더해준 값을 y 라고 합니다.

y + (1번 원소)가 전체 배열의 합의 절반보다 strictly 하게 크면 YES 이고 아니면 NO 입니다.

 

B번

 

처음에 vv 가 w 를 만들 수 있는 모든 경우의 수를 구합니다.

즉 vvovvovv 가 있으면 3일 겁니다.

dp 배열로 구성합니다.

if(s[x] == 'v')
	dp[x] = dp[x+1] + 1;
    if(dp[x]>=2) ans++;
}else{
	dp[x] = 0;
}

이런 식으로 하면 모든 경우의 수가 ans 가 될 것입니다.

그런 다음 처음부터 보면서 o 를 기준으로 왼쪽 오른쪽에 vv의 경우의 수를 곱해주면 됩니다.

 

C번

 

(1,1) 지점의 가능한 경우는 4가지 일 것입니다.

그리고 (1,x) 과 (x,1) 의 가능한 경우는 2가지 일 것입니다.

왜냐하면 (1,x) 는 (1,x-1) 에서 나왔던 색깔의 반대방향을 넣어주는 것이 2가지이기 때문입니다.

그럼 (2,2) 부터는 윗 방향과 왼쪽 방향의 색깔이 정해져있기 때문에 가능한 경우의 수는 모두 1가지 일 것입니다.

즉 4 * 2 ^ (n-1) * 2 ^ (m-1) 입니다.

 

D번

 

한 가지만 알면 바로 풀립니다.

n ~ n + (n/2) 사이엔 무조건 소수가 있습니다.

그럼 그냥 1 - 2 , 2 - 3 , 3 - 4 ... n - 1 이런 식으로 모두 이어주면 일단 각 정점의 간선의 수는 2개이고 전체 간선의 수는 n 일 것입니다.

그럼 n ~ n + (n/2) 사이에 소수가 있다고 했으니 그 소수 - n 의 간선만 각각 다른 정점에 이어준다면 각 정점에 이어진 간선의 갯수는 2 ~ 3 으로 소수일 것이고 전체의 간선도 소수가 될 것입니다.

 

E번

 

a b c 만 존재하고 연속된 알파벳은 같지 않으니

(ab) (ac) (bc) (ba) (ca) (cb) 가 될 것입니다.

그럼 예를 들어 문자열 제일 왼쪽 부분에 ab가 나왔다고 가정하겠습니다.

그럼 문자열 제일 뒷쪽 부분엔 어떤것이 나와도 무조건 a b 둘 중에 하나는 있을 것입니다.

왜냐하면 cc 로 나타나는 것이 불가능하기 때문입니다.

그럼 a b 둘중에 하나를 추가해주고 불가능 할 때까지 해줍니다.

그럼 2개의 문자 중에 하나는 무조건 될 것이기 때문에 전체 문자열 / 2 의 길이는 보장이 되게 됩니다.

 

F1 번

 

dp[l][r] 을 밑에 어떤 색깔이 오든 상관 없이 l ~ r 이 같은 색깔로 덮혀있었다고 가정할 때 가능한 경우의 수라고 가정하겠습니다.

그럼 l ~ r 사이에 가장 작은 수의 위치를 x 라고 가정하겠습니다.

그리고 l ~ (x-1) 사이의 한 점 t를 잡으면

(t - (x-1) ) 의 수들은 x 의 수에 의해 덮혀져 있다고 합시다.

x 오른쪽으론 갈 수 없는 것이 x가 먼저 칠해지기 때문에 x 오른쪽으로 가 버리면 x의 수를 다시 칠할 수 없기 때문입니다.

그리고 l ~ (t-1) 은 x의 수에 덮혀져 있지 않다고 합시다.

그럼 dp[l][t-1] * dp[t][x-1] 이 값이되고

오른쪽 부분도 똑같이 해줍니다.

그리고 두 값을 곱해주면 dp[l][r]의 값이 되게 됩니다.

 

F2 번

 

F1에서 추가된 것은 배열의 길이가 10^6 이 되었다는 겁니다.

그러면 이제 어떤 색깔이 있을 때 중복된 색깔도 있다는 거겠죠?

생각을 천천히 해봅시다.. 해보면 x 라는 색깔이 있을 때 y ( x<y ) 는 x 의 왼쪽 오른쪽에 하나 이상 동시에 존재할 수 없습니다. 

왜냐하면 x 보다 작은 y 가 x 양쪽에 하나씩 있으면 y가 칠해질 때 x를 덮어버리기 때문이죠

여기서 한단계 더 생각해보면 그럼 x 가 있고 모든 y ( x<y ) 는 젤 왼쪽에 있는 x 왼쪽에 있거나 젤 오른쪽에 있는 x 오른쪽에 있거나 x 와 x 사이에 ( 그 사이안엔 x가 없어야 합니다 ) 존재할 수 밖에 없습니다.

즉 이렇게 생각하게 되면 중요한 점이 배열의 위치가 상관없어집니다!!

이유는 어차피 서로가 서로를 가로지르지 못하고 안에 있거나 아예 왼쪽 오른쪽에 있게되다 보니 하나의 집합처럼 움직이게 됩니다. 예를 들어 2...23...34...4 이런 식으로 있다면 ... 안에 있는 집합은 어차피 2,3,4가 오지 못합니다.

즉 (2)(3)(4) 이렇게 묶어서 생각할 수 있습니다. 그럼 문제에서 배열의 길이가 1e6이 되었지만 실상 dp 배열은 색깔의 갯수로 처리가 가능해집니다.

즉 N^3 인 500^3 으로 풀릴 수 있게되는 것입니다.

즉 그럼 x 왼쪽 오른쪽은 F1 처럼 이제 위치 -> 색깔로 바꾸고 풀면되고 이제 문제는 x 와 x 사이의 구간입니다.

근데 이 구간은 생각하기 쉬운게 어차피 x 와 x 사이의 구간엔 x 보다 큰 숫자만 올 수 있으므로

그냥 처음 문제 처럼 돌아가서 x 를 0이라 생각하고 F2의 작은 문제를 푼다고 생각하면 됩니다.

그렇게 되면 x의 위치가 a b c d 라고 가정하면 [a+1,b-1] , [b+1,c-1] , [c+1,d-1] 의 구간으로 생각해서 다시 풀어주면 됩니다.

 

G번 부턴 레이팅이 3000을 넘어가는 문제들이라 일단 해야되는 거 다른거 마저하고 풀도록 하겠습니다.