Atcoder Regular Contest 171
https://atcoder.jp/contests/arc171/tasks
일단 패널티 때문에 조금 조짐 (10틀 = 50분+)
A, B도 조금 마음에 안 들었지만, 못 푼 E가 흥미로워 보이니 진행
A. No Attacking
최적의 배치에 대해서 조금 고민해보면 된다.
아래의 방식으로 최적 숫자를 고민하지는 않았지만, 설명을 편의를 위해 아래와 같이 설명한다
우선 N * N 판에 폰을 놓는 것을 생각해보자.
그렇다면 홀수 X좌표를 가진 칸에만 배치하면 된다. 즉 N개씩 (N + 1) / 2줄을 배치할 수 있다.
이제 앞으로 룩을 배치하자. 단, 최대한 제거해야 하는 폰을 최소로.
즉, 처음에는 (2, 1)에, 다음에는 (4, 2)에... 로 순서대로 (2K, K)에 배치하면 된다.
그 다음에는 (1, N/2 + 1), (3, N/2 + 3), ... 순서대로 배치하는 생각을 하면 된다
그러면 적당히 A에 따른 최대 B 값을 구할 수 있다.
B. Chmax
모든 i에 대해서 A[i] >= i 가 성립하여야 한다. 이게 성립하지 않으면 일단 불가능하다.
우선 적당히 P[x]가 정해진 x들이 있다.
예를들어서 P[a] = P[b] = P[c] = P[d] = d라고 한다면, P[a] = b, P[b] = c, P[c] = d로 정해진다.
그러면 P[d]와 같이 끝에 있는 애들만 결정해주면 된다. 이런 a, d 쌍을 (L, R)이라 하자
그러면 R 크기순으로 (L1, R1), (L2, R2), ...를 정렬했다면,
답 = (R1 이하의 L값들) * (R2 이하의 L값들 - 1) * (R3 이하의 L값들 - 2) * ... 로 구할 수 있다.
C. Swap on Tree
우선은 대충 각 점 i에 대해서, i와 이웃한 간선 간의 순서만 중요함을 알 수 있다. (증명 에디토리얼 참고)
Tree dp를 하자.
cnt[i][0] = i부터의 subtree에 대해 i와 부모를 잇는 노드를 사용하는 경우의 수
cnt[i][1] = i부터의 subtree에 대해서 i와 부모를 잇는 노드를 사용하지 않는 경우
그러면 cnt[i][1]를 계산할 때에는 다음과 같다
-> \(\sum_{S\subset {childs}}{(|S|)! *\prod_{p\in S}{cnt[p][0]}\prod_{q\notin S}{cnt[q][1]}}\)
cnt[i][0]를 계산할 때에는 다음과 같다.
이 경우에는 child들과 연결된 간선 뿐만 아니라, 부모와 연결된 간선도 순서에 고려해주어야 하기 때문이다
-> \(\sum_{S\subset {childs}}{(|S| + 1)! *\prod_{p\in S}{cnt[p][0]}\prod_{q\notin S}{cnt[q][1]}}\)
이때 모든 subset에 대해서 따로 계산해줄 필요는 없다.
결국 |S|가 같다면 어차피 곱해지는 숫자가 똑같다.
sum[x] = (child 중 부모와 잇는 노드를 사용하는 횟수가 x인 경우에 대해 뒤쪽 \(\prod\)값의 합)
그러면 모든 child에 대해서 앞에서부터 순서대로
-> nxt_sum[x + 1] += sum[x] * cnt[child][0]
-> nxt_sum[x] += sum[x] * cnt[child[1]
위의 과정을 모든 child에 대해 돌리면 우리가 원하는 sum 값이 완성된다.
D. Rolling Hash
우선 x[i] = y[i] * B^i 를 만족하는 적당한 y가 존재한다
따라서 그냥 hash(X) = y[1] + .. y[N]이랑 다를게 없다.
그러면 A[L] + A[L + 1] + ... + A[R] = 0을 만족하지 않게 하는건, 적당히 presum[R + 1] - presum[L] != 0인 것이다
따라서 presum[0]부터 presum[N]까지, M개의 조건을 만족하도록 P - 1개의 숫자를 부여해주면 된다.
그냥 백트래킹하면 시간 내에 잘 돈다. (1ms에 도는 것을 보면 막는게 거의 불가능해 보인다)
이것 외에도 dp[S] = (S를 칠하는데 필요한 최소 색의 수)를 계산하면 된다.
-> dp[S] = Min(dp[T] + dp[S - T])가 된다. (단, T는 S의 subset)
모든 (S, T) 쌍의 개수는 3^N이니 잘 돈다
E. Rookhopper's Tour
Rookhopper tour를 조금만 생각해봐도 가로 -> 세로 -> 가로 -> 세로... 혹은 세로 -> 가로 -> 세로 -> 가로 임을 알 수 있다.
이때 돌의 움직임을 생각하면 (x, y) -> (x + p, y) -> (x + p, y + q) 등으로 이동할텐데, (p, q는 양수라 가정)
그렇다면 (x + p - 1, y)와 (x + p, y + q - 1)에 흰 돌이 있다는 뜻이고, 인접한 두 행을 소모하게 된다
즉, 연속해서 이웃한 행들과 열들을 소모하는 과정으로 흑돌의 움직임을 대응할 수 있다.
그 다음은? 적당히 수학?