2022 ICPC Asia Taiwan Online Programming Contest

https://codeforces.com/gym/103990

오랜만에 셋을 풀려는데 OReO가 이미 소모한 셋 중에서 해봤다.

오전 8시 12분부터 3시간 동안 알차게 수업시간을 유기했다.

 

셋이 열리자마자 A를 읽었는데 palindrome이 뭐 떠오르는게 없어서 거의 즉시 버렸다.

 

B를 읽고 잠시 생각하다가 빠르게 풀이를 떠올렸다. 

sum(i * a[i])와 sum(a[i])를 구할 수 있는 lazy segtree를 만들어주면 아주 간단하게 풀 수 있다.

오랜만에 그렇게까지 정석적이지는 않은 lazy seg의 구현이였어서 생각보다 오래 걸렸다.

Lazy segtree를 열심히 짜고 제출 했는데 WA (+19분)

 

C가 많이 풀려있길래 읽고 AC (+20분)

F가 많이 풀려있길래 읽고 AC (+27분)

-> 문제가 좀 길어서인지 꼼꼼히 읽다가 오래걸렸다. 게다가 long double로 할 부분을 int로 해서 디버깅 시간 소모됨

 

H가 많이 풀려있길래 봤다.

단순하게 문제의 입력으로 주어지는 N보다 pow(6, x)가 더 큰 최소의 x를 구해주면 된다.

N의 범위가 말도 안되게 크기도 하고, 얼마전 구데기컵에서 파이썬에 크기 제한이 있다한 걸 봤기에 C++로 했다.

음... FFT를 들고와서 구현해서 AC. (+38분)

그냥 파이썬을 박아볼걸 그랬다. 

 

이제 이쯤하고 다시 B로 돌아왔다.

알고보니 근데 segtree 구현 이슈로 3번 더 WA를 받았다. (+54분, +55분, +58분)

분명 구현은 틀리지 않았는데...를 되뇌이며 어떤 문제가 많이 풀렸는지 다시 살피러 갔다.

 

G가 많이 풀려있어서 접근했다.

어떤 구간 [L, R]의 프로그램들을 재생한다고 하자.

그러면 여기에 있는 프로그램들을 모두 pq에 넣고 제일 많은 코인을 주는 프로그램을 M - (이동)번 고르면 된다.

단, 이동횟수를 셀 때 맨 처음에 1번 프로그램에서 L로 먼저 갈 수 도 있고, R로 먼저 갈 수도 있음에 주의.

본인은 구현의 방법으로 인해서 위의 주의사항을 고려했다고 생각했는데, 알고보니 따지지 않아서 WA를 받았다.

여기서 WA를 4번 받고 (+80분, 81분, +83분, +89분) 겨우 AC를 받았다. (+91분)

 

이제 또다시 B로 왔다.

무엇을 고려하지 않았는지 대충 깨달았다.

1) [L, R)을 모두 0으로 바꿔버리는 쿼리를 만들었는데 이것의 구현이 잘못됨

2) sum(i * a[i])를 단순히 들고오면 안되고 sum( (i - L) * a[i] )를 가져와야 함

-> 이 두 개를 틀렸었다.

1번 더 WA를 받고 (+95분), AC를 받았다. (+97분)

 

D가 사실 중간에 G를 풀기 전에 읽었었는데 각도가 나오는게 마음에 들지 않아서 넘겼었다.

하지만 생각보다 쉬운 문제이다.

우선 d[i] = 0인 점을 통해서 루트는 아주 쉽게 구할 수 있다. (편의상 0이 루트라 하자)

그러면 set에 0, n을 넣어두자.

d값이 작은 순서대로 숫자들을 보았을 때 set에 있는 자기보다 작은 애를 L, 큰 애를 R이라고 하자.

만일 d[L] + 1 = d[cur]이면 L과 그게 아니고 d[R] + 1 = d[cur]이면 R과 연결시켜주면 된다.

동일한 d값을 가진 cur이 여러 개가 같은 (L, R)에 있을 수 있는데 이건 그냥 일괄적으로 L, R과 연결해주면 별 문제 없다.

생각보다 빠르게 AC (+111분)

 

이제 E를 잡았다.

문제에서 주어진 숫자가 c라고 하자. (문제에선 x, y, k지만 혼자 끄적일 때 a, b, c로 했기 때문)

그리고 y = (q / p) * c로 표현할 수 있다. (단, p와 q는 서로소이고 q > p)

그러면 x = (q / (2q - p)) * c임을 알 수 있다.

문제에서 x + y를 최소화 해야 하므로 q / p를 최소로 만들어주는 p, q를 잘 고르면 된다.

위의 식에서 gcd(p, 2q - p) = 1 or 2이며, p와 2q - p는 기우성이 같은 c의 약수이다.

따라서 그냥 c의 모든 약수들을 구하고(폴라드 로) 그 다음 짝수와 홀수 약수들을 분리하자.

-> 짝수 두개를 고르는 행위는 홀수 두 개로 바꿀 수 있다고 착각하여 여러 번 틀렸다. WA(+131분, +138분, +139분)

이후 각각을 정렬한 다음에, 인접한 애들 두 개를 d[i] = p, d[i + 1] = 2q - p를 대입해보자.

이 들 중에서 q / p가 제일 작게 되는 p, q를 구하면 답을 구할 수 있다.

1) __int128_t를 출력해야 하기 때문에 만약에 ICPC에 나왔다면 상당히 귀찮았을 것이다. 

2) k의 최댓값인 4e18에서는 잘 굴러가는데 다른 숫자에서 long long이 overflow 될 수 있다.

3) q / p의 최솟값을 구할 때, 이 값이 1e18보다 클 수 있음에 유의해야 한다. 초기값을 1e18로 설정하면 틀린다. 

2번 더 틀리고 (+156분, +157분), 드디어 답을 얻었다. (+160분)

 

남은 시간 동안 I를 고민하다가 마쳤다. (차라리 A를 볼 걸 그랬나?)

코포에서 Dashboard을 보는게 안 좋은건가 하는 생각이 들기도 한다.

사실 어차피 5등정도 까지는 설카가 해줄텐데 괜찮은가 싶기도 하고...

위의 WA 목록을 보면 1, 2분마다 제출하여 수많은 패널티를 쌓았음이 확인된다.

아니 애초에 무언가를 고쳤는데 계속 WA를 받았다는 뜻은 처음 코드가 3곳 이상에서 틀렸다는 뜻이니 슬프다.

구현은 남에게 맡길 수 있으면 좋겠다.

 

I를 고민할 때 생각한 풀이인 아주 오래걸리는 풀이는 아래와 같다.

Combination에서 제일 숫자가 작은 Leader을 i번이라고 하자.

그렇다면 i + 1번 ~ n번 leader들의 L값과 R값을 정렬하자.

1) 만일 현재 값이 L[x]라면 : x가 포함된 combination들인 2^(현재 참여가능한 리더의 수)를 답에 추가 

2) 만일 현재 값이 R[x]라면 : x를 현재 참여가능한 리더의 수에서 제거

-> 모든 combination은 제일 숫자가 작은 리더와 제일 L이 큰 리더가 유일하기에 모두 딱 한 번씩만 세질 것이다.

 

조금 생각을 해보니 굳이 숫자가 작은 Leader가 아니라 그냥 L이 제일 작은 리더를 생각하는게 맞을 것 같다.

또 생각해보니 동시에 모든 리더들이 제일 작은 리더인 상황을 고려할 수 있다.

-> x가 추가되는 상황에서 현재 총 참여 가능한 리더가 y명이면, 그냥 순서대로 y - 1, ... 0명이 추가 참여가능하기에

-> 근데 여전히 0 ~ y의 수에 대해서 C(y, z)를 ans[z + 2]에 더해주어야 해서 복잡도가 O(n^3) 수준이다.

-> 수식적으로 생각해보니 이 짓은 1 + (1+x) + (1+x)^2 + ...+ (1+x)^(y - 1) = {(x+1)^(y) - 1} / x 라서 O(n^2)으로 할 수 있다.

 

해설을 보니 위의 짓을 다음과 같이 할 수 있다.

일단 우리가 구해야 하는 식은 대충 \(\sum{(x + 1)^y} = \sum\sum{C(y, i)x^i}=\sum\sum{\frac{y!}{i!(y-i)!}x^i}\) 

이 값은 \((\sum y!\space x^{y})*(\sum(\frac{1}{k!}\space x^{-k}) = \sum{\frac{y!}{k!}\space x^{y-k}}\) 로 구할 수 있다.

맨 마지막에 이제 ans[i]에 1 / (i!)을 각각 곱해주면 답이 된다.

기가 막힌다 기가 막혀

 

나는 A처럼 숫자 조건이 100인 문제가 세상에서 제일 싫다

20이나 26 정도면 2^(20)이나 문자열이겠거니 싶은데 100이면 별의별 복잡도가 다 튀어나온다.

아무튼 다음과 같은 것을 고려할 수 있다.

1) 같은 단어를 두 번 반복해서 지날 수 없다. (aa)

2) aba와 같이 중간에 다른 문자를 두고 반복해서 지날 수 없다.

-> 따라서 모든 상태를 (행) * (열) * (직전 문자) = N * M * 26 정도로 표현가능하다.

-> 생각해보면 직전 문자는 4종류 밖에 없으므로 N * M * 4이다.

이제 다익스트라 같은 거로 최대 거리를 구해주면 된다.

-> 다익스트라를 하고 난 뒤 추가 작업을 진행해줘도 되고 따로 무한히 긴 경로가 가능한지 체크해도 된다.

이러고 나면 O(T * N * M * 4 * log) 정도로 문제가 풀리고 이 정도는 시간내에 돌아갈 것이다.

이건 딱봐도 구현이 이쁘지 않아서 구현을 안해보았다.