Codeforces Round #810

https://codeforces.com/contest/1710

 

1B를 2명 정도 풀었는데 1E를 20명이 푼 이상한 라운드.

E가 중국에서 연습문제로 매우 잘 알려진 것을 베낀 문제 + 댓글에 공유됨.

댓글에 안 공유되었으면 언레할지 말지가 더 큰 논란이었을 듯한데 다행히 누가 공유해주었다.

 

2A. Perfect Permutation

 

p[i] = i + 1로 하면 된다.

 

2B. Party

 

모든 간선의 수가 짝수라면 단순하게 0이 답이된다.

 

간선의 개수가 홀수라면 아래 두 가지 중 한가지가 답이 된다.

1) 인접한 간선의 수가 홀수인 정점 하나를 지운다.

2) 간선들 중에서 인접한 간선의 수가 짝수인 두 정점을 잇는 간선이 있다면 그 두 정점을 지운다.

-> 만일 인접한 간선의 수가 홀수인 정점이 간선에 포함되어 있다면 1)에서 이미 고려하였기에 따질 필요가 없다.

1)에서 확인할 개수가 정점의 수인 n개, 2)에서 확인할 개수는 간선의 수인 m개이므로 O(n + m)

 

A. Color the Picture

 

그림의 모양은 반드시 (같은 색의 행이 2행 이상씩 붙은 형태) or (같은 색의 열이 2열 이상씩 붙은 형태)이다.

-> 만일 아니라면, 반드시 색이 접히는 부분에서 안되는 지점이 생긴다.

따라서 간단하게 2열 이상씩, 혹은 2행 이상씩 같은 색으로 칠했을 때 그림이 가능한지 따져주면 된다.

 

조심해야되는 예외는 최대 2열, 2열, 2열...씩 가능하고 실제 열의 개수는 홀수인 경우이다.

이럴경우 전체 열을 칠해줄 수 있다고 생각할 수 있지만 반드시 한 색은 1열만 칠해지게 되어 불가능하다.

 

B. Rain

 

사실 이런 문제들에서 왜 굳이 x들을 정렬시켜서 주지 않는지 모르겠다.

제일 중요한 관찰은 flood가 일어나는지 안 나는지를 비가 내리는 지역의 중심들에서만 확인하면 된다는 것이다.

-> 만일 어떤 x[i] < x < x[j]인 지역 x에서 flood가 난다면, x[i], x[j] 중 하나에서도 반드시 flood가 나기 때문이다.

 

대회 중에 구현하였을 때에는 nlgn으로 살짝 더럽게 구현했지만 더 이쁜 풀이가 있다.

https://codeforces.com/contest/1710/submission/165562651

우선 모든 event들을 기록한다. (처음으로 비가 내리는 부분, 비의 중심, 비가 더이상 안 내리는 부분)

그 다음 현재 보고 있는 event에서 내리는 비의 양을 나타낼 s, 거리당 비의 양의 변화량을 나타내는 d를 저장하자.

 

1) 만일 현재 지역이 비의 중심이라면 flood가 날 가능성이 있으므로 w[i] = s로 이 지역에 내린 비의 양을 저장한다.

2) 현재 보고있는 event가 처음으로 비가 내리는 곳이면 d++, 중심이면 d -= 2, 끝난 곳이면 d++를 해준다.

(처음 비가 내리는 곳 이후에는 거리당 비가 1씩 더 내리며, 중심 이후에는 1씩 덜 내리며, 끝나면 변화가 없다.)

3) 직후의 event와의 거리를 이용해서 s += d * (거리)를 해준다. 

-> 이를 통해서 모든 지역에 내리는 비의 양을 알 수 있다.

 

특정 i번째 입력에서 x[i]에 p[i]만큼의 비가 내린다고 가정하자.

또한 특정 x[j]에서 w[j]만큼의 비가 내려 홍수가 난다 가정하자.

-> x[j] >= x[i]라면 (w[j] - m) > p[i] - (x[j] - x[i])면 여전히 홍수가 난다.

-> x[j] <= x[i]라면 (w[j] - m) > p[i] - (x[i] - x[j])면 여전히 홍수가 난다.

따라서 MAX(w[j] - m + x[j]) 값을 p[i] + x[i]와 비교해주고, MAX(w[j] - m - x[j]) 값을 p[i] - x[i]와 비교해주면 된다.

 

C. XOR Triangle

 

(a ^ b) + (a ^ c) - (b ^ c) = 2 * ((a & ~b & ~c) | (b & c & ~a)) > 0 이다. (벤 다이어그램을 그리면 더 쉽다)

아무튼 a한테만 있거나 a한테만 없는 비트가 있어야 한다.

-> 따라서 이 조건을 이용해서 포함과 배제를 해주면 된다.

-> (조건 0개) - 3 * (조건 1개 불만족) + 3 * (조건 2개 불만족) - (조건 3개 불만족)를 계산해주면 답을 구할 수 있다.

 

dp[i][j] : 앞에서부터 i번째 비트까지 고려했을 때 j에 대응되는 상태를 가지는 경우의 수

-> j에 대응되는 상태 : (j & 1)이면 a가, (j & 2)이면 b가, (j & 4)면 c가 n과 앞에서부터 i번째 비트와 동일한 상태

이제 i + 1번째 비트는 벤 다이어그램 상에서 8가지의 가능한 위치가 존재한다. (이 값도 위의 j와 비슷하게 정의)

(단, 조건을 1개 만족시키지 못할 때마다 가능한 위치가 2개씩 감소한다.)

-> 이 가능한 위치들 (k) 각각에 대해서

if) n도 이 비트를 가지고 있다면 j & k의 상태로 변화하게 된다. 

-> dp[i + 1][j & k] += dp[i][j]

if) n이 이 비트를 가지고 있지 않다면  j & k = 0일때만 그 위치에 비트를 위치시킬 수 있다.

-> if(j & k == 0) dp[i + 1][j] += dp[i][j]

 

https://codeforces.com/contest/1710/submission/165629329