Codeforces Round 901 (Div. 1)
https://codeforces.com/contest/1874
으아... 아마도 1D는 다시 언급하겠지만 FST가 뜰 것 같았다.
끝나고나서야 FST를 받지 않는 방법을 떠올렸다...
+) 다행히도 AC를 받을 수 있었다. 나처럼 코드를 짰던 테스터가 없었나보다
+) 2797 퍼포, +84 맛있게 먹겠습니다...
A. Jellyfish and Game
몇 번 게임을 굴려보면 결국 몇 번 지나고 나면 둘의 행동이 고정됨을 알 수 있다.
따라서 T = 2000으로 넉넉하니까 테케마다 1000 + (K % 2) 만큼 굴려보면 된다.
B. Jellyfish and Math
우선 각 비트는 서로 영향을 주지 않는다는 것을 알 수 있다.
따라서 한 비트 한 비트를 따로따로 보자.
그러면 {x, y, m} 세트에 4개의 operation을 가하면 {x', y', m'}이 된다는 것을 알 수 있다.
-> {x, y, m}을 마치 2진법으로 생각한다면, 0~7을 또 다른 0~7로 보내는 것임을 알 수 있다.
-> 따라서 어떤 operation은 크기가 8인 벡터로 표현할 수 있다.
그러면 operation1 을 하고 operation2를 하는 것 또한 두 벡터를 합성한 또 다른 벡터로 표현할 수 있다.
이때 m은 변하지 않으므로, 모든 변환의 수는 그렇게까지 많지 않다는 것을 알 수 있다. (많아야 4^8)
따라서 모든 종류의 변환에 대해서 필요한 operation의 수인 dist를 구할 수 있다.
이 과정은 BFS로 할 수 있다.
그러면 A, B, C, D, M이 테스트케이스로 들어왔을 때, 각각의 비트를 살펴 필요한 변환을 구할 수 있다.
이걸 chk이라고 한다면, i번째 비트와 j번째 비트에서 chk[x]가 서로 다르게 나타나야 한다면, 이 변환은 불가능하다.
예를 들어 11(2), 11(2), 10(2), 11(2), 00(2)가 입력이라면,
동일한 operation을 가하였을 때 첫 번째 비트와 두 번째 비트는 동일하게 바뀌어야 하는데 결과가 다르니 불가능하다
이제 chk이 가능하다면, 우리가 미리 구한 dist에서 비교를 하면 된다.
chk에서는 나타나지 않는 변환이 있을 수 있기에 단순히 dist[chk]를 출력하면 안된다.
예를 들어 11(2), 10(2), 10(2), 11(2), 00(2)가 입력이라면,
(1, 1, 0) -> (1, 1, 0) 등은 확인 가능하지만, (1, 1, 1)은 무엇인지 알 수 없다.
따라서 모르는 변환은 배제하고서 dist의 벡터들과 비교해야 한다.
이거도 시간이 꽤 오래 걸리기 때문에 ans라는 map을 또 만드는 것이 좋다.
C. Jellyfish and EVA
Precalc[i][j]를 만들자.
만일 i개의 도로와 연결되어 있고, 확률순으로 정렬했을 때 a[0] < ... < a[i - 1]이라고 가정한다면
(현재 n에 도달할 확률) = sum( a[x] * precalc[i][x] )가 되는 precalc[i][j]를 만들면 된다.
우선 Jellyfish는 무조건 제일 확률이 높은 도로를 선택해야 한다.
이것은 precalc[i][j] <= 1 / i 라는 점을 이용해서 수학적 귀납법 등으로, 혹은 직관적으로 증명할 수 있다.
그러면 우선 precalc[i][i - 1] = 1 / i이다.
Asuka가 동일한 도로를 선택하지 않았다면, 이제 Asuka가 도로 하나를 더 골라서 파괴할 것이고 i - 2인 상황이 된다.
0 <= j < i - 1에 대해서, Asuka는 j / i로 j보다 더 확률이 적은 곳을, (i - j - 2) / i로 더 높은 곳을 파괴한다.
확률이 더 적은 곳을 파괴한다면 j는 사실상 i - 2개 중에서 j - 1번째가 되는 것이고, 아니라면 i - 2개 중 j번째이다.
따라서 precalc[i][j] = j / i * precalc[i - 2][j - 1] + (i - j - 2) / i * precalc[i - 2][j]가 된다.
이렇게 모든 precalc를 구한다면 쉽게 Jellyfish의 행동을 정할 수 있다.
N - 1번째 점부터 시작해서 ans[x]를 N번 점에 도달할 확률이라고 한다면,
모든 인접한 점들을 ans[x]에 대해 정렬한 후 precalc를 곱해서 더해주면 된다.
D. Jellyfish and Miku
식정리를 통해서 다음 사실을 알 수 있다. (생략)
-> b[n - 1] = m * 2 / a[n - 1] - 1
-> 따라서 F(n, m) = Min( m * 2 / x - 1 + F(n - 1, m - x))가 된다.
(F(n, m)에서의 x값 <= F(n, m + 1)에서의 x값)이라는 사실 정도는 눈치챘다.
정해는 여기서 DnC dp를 굴리는 것이다.
이걸 떠올리지 못한 나는 단순히 적당히 x ~ x + 20까지 살펴보며, 최대가 될 때까지 이동하는 방식을 취했다.
x ~ x + 20까지 살펴보면 전체 테스트 케이스 중 50개 정도가 틀린다
x ~ x + 30까지 살펴보면 전체 테스트 케이스 중 10개 정도가 틀린다.
이걸 FST를 맞지 않는 방법이 있다.
로컬에서 굴려서 x ~ x + 30으로 했을 때, 틀리게 되는 10개의 n, m 쌍들을 살펴본다.
그러면 n = 10, m = 2633에서 x를 조정해주면 틀리지 않는다는 사실을 알 수 있다.
-> 따라서 여기에서만 특별하게 x값을 조정해주면 아마도 될 것이다.