[Atcoder] ARC133후기

https://atcoder.jp/contests/arc133

이 바보같은 과거의 내가 무조건 한다는 마인드로 rated register를 해버렸다. 이게 최근에 atcoder에 생긴 제도인데, rated register을 하면 문제를 보거나 제출하지 않아도 rated가 된다. 하는 수 없이 집에 오는 버스에서 부랴부랴 폰코딩으로 A B C를 맞았다. 집에 도착한 이후 D를 풀고 있었는데 접근은 잘 한 것 같으나 결국 풀이에는 실패했다 ㅜㅜ 그래도 점수 떡락은 면했다. 다행히 오늘 A B C는 모두 쉬웠고 구현도 쉬웠다.

 

A

길이 $n$의 수열이 주어진다. 수열에서 어떤 숫자 $x$를 골라 $x$를 모두 제거한 수열이 사전순으로 가장 크도록 하고 싶다.

 

$a_{n+1}=0$이라 두고, $1 \leq i \leq n$에 대하여 $a_i>a_{i+1}$인 가장 작은 $i$에 대해 $x=a_i$라 하면 된다.

B

두 순열 $P, Q$가 있다. 적당히 두 순열의 부분수열을 골라 순서대로 $P$의 원소였던 애가 $Q$의 원소였던 애를 나누게 하면 된다. 이런 경우 중 가장 긴 것의 길이는?

 

에라토스테네스의 체 구하듯이 각 $i$의 배수들을 모두 체크해도 $n \log{n}$밖에 안 된다. 즉 모든 가능한 매칭의 가지수가 $n \log{n}$이다. 각 $P_i$에 대해 $Q$에서 $P_i$로 나눠지는 원소들의 위치를 구하고 시작하자. 마치 LIS를 구하듯 $\displaystyle dp_i=\max_{1\leq j<i}(dp_j+1)$꼴의 점화식이 생긴다. 근데 이제 이 점화식을 적용하는 것은, 새로 매칭이 생겼을 때만이다. 인덱스를 큰 것부터 작은 순서대로 BIT나 세그로 $dp$를 업데이트해준 후 최댓값을 출력하면 된다.

 

C

$h \times w$ 격자에 $k$보다 작은 음이 아닌 정수들이 있다. 각 행/열별로 합의 $\mod k$가 주어졌을 때, 전체 격자 숫자 합의 가능한 최댓값을 구하자.

 

모든 격자에 $k-1$을 채웠다고 가정해보자. 그랬을 때 어떤 열을 $k$로 나눈 나머지는 $-w \mod k$다. 이 값과 해당 열의 실제 $\mod k$값을 비교하면 그 열에서 얼마나 빼야 하는지 알 수 있다. 이 결과를 열에 대해 다 더하고, 행에 대해 다 더하자. 생각해보면 자명하게 두 값의 $\mod k$는 같아야 한다. 그러지 않을 경우 -1을 출력. 또 생각해보면 두 수 중 max값만큼만 빼도 충분히 조건을 만족시킴을 알 수 있다. $hw(k-1)-\max(sum_{row}, sum_{column})$이 답이다.

 

 D

$L \leq l \leq r \leq R, V$에 대해 $l \oplus (l+1) \oplus \cdots \oplus r=V$인 경우의 수를 세면 된다.

 

풀지는 못했으나, 알고 보면 $1$부터 $k$를 XOR한 값은 4를 주기로 주기성을 띤다. $1, i+1, 0, i$ 이런 식으로. 이 문제는 이러한 수열에서 두 값을 XOR한 결과가 $V$인 경우를 세는 문제랑 똑같아지고, 저 $i+1$, $i$인 경우들 사이에서 골라져 $V$가 되는 경우의 수를 구하는 것이 어렵다. 이것을 해결하지 못해 못 풀었다.

 

참 말도 안 되는 이유로 열심히 폰코딩 했는데, 다행히 떡락은 면했다. 다음주에 있을 ARC에서는 꼭 레이팅 상승해야지.