Codeforces Round 870 (Div. 2)

https://codeforces.com/contest/1826

 

흠... 간만인지 처음인지 가물할 정도로 Div2 올솔을 했다.

E, F가 내가 좋아하는 스타일이 아니기에 기쁘지는 않다.

다만, E, F를 만일 AC를 못 받았다면 매우 화가 났을거라서 그나마 다행이다.

+) 진짜 역대급으로 셋이 이상해서 덕분에 생전 처음으로 12등에 도달한 것 같다.

 

A. Trust Nobody

 

A를 읽다보면 조금 헷갈린다. 무슨 소리를 하고 있는건지가

따라서 그냥 모든 경우의 수를 brute-force하자.

i명의 사람이 거짓말쟁이인 경우가 실제로 가능한지 하나하나 체크해주면 된다.

가능한 경우가 있다면 ok. 없으면 -1

 

B. Lunatic Never Content

 

앞에서부터 차근차근 보자

a[i] = a[n - i + 1] (mod x)이라는 것은 단순하게 a[i] - a[n - i + 1]이 x의 배수라는 것이다.

따라서 모든 (a[i] - a[n - i + 1])의 gcd값을 구해주면 된다.

 

C. Dreaming of Freedom

 

가장 처음 할 수 있는 생각이 2K명이서 2개에 K 표씩 나눠주면 영원히 끝나지 않는다는 것이다.

똑같이 3K, 4K, ... 명이라면 같은 일이 일어난다.

이런 일을 방지하기 위해서는 m이 충분히 작는 일밖에 없다.

따라서 n의 1이 아닌  최소약수가 m보다 작다면 No, 크다면 Yes

 

D. Running Miles

 

그나마 제일 괜찮은 문제이다.

n개의 지점 중에서 한 점을 중심으로 양옆의 L, R을 고른다고 가정하자

그러면 b[L] + b[mid] + b[R] - (R - L)의 최대를 구한다고 생각해도 된다.

이 식은 b[mid] + (b[L] + L) + (b[R] - R)과 똑같다.

따라서 set이나 segtree 등을 이용해서 왼쪽의 (b[L] + L)의 최댓값과 오른쪽의 (b[R] - R)의 최대를 구하면 된다.

어차피 b[mid]는 mid를 중심으로 보고 있는 현재상황에서는 상수이기에 이 셋을 더해주면 된다.

 

모든 mid값에 대한 최댓값을 구하면 답이 나온다.

 

E. Walk the Runway

 

문제 형태가 bitset이 상당히 좋은 형태이다.

수상하게 m = 500이고 (아직도 m = 500의 정체는 모르겠음)

어떤 i번째 모델 다음에 j번째 모델이 올 수 있는지는 0, 1로 쉽게 표현되기 때문이다.

따라서 bitset<5000>에 현재 모델에서 1번, 2번...n번 모델이 다음에 올 수 있는지 저장해주면 된다.

이것은 단순 복잡도가 O(MN^2)인데 분모에 64가 추가되면 생각보다 버틸만한 복잡도가 나온다.

 

O(M * N^2)의 복잡도를 가지는 과정을 설명하자면,

adj[i][j] = (i번 모델 다음에 j번 모델이 올 수 있는가?) 

특정 i번째 마을에서 rating순으로 정렬했을 때 (a[0] > a[1] > ... a[n - 1])번째 모델이 순서대로 온다고 가정하자.

그러면 모든 a[i], a[j] (단, i < j)에 대해서 a[j] 다음에는 a[i]가 올 수 없다.

따라서 N^2개의 쌍에 대해서 adj[ a[j] ] [ a[i] ] = 0을 처리해주면 된다.

 

하지만 여기서 bitset cur을 만들어보자.

그러면 a[0]에서는 cur[a[0]] = 0을 해두면 cur는 a[0]만 0으로 되어있고 adj[a[0]] &= cur을 해도 똑같다.

a[1]에서는 cur[a[1]] = 0을 해두면 cur는 a[1], a[0]가 0으로 되어있고 adj[a[1]] &= cur을 하면 된다.

즉 bit flip을 매번 하나씩 해가면서 & 계산을 해주면 adj에서 하는 작업이 그대로 된다는 뜻이다.

이 bitset을 쓰면 bit flip과 & 계산이 총 N * M번 이루어지는데, & 계산이 N / 64라서 될 것이라고 믿는 것이다.

 

이때 i번째 모델 다음에 j가 오고 j번째 모델 다음에 i가 올 수가 없으므로 사이클이 없다.

따라서 단순한 위상정렬 느낌으로 dp를 굴리면 답이 나온다.

당연히 좋은 풀이가 있을 거라고 생각했지만.... 그건 좀

 

F. Fading into Fog

 

아니 솔직히 점을 주는데 그 정확도가 1e-4라는게 말이 안된다.

+ 알고보니 추가로 노이즈를 주는 거였다니. 굳이 이런 문제 설계를 했어야 했을까?

 

각설하고, 선이 3개 있다면 반드시 답을 구할 수 있다.

x = 0, y = 0, x + 1000y = 0만 쓰면 된다.

x = 0, y = 0을 이용하여 모든 x좌표와 y좌표를 구했다고 가정하자.

그렇다면 우리는 현재 나올 수 있는 N^2개의 쌍이 다음 쿼리에서 모두 다른 점으로 나타나길 바란다.

 

이때 문제에서 x와 y값들은 100이하의 절댓값을 가지며, 동시에 모든 x, y값은 서로 차이가 1 이상이라고 한다.

따라서 200정도가 가능한 최대 기울기이며, 기울기를 1000정도가 넘어가면 무조건 다른 점으로 나타난다.

이때 a, b는 100을 넘지 못하므로 0.1x + 100y = 0을 쿼리로 던져주면 모두 다른 점으로 받는다.

EPS 처리를 잘 해주어서 1e-4라는 답없는 정확도의 입력을 받아도 답을 얻어낼 수 있다.

 

쿼리를 받을때 지나치게 엄격하면 엄격한대로, 너그러우면 너그러운대로 AC를 받지 못한다.

솔직히 내 풀이가 아마 출제자의 의도에 가까워서 AC를 받은 것 같다.

다른 풀이들은 아마 오차로 인해서 아마도 AC 받는게 반쯤 불가능에 가까울 것이다.