Codeforces Round #851 (Div. 2)
https://codeforces.com/contest/1788
감을 다 잃었는지 진짜 오래걸렸다.
A는 2의 개수가 아니라 직접 곱하고 있었고
B는 TLE가 안생긴다는 것을 굳이 확인했고
C는 construction 감다뒤
D는 답에 mod 1e9 + 7 처리를 안하고 있었고
E는 segtree 안쓰고 풀겠다고 + psum의 최소값이 음수임을 간과해서 오래걸렸다.
F도 find함수를 쓰고 나서야 올바른 val 값이 있다는 것을 간과해서 여러번 틀렸다.
A. One and Two
a의 값은 1이나 2이다.
따라서 a1 * .... * ak는 이중에서 2의 개수와 대응시킬 수 있다.
n = 1000으로 만만하므로 그냥 모든 k에 대해서 O(n)으로 각각 판단해주면 된다.
B. Sum of Two Numbers
x + y = n이다.
출제자 왈, x와 y를 bruteforce로 찾는게 countertest가 있다고 한다.
하지만 중복되는 입력에 대한 안전장치만 해두면 30ms로 가볍게 통과한다.
실제로 ~1e9의 숫자들 중에서 ((n+1)/2, (n-1)/2)부터 bruteforce하였을 때 상위 1e4개는 필요한 계산이 3e6번 밖에 안된다.
즉, 물론 99999999등의 숫자를 박으면 혼자서 1e4번 계산이 필요하지만 이런 서로다른 경우가 1e4개 존재하지 않는다.
의도대로였다면 그냥 n을 string으로 주거나 n <= 1e18로 하는게 나았을 것이다.
C. Matching Numbers
사실 {a1 + b1, a2 + b2 ... } = {i, i + 1, ..., i + n}이 되기에
간단한 계산으로 i = (3n + 1) / 2가 됨을 알 수 있다.
솔직하게 근데 이 값을 아는게 construction에 크게 도움이 되지 않는다.
아무튼 직관은 (1, x), (2, x + 1) ... (j, x + j)로 연결을 시키면 하나의 기우성이 대충 차고,
그 이후로는 (j + 1, j + 1 + y), (j + 2, j + 2 + y)...로 연결을 시키면 다른 기우성이 꽉 찰 거라는 것이다.
그래서 해보면 x = (3n + 1)/2, j = (n + 1)/2, y = n / 2를 대입시키면 이게 된다.
D. Moving Dots
어떤 점은 반드시 최초로 만나는 두 개의 점이 존재하며, 그 두 점의 위치에 의해 결정이 된다.
어떤 점이 a[i]와 a[j]가 만나서 생긴다고 가정하자.
그러면 당연하게도 [2a[i] - a[j], 2a[j] - a[i]) 범위에는 다른 점이 있어서는 안된다.
간단한 이분 탐색으로 (뭐 투포인터 느낌도 아마 될 것이다) 범위 외의 점의 개수 cnt를 구할 수 있다.
그러면 2^cnt 종류의 subset에서 특정 점이 생기는 것이므로 이것을 모두 합해주면 된다.
E. Sum Over Zero
간단한 DP
일단 prefix sum으로 psum[i] = [0, i)의 합 을 만들어두자.
그러면 문제의 조건 a_x + ... + a_y = psum[y + 1] - psum[x]이다.
그냥 애초에 segment를 [L, R) = [x, y + 1)이라고 여기고 y - x + 1은 R - L이라고 여기자.
띠라서 dp식은 dp[R] = max(dp[R - 1], dp[L] - L + R) (단, psum[R] - psum[L] >= 0) 이다.
이것을 psum[i] = x라면 x에 dp[i] - i 값들의 최댓값을 가진 segment tree로 간단하게 해결할 수 있다.
(psum 값이 본인 이하인 값들 중에서 dp[L] - L의 최댓값에 자신의 번호인 R를 더해주면 된다.)
하나 발견할 수 있는게 있다.
psum[i] <= psum[j] 이고 dp[i] - i >= dp[j] - j인 i, j 순서쌍이 있다고 가정하자.
그렇다면 어떤 dp[k]를 계산해줄 때 굳이 i를 마다하고 j를 선택할 이유가 없다.
따라서 하나의 set에 {psum[i], dp[i] - i}값들을 모두 넣어주고 monotonicity가 맞도록 관리해주면 된다.
그러면 psum값이 나보다 작은 애들 중에서 psum값이 제일 큰 애가 dp[L] - L값도 가장 크다.
dp[R] = prev(lower_bound({psum[R] + 1, -1e18}) -> second + R따위로 해도 올바른 답을 얻을 수 있다.
F. XOR, Tree and Queries
ans[u] = (1번 노드부터 u번 노드까지의 경로를 모두 XOR하여 나온 값)
조건인 [u, v, x]가 들어왔다고 가정하자.
루트를 1번 노드라고 했을 때 w = LCA(u, v)라면
x = (ans[u] ^ ans[w]) ^ (ans[v] ^ ans[w]) = ans[u] ^ ans[v]로, w와 관계없이 u, v와만 관계있음을 알 수 있다.
따라서 [u, v, x] 조건이 들어오면 union-find에서 이 둘을 merge해주고 parent에 대한 XOR값을 val에 저장해둔다.
예를 들어 find(i) = j 라면 ans[j] = ans[i] ^ val[j]가 될 수 있도록 val 값을 설정하자는 것이다.
만일 find(u) == find(v)면 val[u] ^ val[v]가 x랑 같은지 확인해서 간단하게 가능한지 불가능한지 확인해줄 수 있다.
가능성의 판단은 위에서 끝난다.
이제 a1 ^ a2 ^ ... ^ a[n - 1]이 최소가 되도록 find(i) = i인 i들의 ans 값들을 설정해주면 된다.
(다만, 1번 노드는 트리의 루트라고 하였기 때문에 ans[1]은 무조건 0이어야 함에 유의)
a1이 (u, v)를 이어주는 edge라면 a1 = ans[u] ^ ans[v] = val[u] ^ val[v] ^ val[find(u)] ^ val[find(v)]의 값을 가진다.
따라서 간단하게 a1 ^ a2 ^ ... ^ a[n - 1]에서 ans[i]가 각각 몇 번 등장하는지 체크해준다.
ans[i]들 중에서 홀수 번 등장하는 애들을 b1, b2... bm이라고 한다면
a1 ^ ... ^ a[n - 1] = b1 ^ b2 ^ ... ^ bm ^ (val 값들을 XOR해준 값 = tot)이 된다.
만일 b1... bm 중에 ans[1]이 아닌게 존재한다면 그 값에 tot를 부여하면 a1 ^ .. ^ a[n - 1]은 최솟값이 된다.
풀이로 설명하려니 엄청 복잡해 보이는데 그냥 간단하게 union find로 0, 1을 색칠하는거랑 크게 다를게 없는 문제다.