Codeforces Round #789 (Div. 2)

https://codeforces.com/contest/1678

 

이때 C번 문제(Div1 기준 A)가 단번에 안 풀리는 것을 보고 나의 상태에 이상함을 감지한 뒤 튀었다.

C, D가 분명 어렵지 않은 문제들인데 나랑 상성이 안좋아서 만일 런하지 않았다면 박살났을 것 같다.

업솔빙(?)할 때 보니 E, F는 상대적으로 잘 풀리는 셋이었다.

 

A. Tokitsukaze and All Zero Sequence

 

전부 0으로 만드세요.

-> 이미 0인게 있거나 같은 쌍이 있다면 바로 0으로 바꿔가는 과정이 가능.

-> 만일 없다면 기본적으로 같은 쌍을 한 번 만들어준 뒤 0을 만들어주어야 하기 때문에 1번 추가됨.

 

B2. Tokitsukaze and Good 01-String (hard version)

 

그리디하게 하거나 DP로 짤 수있다.

이게 의외로 똑바로 그리디나 DP를 설계하지 않으면 매우 잘 틀린다. (*1800)

 

C. Tokitsukaze and Strange Inequality

 

예상 복잡도가 N^2인만큼 애초에 N^2lgn과 같이 segtree를 사용하는 풀이를 기본으로 생각하면 안된다.

-> 특정한 전처리를 해주고 b, c의 위치마다 가능한 tuple의 개수를 세주면 된다.

-> cnt[i][j] : 만일 j > i라면 x >= j이고 a[x] > a[i]인 x의 개수. j < i라면 x <= j이고 a[x] > a[i]인 개수.

-> b와 c의 위치가 결정되면 여기서 가능한 tuple의 개수는 cnt[c][b-1] * cnt[b][c + 1]이 된다.

전처리가 O(N^2), 답을 계산하는 과정도 O(N^2)

https://codeforces.com/contest/1678/submission/156966938

 

D. Tokitsukaze and Meeting

 

관찰 1) 한 번 같은 열에 있었던 학생들은 계속해서 같은 열에 존재한다.

-> (들어가는 순서) % m을 기준으로 학생들을 각 열에 배정해주면 된다.

-> 얌전한 아이가 없던 열에 얌전한 아이가 들어갈 때  (얌전한 아이가 있는 열의 수)++

관찰 2) 제일 최신의 row만을 제외한다면 row들의 상태는 m번 전의 상태와 일치한다.

-> (m번 전의 얌전한 아이가 있는 row의 개수) + (최근 m번 내에 얌전한 아이가 있는지 여부) 

https://codeforces.com/contest/1678/submission/156997732

 

E. Tokitsukaze and Two Colorful Tapes

 

당연하게도 |x- y|식의 계산에서 하나는 양수로, 하나는 음수로 반영되는데, 큰 애들이 많이 더해지는게 좋다. 

ca -> cb로 사이클을 만들 수 있다.-

> 이 사이클의 크기가 짝수라면 더 큰 절반은 항상 +가 되고, 더 작은 절반은 항상 -가 되도록 할 수 있다.

-> 이 사이클의 크기가 홀수라면 적어도 하나는 한 번 더해지고 한 번 빠지게 된다.

-> 따라서 홀수 크기의 사이클의 개수만큼 중간치를 날려버리고 (큰 것들의 합)*2 - (작은 것들의 합)*2한다.

https://codeforces.com/contest/1678/submission/157102440

 

 

F. Tokitsukaze and Permutations

 

관찰 0) a, v가 operation을 한 번 거치면, v가 전부 한 칸씩 앞으로 이동하며 1씩 감소하며, 뒤에 0이 하나 붙는다.

ex) 0 1 0 2 3 0 -> 0 0 1 2 0 0

 

관찰 1) k = 0일 때, v가 결정되면 a가 결정된다. (v와 a는 일대일 대응이 된다.)

야매 pf) 가능한 v의 개수와 가능한 a의 개수가 놀랍게도 n!으로 동일하다. 따라서 이 둘은 대응할 것이다.

엄밀 pf) v가 주어진다면 뒤에서부터 적당하게 a를 만들 수 있다.

-> 따라서 k = 0일 때의 v의 개수를 세면 답을 구할 수 있다.

 

관찰 2) 어떤 k에 대해 0의 개수가 i개인 수열 v는 k번의 opeation 이전에 ((k + 1)^i) * k!개 종류가 가능하다.

노가다 pf) 직접 combination이랑 씨름해보면 i = 1이면 2^i, i = 2면 2 * 3^i, i = 3이면 6 * 4^i

엄밀 pf) 이미 있던 i개의 0은 k번을 거슬러 올라가면 0~k가 모두 가능하여 (k+1)^i

            거슬러 올라가면서 수열의 맨 앞에 0이 계속 붙는데, 이 0들이 가능한 수열의 개수가 k!

 

관찰 3) 굳이 0의 개수가 i개인 초기 수열의 개수를 센 뒤 각각에 ((k + 1)^i) * k를 곱해 답을 구할 필요가 없다!

-> 0이 오면 경우의 수가 모두 동일하게 (k + 1)배가 된다.

-> 따라서 -1이 오면 (i + k + 1)배, 0이 오면 (k + 1)배, 양수가 오면 1배를 시켜주면 답이 된다.

유의) 마지막 k개에 0이 아닌 숫자가 올 수는 없으므로 이런 경우에는 가능한 a의 개수가 0개이다.

https://codeforces.com/contest/1678/submission/157352126