Codeforces Round 929 (Div. 3)

처음으로 Codeforces 후기를 남긴다. 그린을 넘어 민트로 향한 지 꽤 됐는데 지금에서야 후기를 남기는 이유는 D번 때문이다.

solved.ac 디스코드에서 소위 답 맞춰보기를 하는데 나만 풀이방식이 달라서 핵 당해서 터질까 염려되었는데, 결국에는 옳다는 게 증명되는 바람에 한 숨 돌릴 수 있었던 것.

5문제, 227분의 페널티로 전체 2572등으로 마무리하였다. 아직 오픈핵 진행 중이라 레이팅이나 등수가 변동할 수는 있겠는데, 그 때 맞춰서 업데이트 해 보도록 하겠다.

UPD) 참가 대상 중 1827등을 거두었다.

Contest Submissions

반성할 점

B를 풀 때 머리로 풀려다가 WA 하나를 적립한 점. 심지어 바로 옆에 종이도 있었는데 천천히 머리를 식힐 생각을 하지 않고 무작정 이러면 되겠지 식으로 풀어서 결과적으로 시간도 낭비하고 틀리지 않았어야 할 곳에서 틀렸다.

그리고 E를 짤 때 차분하지 않은 상태에서 짠 것. 평정심 없이 급하게 짜다 보니 예제도 안 나오는 상황에 맞닥트렸고, 심지어 변수 이름마저 잘못 쓴 케이스도 잡지 못한 채 한참동안 헤메었다.

마지막으로 D를 풀 때 증명되지 않은 풀이를 마구잡이로 사용한 것. 옳은 풀이였어서 다행이지, 그렇지 않았다면 맞왜틀을 외치며 페널티를 적립하거나 천운을 타고 통과했더라도 핵당해서 틀리게 되었을 것이다.

 

조금만 더 잘 했으면 블루까지 더 빠르게 갈 수 있었는데, 오히려 블루 가기 전에 이런 반성할 점을 발견한 것만으로도 충분히 좋은 성과라고 생각한다. 게다가 그러면서 레이팅까지 챙겼으니 금상첨화라.

 

0:01 A AC

def solve():
    N = int(input())
    print(sum(map(lambda x: abs(int(x)),input().split())))
for _ in range(int(input())): solve()

그냥 음수를 한 쪽에 몰아넣은 다음에 그 쪽 부분만 부호를 반전시켜 주면 최대로 만들 수 있다. 그냥 모든 원소에 절댓값 씌워서 더해 주면 바로 맞을 수 있다.

 

0:20 B AC (+1)

def solve():
    N = int(input())
    l = list(map(int,input().split()))
    a = [0,0]
    for i in l:
        if i%3 == 1: a[0] += 1
        elif i%3 == 2: a[1] += 1
    if a[0]%3 == a[1]%3: return 0
    if a[0] == 0: return a[1]%3
    if a[1] == 0: return min(1,a[0]%3)
    else: return 1
for _ in range(int(input())): print(solve())

3의 배수는 존재 유무가 답에 전혀 영향을 끼치지 않는다. 3으로 나눈 나머지만 관리하여도 충분하고, 1의 수와 2의 수가 답에 직접적인 영향을 미친다.

1과 2가 같은 수만큼 존재할 경우 1+2로 상쇄된다. 그렇지 않을 경우 1과 2를 3으로 나눈 나머지로 관리해 줘야 하는데, 각 케이스마다 종이에 써 가면서 합이 3의 배수가 되도록 몇 번의 연산으로 가능한지 체크해 주면 된다. 

2가 두 개일 때만 1이 3N개 있느냐 아예 없느냐로 답이 갈리는데, 이는 1이 3N개 있으면 1을 하나 지워서 2 두 개를 1+2로 곧 3의 배수로 만들 수 있기 때문이다. 케이스워크 잘 해 주면 된다.

 

0:27 C AC

from sys import stdin
input = stdin.readline
def solve():
    a,b,l = map(int,input().split())
    ans = set()
    for i in range(20):
        for j in range(20):
            if l%((a**i)*(b**j)) == 0: ans.add((a**i)*(b**j))
    print(len(ans))
for _ in range(int(input())): solve()

정말 이래도 되나 싶은 브루트 포스 문제. 시간제한이 5초라는 걸 못 보고 이런저런 정수론적 지식을 이용하려고 했으나, \(l\le10^6\)이라는 조건을 뒤늦게 캐치하고 브루트 포스로 노선을 틀었다.

\(2\le a,b\le 100\)이므로 \(a^x\mid l\)일 수 있는 \(x\)는 커 봐야 19이다. \(2^{20}=1\,048\,576\)으로 백만을 넘어간다. 나눠지는지를 집합에 저장하고 그 길이만 세 주면 상수가 좀 크더라도 쿼리당 \(\mathcal O(1)\)에 풀 수 있다. 시간제한이 5초라서 별도의 상수커팅 없이도 AC를 따 내기에는 충분하다.

 

1:29 D AC (+2)

from math import gcd
from sys import stdin
input = stdin.readline
def solve():
    N = int(input())
    l = list(map(int,input().split()))
    if N == 2:
        print('YES' if l[0]!=l[1] else 'NO')
    else:
        g = gcd(*l)
        l = [i//g for i in l]
        cnt = sum(1 for i in l if i==1)
        if cnt > 1: print('NO'); return
        else: print('YES')
for _ in range(int(input())): solve()

이게 대망의 그 문제다. 사풀로 뚫었다고 생각했지만 실제로는 정해였던 풀이. 반성은 반성 나름이고 맞힌 건 맞힌 거다.

\(N=2\)일 때는 같지만 않으면 반드시 \(a<b\)일 시 \(a\bmod b=a\)가 되므로 0을 피할 수 있다. 이 케이스는 간단하니 미리 처리해 주자. 그렇지 않다면, 전부 \(\gcd\)로 나눠 주자. \(a_1\bmod a_2\bmod \cdots \bmod a_N=0\)임과 \(ga_1\bmod ga_2\bmod \cdots \bmod ga_N=0\)은 동치이기 때문이다.

그 다음 배열을 순회하며 1의 갯수를 체크한다. 만약 1이 2개 이상이면 앞에 어떤 수가 와도 반드시 0이 되는 \(\bmod 1\)을 피할 수가 없다. 그러므로 답은 NO. 만약 그렇지 않다면 답은 반드시 YES다.

왜 그럴까? 배열이 \(a_1\le a_2\le \cdots \le a_N\)을 원소로 가진다고 하자. 1이 1개라면 \(1<a_2,a_3,\cdots,a_N\)이므로 \(a_1\bmod a_2\cdots\bmod a_N=1\ne0\)이다.

그렇지 않다면, 곧 1이 0개라면 우선 \(\gcd\)로 나눠 주었기 때문에 배열의 모든 원소의 최대공약수는 반드시 1이다. 그렇다면 \(a_1\not\mid a_i\)인 \(i\)가 반드시 존재하게 된다. \(a_i\bmod a_1\)은 0이 아니고, \(\bmod\)의 정의 상 \(a_1\)보다 작아야 한다. 위에서 \(a<b\)일 시 \(a\bmod b=a\)라고 명시한 바 있다. 따라서 \(a_i\bmod a_1=a_i\bmod a_1\bmod a_2\cdots\bmod a_{i-1}\bmod a_{i+1}\cdots\bmod a_N\)이 성립하고, 이 값은 0이 아니다.

따라서 수열을 적당히 재배열해 \(b_1\bmod b_2\bmod\cdots\bmod b_N\ne0\)이도록 만들 수 있다.

 

1:00 E AC

from bisect import bisect_left
from sys import stdin
input = stdin.readline
def solve():
    N = int(input()); answer = []
    array = list(map(int,input().split()))
    prefix = [0]
    for i in range(N): prefix.append(prefix[-1]+array[i])
    for _ in range(int(input())):
        l,u = map(int,input().split());
        left = l
        r = N
        while r-l > 1:
            mid = (l+r)//2
            t = prefix[mid]-prefix[left-1]-u
            if t < 0: l = mid
            elif t > 0: r = mid
            else: answer.append(mid); break
        else:
            ll = prefix[l]-prefix[left-1]-u
            rr = prefix[r]-prefix[left-1]-u
            if abs(ll)<abs(rr): answer.append(l)
            else: answer.append(r)
    print(*answer)
for _ in range(int(input())): solve()

문제에서 쿼리마다 구해 줘야 하는 값은 다음 식이 최소가 되게 하는 \(l\le r\le n\)이다.

\[\sum_{j=1}^{\sum_{i=1}^ra_i}(u+1-j)\]

이 값은 \(u\)와 \(\sum_{i=1}^ra_i\)가 가까울수록 커지고 멀수록 작아진다. 지문이 어지러웠던 원본 문제는 이제 부분합을 \(u\)와 가장 가깝게, 적어도 \(\mathcal O(\log n)\)의 시간 내에 구해야 하는 문제로 바뀐다.

왼쪽 끝이 고정되어 있으니 이분탐색을 생각해 볼 만 하다. 부분합이 정확하게 \(u\)와 같다면 미리 반복문을 빠져나가고, 그렇지 않다면 어느 쪽의 부분합이 \(u\)와 더 가까운지 사후에 검사해 주면 된다.