NWRRC 2022

https://codeforces.com/gym/104012

 

딱히 팀에 전략은 없는데 잘 굴러가는 것 같다.

 

A. Absolutely flat

 

a1, a2, a3, a4에 b를 한 번 붙여서 전부 같도록 할 수 있는지 확인하면 된다.

-> Hibye가 읽자마자 풀어서 AC (+2)

 

L. Limited Swaps

 

차이가 2 이상인 경우만 swap이 가능할 때, a를 b로 바꾸는 것이 가능한 문제이다.

-> 차이가 1인 경우에는 앞뒤관계가 바뀔 수 없다.

-> 따라서 a와 b에서 1 차이인 두 수가 앞뒤관계가 다른 경우가 있는지 확인해주면 끝

 

K번부터 읽기 시작해서 Hibye가 AC를 받을 때 쯤 이미 L의 풀이를 떠올렸다.

다만, 중복되어서 숫자가 나타날 수 있는지 알고 잠시 구현 헤맸지만, 예제를 보고 permutation임을 알았다.

AC (+7)

 

N. New Time

 

L번을 보고 나서 대시보드를 보니 많이 풀려있었다.

매우 간단한 구현문제이기 때문에 곧바로 AC (+11)

 

C. Computer Network

 

그냥 항상 제일 적은 곳에 포트를 꼽으면 되기에 priority queue를 쓰면 풀 수 있다.

Hibye가 풀어서 AC (+22)

 

E. Easily Distinguishable Triangles

 

관찰을 통해 상하와 좌우는 완전히 독립된 상황임을 알 수 있다.

따라서 상하나 좌우 각각에 대해 경우의 수를 구하고 둘을 곱하면 답을 알 수 있다.

 

상하 연속하게 x개의 '?'가 있다고 하자.

그렇다면 위아래에 둘 다 검은색이 있다면, 이들을 채우는 것은 불가능하고

위아래 중 한쪽에만 검은색이 있다면 이들은 반드시 위에서 아래로, 혹은 아래에서 위쪽으로 색칠되어야 하고

위아래가 둘다 흰색이라면, 적당히 위쪽은 위쪽을 바라보고, 적당히 아래는 아래쪽을 바라보도록 색칠된다.

-> 따라서 첫 경우는 *0, 둘째 경우는 *1, 셋째경우는 방향이 바뀔 후보가 x + 1개이니  *(x + 1)을 해주면 된다.

Hibye도 비슷하게 알아서 잘 푼 것 같다. (+42)

 

M. Mex and Cards

 

cnt[0], cnt[1], cnt[2]...가 주어진다.

Min(cnt[0]) + Min(cnt[0], cnt[1]) + Min(cnt[0], cnt[1], cnt[2]) + ...를 구하면 된다.

이때 쿼리로 들어오는 값들은 cnt[i]의 값들을 +-1 씩 바꾼다.

 

cnt[i]의 값이 바뀐다면 적당한 범위 [i, j]의 min값만이 바뀌게 된다.

따라서 이분탐색으로 위의 조건을 만족하는 j를 구하면 된다.

처음에 segtree를 짜다가 -> set만으로 될 줄 알고 갈아 엎었다가 -> 다시 segtree를 짜느라 시간이 조금 걸렸다.

내가 풀었으니 AC(+60)인데 마지막으로 풀었던게 N이므로 이딴 문제에 50분이나 소모한 것이다.

 

B. Bricks in the Wall

 

업솔빙을 할 때는 그냥 직관적인 풀이로 했다.

아마도 정해는 적당히 순서대로 하면 너무 많은 계산을 할 필요가 없는 해일 것이다.

나는 그냥 multiset에 모든 vertical, horizontal을 다 박아두고 

어떤 [i][L] ~ [i][R]이 비어있으면, 얘랑 겹치는 vertical을 set에서 제거해주고

1) vertical이 든 set을 이용해서 안 겹치는 애들 중 최댓값을 구함

2) horizontal이 든 set을 이용해서 얘를 제외하고 최댓값을 구함

3) L~R을 set에서 제거하는 동안 위아래로 뻗어나갈 수 있는 최대 길이를 구함

-> 이 중에서 제일 큰 것과, 현재 horizontal block의 크기의 합의 최댓값을 답으로 구했다.

 

사실상 위의 풀이에서 1, 2 때문에 set을 쓴건데 이거도 전처리를 잘 해두면 O(1)으로 할 수 있다.

따라서 정해는 O(nm), 돌려보니 O(nmlog)도 잘 돌아간다.

내가 M에, 준서가 F에 끙끙댈 동안 Hibye가 이걸 풀었다. WA(+70), AC(+74)

 

F. Focusing on costs

 

준서가 어떻게 했다. WA(+80, +82), AC(+109)

대충 풀이는 atan - cos, atan - sin을 적용시키면 a / b가 적당하게 바뀐다는 관찰로 하면 된다.

그래서 잘 반복하다보면 답이 나온다.

 

K. K-Shaped Figures

 

내가 처음 읽은 문제인데 보자마자 풀기 싫어서 넘어갔었다.

이때 나는 한창 I번 풀이 가닥을 잡아서 I에 시간을 박고 있었다.

아무튼 성현이에게 넘겼더니 알아서 AC(+123)를 받아오더라

 

I. IQ game

 

M을 풀고나서 사실상 모든 시간을 이 문제에 박았다. (AC +288)

가닥은 꽤 빠르게 잡았는데 디테일에도, 풀이에도 문제가 있어서 시간이 좀 오래 걸렸다.

 

우선 Hyperblitz로 가는 지역부터 반시계 방향으로 area[0], area[1], ... area[k - 1]이라고 부르자.

area[0]에 1번 화살표가 가면 바로 hyperblitz를 풀게 된다.

area[0], area[1]에 2번 화살표가 가면 hyperblitz를 풀게 된다.

area[0], area[1], area[2]에 3번 화살표가 가면 hyperblitz를 풀게 된다.

 

따라서 area[i]에 화살표가 간 횟수를 a[i]라고 한다면, for all j, area[0] + area[1] + ... + area[j] <= j + 1

이때 이러한 일, 즉 (a[0], a[1], ... a[k - 1])이 일어날 확률은

-> (area[0]번 지역부터 area[k - 1]번 지역을 가는 순서의 개수) * ( area[0]^a[0] * area[1]^a[1] * ... ) / (n^(sum of a)) 가 된다.

마지막으로 가는 지역이 area[x]라면, 지역을 가는 순서의 개수는

(a[0] + a[1] + .. + a[k - 1] - 1)! / a[0]! / a[1]! ... / a[x - 1]! / (a[x] - 1)! / ... / a[k - 1]!이 된다.

그러면 이제 답을 구할 때는 위의 확률에 간단하게 sum of a를 곱하면 기댓값을 얻을 수 있다.

 

dp[i][j] : hyperblitz를 풀게 될 마지막 지역이 정해지지 않은 상태이며, a[0], ... a[i - 1]이 정해져 있고 현재까지 a의 합은 j

-> dp[i][j]에는 합이 j인 모든 (a[0], .. .a[i - 1])에 대해서 (area[0]^a[0] * .. ) * 1/a[0]! 1/a[1]! ... 이 더해져 있다.

-> 이제 area[i]를 a[i]번 화살표가 간다면 단순하게 area[i] ^ a[i] / a[i]!을 곱해주면 된다.

만일 현재 지역인 i번째 지역이 마지막으로 가는 지역이라면

area[i] ^ a[i] / (a[i])!이 아니라 (a[i] - 1)!을 곱해주어야 하므로, 이 값을 final[i + 1][j + a[i]]에 더해주자.

 

final[i][j] : hyperblitz를 풀게 될 마지막 지역이 정해진 상태이며 a[0], ... a[i - 1]이 정해져 있고 현재까지 a의 합은 j

-> 전이시킬 때는 단순하게 아까처럼 area[i] ^ a[i] * 1 / a[i]!을 곱해주면 된다.

 

이래놓고 맨 마지막에 final[k][i] * (i - 1)! / n^(i)를 다 더하면 답을 얻을 수 있다.

 

------여기까지가 대회 중에 푼 문제들 (팀원이든 나든)

 

D. Dice Grid

 

맨 처음에 (-1, -1, -1, -1, -1, -1) 주사위가 있었다고 생각하자.

그렇다면 이 주사위를 판 위에서 굴리면서 -1이었던 면들을 적당한 숫자로 바꾸어준다고 상상하자.

예를 들어 (i, j) -> (i + 1, j)로 가고 싶다면, 

1) 앞면에는 -1이 있고 c[i + 1][j]로 바꾸어준다

2) 앞면에 이미 c[i + 1][j] 인 두 가지 경우로 요약이 된다.

그러면 맨 마지막에 (n, n)에 도달한 다음에는 적당히 여러 종류의 주사위들이 있을 것이다.

 

다만 문제에서는 맨 처음의 주사위 형태를 물어보므로 다시 이 주사위들이 맨 처음에는 어떤 상태였는지 맞춰주면 된다.

 

G. Greatest common divisor

 

N = 200000이더라도 실제로 값이 같은 쌍이 많지 않다.

따라서 어떻게든 gcd(x, y) = div_gcd(x, y)가 되는 쌍들을 모두 구해주기만 하면 된다.

이때 div_gcd(x, y) = div_gcd(y, x / y)로 표현할 수 있다.

이때 y * x/y <= x <= n이므로 (y, x / y) 쌍의 개수는 nlgn 미만이다.

따라서 모든 (y, x / y) 쌍에 대해서 확인하면서 가능한 것 같으면 (x, y)를 복구해주면 된다.

 

J. Joking?

 

제일 먼저 떠올릴 만한 전략은 적당히 순서대로 넣는 것이다.

-> 즉 예를 들어 {1, 2, 3, 4, 5}순대로 숫자를 넣어주고, {5, 4, 3, 2, 1} 순서대로 숫자를 넣어주는 것을 반복하는 것이다.

-> 사실 k = 120이면 위와 같은 전략만으로도 n = 2, 3, 4가 뚫린다.

 

따라서 n = 5일 때가 관건이다.

-> 꼭 {1, 2, 3, 4, 5}가 아니라 다른 랜덤한 순서인 {2, 1, 3, 4, 5}, {5, 4, 3, 1, 2}를 넣어도 괜찮음을 알 수 있다.

따라서 이제 k / 2번 랜덤하게 {1, 2, 3, 4, 5}의 순열을 만들어서 순서대로 넣어주면 된다.

-> 사실 이 설계법이 너무 강해서 그냥 이대로 제출해도 AC를 받을 것이다.

 

혹시라도 N = 5인 테케가 100개 들어 있을 걸 걱정하면 이제는 만든 a를 평가하는 것이 더 관건이 된다.

각각 n ^ k번을 전부 해보는 것은 너무 느리다.

따라서 더 빠른 방법으로 특정 permuation이 몇 번 나왔는지 세주면 된다.

-> 여기서 이제 dp를 하면 된다. 

-> dp[i][j] : permutation의 i번째 원소는 주사위에서 a[i][j]가 나온 경우의 수

-> dp[i + 1][j] = (dp[i][0] + dp[i][1] + ... dp[i][x]) (단, a[i][x] < a[i][j] < a[i][x + 1])