Codeforces Global Round 20

https://codeforces.com/contest/1672

 

E를 FST 당해서 퍼포가 2210. 

57분에 제출한 E가 만일 맞아서 1272점을 받았다면 2580 정도의 퍼포로 +150였을텐데 아쉽다.

 

A. Log Chopping

 

길이 x짜리 log는 x - 1번 chop할 수 있다 -> chop의 총 횟수를 구해주면 된다.

 

B. I love AAAB

 

맨 끝이 B이고 항상 B의 개수가 A의 개수 이하이면 된다.

https://codeforces.com/contest/1672/submission/154695824

 

C. Unequal Array

 

어차피 문제에서 주어진 operation을 가하면 여전히 1쌍의 숫자는 같다.

-> 따라서 operation을 할 것이라면, 맨 앞에 있는 같은 쌍부터 맨 뒤에 있는 같은 쌍까지 모두 다르게 만들어줘야 한다.

-> 이미 같은 쌍의 개수가 1개 이하라면 0을 뱉고, 그게 아니면 (맨뒤 - 맨앞 - 1)번 가해주면 된다.

https://codeforces.com/contest/1672/submission/154711941

 

D. Cyclic Rotation

 

b의 뒤에서부터 역으로 a를 만들어주면 된다.

만일 1 2 3 4 5 6 6 처럼 b에 6이 연속되어 있다면, 더 앞에 있는 b는 1, 2, 3, 4, 5 옆의 아무 곳으로 갈 수 있다.

따라서 a의 idx와 b의 idx를 j, i라 할 때 a[j] != b[i]라면 

1) b[i] == b[i + 1]이라면 b[i]를 leftover에 저장해두고 i--

2) 그것도 아니라면 더 뒤에 있던 b[i'] == b[i'+1]에서 온 leftover과 매칭이 가능한지 확인

https://codeforces.com/contest/1672/submission/154723004

 

E. notepad.exe

 

우선 30번 이하의 이분탐색으로 결과가 1이 나오는 최소 w를 구할 수 있다.

-> 그렇다면 (모든 문자열의 길이의 합) + (n - 1) = w 이다.

이 값을 기반으로 w / 1, w / 2 , w / 3 ... 를 물어보면 최소값을 알아낼 수 있다.

https://codeforces.com/contest/1672/submission/154775083

저 최소 w를 찾는 이분탐색에서 L = 0이라고 하면 Test 14에서 틀린다. R = 4e6으로 하면 test 20에서 틀린다고 한다.

(누텔라도 이거에 당해줘서 기분이 나쁘지 않다.)

 

F1. Array Shuffling

 

a[i] -> b[i]의 간선들의 그래프를 생각할 때, cycle의 수가 최소한이 되어주면 된다. 답은 n - cycle의 수이다.

-> 이때 cycle의 수의 최솟값은 제일 많이 등장하는 숫자의 개수 이상이다.

-> (개수가 1 이상인 숫자들로 이루어진 cycle), (2 이상인 숫자들로 이루어진 cycle)...을 만들면 위의 개수가 가능하다.

https://codeforces.com/contest/1672/submission/154746479

 

F2. Checker for Array Shuffling

 

Cycle의 개수를 세야한다고 생각한다고 접근하였는데 성공하지 못하였다.

-> Cycle의 개수를 굳이 셀 필요 없이 그 개수가 (제일 많이 등장하는 숫자의 개수)와 다르다는 것만 보이면 된다.

-> 심지어 제일 많이 등장하는 숫자는 그 Cycle들에 모두 한 번씩 등장하여야 한다.

-> 따라서 제일 많이 등장하는 숫자를 제거한 그래프는 DAG가 되어야 한다.

https://codeforces.com/contest/1672/submission/154770519

 

제일 많이 등장하는 숫자가 모든 Cycle에 등장한다는 생각을 하지 못한 것이 패착이 된 것 같다.

또한 너무 빡센 과제인 'Cycle의 최소 개수 세기'에 몰두하였다.

사실 F2 정도 위치라면 위의 과제를 시킬만도 하다고 생각했기 때문에 그런생각을 한 것 같기도 하다.

 

혹시라도 위의 작업을 진행한 사람이 있나 찾아봤는데 없는 듯하다.

정답을 알고나니 모든 점에서 더이상 degree가 없을 때까지 계속해서 cycle을 굴려주면 될 것 같기도 하다.

 

참고로 이번에 F2, G, H의 난이도 조절은 실패했다.

F2가 112솔, G가 29솔, H가 134솔이다.

ABCDEF1이 생각보다 아이디어틱해서 (소위 말하는 능지셋) GH도 보기는 할 생각이다. 

 

G. Cross XOR

 

일단 귀찮으니 여기서의 a + b 는 일반적인 a + b가 아니라 (a + b) % 2라고 하자.

대놓고 a[i, j] = (i행이 골라진 횟수) + (j열이 골라진 횟수) + (i, j가 골라진 횟수)이다.

그러면 예를 들어 a[i, 0] + a[i, 1] + ... = (i행이 골라진 횟수) * c + (전체 고르기) + (i행 고르기)이다.

-> c가 홀수라면 항상 1씩 증가하고, c가 짝수라면 i행이 골라졌는지 여부에 따라 달라진다

혹시 특정한 움직임으로 예쁘게 한 칸을 뒤집거나 짝지어진 두 칸을 뒤집는 방법이 존재하는가?

-> 직사각형의 네 꼭짓점 정도는 내가 원하는대로 뒤집기 가능.

이쯤하고 시간이 끝

 

1) r과 c가 모두 짝수라면 내가 원하는대로 칸뒤집기가 가능하다.

-> (i, j)에 대해서 i 또는 j가 겹치는 모든 칸을 전부 뒤집어주면 된다.

2) r과 c 중에 하나가 홀수라면 (wlog c) 모든 i에 대해 a[i, 0] + a[i, 1] + ... 이 같기만 하다면 가능하다. 

-> (i, j)에 대해서 (0, j) ... (i - 1, j) (i + 1, j) ... (r - 1, j), (0, c - 1), ... (i - 1, c - 1), (i + 1, c- 1) ... 만 뒤집는다

-> 그러면 임의의 (i, j)의 상태를 (i, c)와 함께 바꾸어줄 수 있다.

-> a[i, 0] + a[i, 1] + ... 값은 원래 모두 동일하므로 마지막에 a[i, c] 또한 0될 것이고 가능하다.

3) r과 c가 모두 홀수라면?

-> 아까 위에서 언급한 대로 4개를 뒤집는 방법을 이용해서 전부 꺼야한다.

-> 조금 더 복잡하지만 모든 R과 모든 C가 매칭되어야 한다.

https://codeforces.com/contest/1672/submission/154758841

 

H. Zigu Zagu

 

F2를 풀면서 동시에 염두에 두고 있었던 문제.

쿼리의 형태가 이 문제도 대놓고 너무 f(R) - f(L)을 이용하는 문제여서 이 적당한 f를 찾는데 집중하였다.

-> 그래서 우선적으로 그냥 [0, i]를 전부 삭제하는데 필요한 조작의 횟수부터 구하는 것을 try함

-> 그래서 DP를 하는데 state를 4개정도 저장해두면 된다.

-> 1) 마지막 구획에 0이 추가가능한지, 1이 추가가능한지  2) 적당한 조작으로 이 앞에 그 반대가 존재하는지

Ex) 010 01 이라면 마지막 구획 뒤에 0이 추가가능하며, 01을 먼저 제거하면 1을 추가하는 것도 가능하다.

-> 이쯤하고 시간이 끝.

 

우리가 어떤 구간을 삭제할 때, 그 구간은 시작과 끝만 정해지면 내부는 010101꼴이기에 중요하지 않다.

즉 삭제될 수 있는 구간의 종류는 [0, 0], [0, 1], [1, 0], [1, 1]으로 총 4가지이다.

당연하게도 [0, 0] 또는 [1, 0] 뒤에는 [0, 0] 또는 [0, 1]이 와야 한다.

-> 만일 이것이 아닌 1로 시작하는 구간이 온다면, 굳이 이 둘을 다른 구간으로 나눌 필요가 없기 때문이다.

따라서 모든 A의 부분수열은 [a, b][b, c][c, d][d, e] ... 의 형태로 유일하게 구간을 나눌 수 있다.

이때 만일 b != c라면, 구간 [b, c]를 먼저 제거하면 동시에  [a, b] + [c, d]로 구간을 지울 수 있고 직관적으로 이득이다.

 

claim) [a1, a2][a2, a3]...[a(n - 1), an]에서 a2 ~ a(n - 1) 중 0의 개수를 b0, 1의 개수를 b1이라하면 max(b0, b1) + 1이 답

pf) 일반성을 잃지않고 우선 b_0 < b_1이라고 가정하자.

    -> [~ 0][0, 1][1, ~]에서 사이를 지운다고 가정하자. 구간의 끝에 있는 1의 개수는 1개 감소한다.

    -> [~ 1][1, 1][1, ~]에서 사이를 지운다고 가정하자. 마찬가지로 구간의 끝에 있는 1의 개수는 1개만 감소한다.

    -> 따라서 구간을 어떻게 지우더라도 맨 끝의 1의 개수나 0의 개수를 2개 이상 줄이는 것은 불가능하다.

    -> 마지막 delete에서는 결국 [a1, an]이기에 b0와 b1은 0이 되어야 하므로 최소 max(b0, b1)만큼을 해야한다.

따라서 맨처음에 언급했던 prefix sum 비슷한 방법으로 b0와 b1을 구해주면 답을 구할 수 있다.

https://codeforces.com/contest/1672/submission/154740773

 

1) 구간을 삭제하는 것이 그렇게까지 엄청나게 이득이 되는 경우는 없었다.

-> 고작해야 앞뒤가 합쳐지는 정도였기에 greedy한 방법 또한 마찬가지로 그렇게까지 더럽지는 않을 것이다.

2) 따라서 [0, i]를 삭제하는 방법을 생각해낼 때에 무지성 dp를 쓰지 않고 어느 정도 greedy한 방법을 생각했어야 한다.

-> 만일 이 greedy한 방법(구간의 끝에 있는 1의 개수나 0의개수 계속 줄이기)을 생각해냈다면 풀었을 것이다.

3) 만일 그러한 방법을 생각해내지 못하였더라도, 이 문제의 경우 delete가 일어날 때마다 1씩 감소하는 숫자가 있다.

-> Hint2에서 언급되었듯이, invariant 혹은 일정한 규칙성을 가진 variant를 발견하였으면 풀 수 있었을 것이다.

 

 

G랑 H에 조금 더 시간을 들였다면 그리디한 방법을 찾을 수 있었을까?

그리고 F2, G, H는 아무리봐도 G가 제일 훨씬 어렵다.