[DOJ] Beginner Contest DOJ 1 버츄얼 후기

sovedac 디스코드에서 고수분들의 DOJ KOI 2nd Round Mock 1 후기를 읽어보면서 DOJ라는 사이트를 알게되었습니다. 뭔가뭔가 궁금해서 가입해보고 디스코드도 들어가보니까 이런 공지가 있었습니다.

DOJ대회 (버츄얼 포함)으로 후기를 적으면 추첨으로 햄버거를 준다고 하여서 한번 대회를 슥보니 ABC처럼 Beginner 대회가 있어서 이걸 버츄얼 돌고 후기를 적어야지라고 생각했습니다. 원래는 BCD2를 하려고 했는데 BCD카테고리에 BCD2가 없어서 버츄얼을 할 수 없는 이슈로 BCD1을 하기로 했습니다. 

BCD는 9문제(A~I)가 있고 난이도순 배열인 대회입니다. 앳코더의 ABC정도의  난이도커브를 의도했다고 합니다,

문제를 풀어봅시다.

 

B번 - 오름차순 만들기

A번은 문제를 보고 어려워보여서 스킵을 했고 B번이 더 쉬워보여서 먼저 풀었습니다. $k$가 음수일때와 양수일때를 나눠서 생각하였습니다.

 

$k$가 양수이면 $a_1 < a_2 < ... < a_N$ 을 만족시키기 위해 $a_2$부터 $a_N$까지 돌면서 $a_i$에 $\max(0,\lfloor \frac{a_{i-1}-a_i+1}{k} \rfloor)$만큼 연산을 사용하여 $a_i$를 업데이트 하면 됩니다.

 

$k$가 음수이면 오름차순을 만족시키기 위해 $a_{N-1}$부터 $a_1$까지 돌면서 $a_i$에  $\max(0,\lfloor \frac{a_{i}-a_{i+1}+1}{|k|} \rfloor)$만큼 연산을 사용하여 $a_i$를 업데이트 하면 됩니다.

 

그리고 $k$와 $a_i$의 절댓값이 크므로($10^9$) 실수연산보다 정수연산만으로 처리하게 해줬습니다.

def main():
    input=open(0).readline
    n,k=map(int,input().split())
    a=[*map(int,input().split())]
    r=0
    
    if k>0:
        for i in range(1,n):
            t=max(0,(a[i-1]-a[i]+1)//k+(((a[i-1]-a[i]+1)%k)!=0))
            r+=t
            a[i]+=k*t

    else:
        tk=-k
        for i in range(n-2,-1,-1):
            t=max(0,(a[i]-a[i+1]+1)//tk+(((a[i]-a[i+1]+1)%tk)!=0))
            r+=t
            a[i]+=k*t
      
            
    print(r)
        
        

main()

 

 

A번 - 쉬운 문자열 문제

B번을 풀고 C,D,E,F번을 읽어봤지만 모두 모르겠는 대참사가 일어나면서(F번은 해보려고 했다가 TLE먹고 안함) A번이라도 풀어야 겠다는 마음으로 A번을 다시 읽어봤습니다.

 

만약 $S$가 $KK\cdots K$ 꼴 (ex. "dadada", "aaaa") 이면 그중 가장 짧은 부분 문자열 $K(1\le |K| < |S|)$를 찾아내어 $\lceil \frac{M}{|K|} \rceil$만큼 반복후 남은 길이 $M - \lceil \frac{M}{|K|} \rceil$ 만큼 아무문자열을 붙이면 된다는 것을 알아내었습니다. $K$를 찾기위해서는 $O(N^2)$방법을 통하여 모든 가능한것에 대하여 조사해보면 됩니다.

 

만약 그런 $K$이 없다면  $\lceil \frac{M}{|S|} \rceil$만큼 반복후 남은 길이 $M - \lceil \frac{M}{|S|} \rceil$ 만큼 아무문자열을 붙이면 됩니다.

 

(중간에 코드 작성 실수로 2wa를 적립했습니다.)

def main():
    input=open(0).readline
    n,m=map(int,input().split())
    s=input().strip()
    r=""
    
    for i in range(1,n):
        if n%i!=0:continue
        for j in range(len(s)//i-1):
            if s[i*j:i*(j+1)]!=s[i*(j+1):i*(j+2)]:break
        else:
            r=s[0:i]
            t=m//len(r)
            print(r*t+"a"*(m-len(r)*t))
            break
    else:
        print(s*(m//n)+"a"*(m-n*(m//n)))

        

main()

 

 

C번 - 01 10

시간이 20분 가량 남아서 C번을 풀려고 했습니다. 뭔가 애드혹처럼 생겼어서 01이나 10은 안되고 11,00이 된다는 것에 꽂혀서 결국 풀어내지 못하였습니다. (실력이슈)

업솔빙을 통해 문제의 아이디어를 보니 이진 문자의 특성에 따라 양 끝값에 따라 인접하면서 서로 다른 문자 쌍의 개수가 짝수인지 홀수인지를 알수 있음이었습니다.

 

만약 양 끝값이 같다면 중간에 문자가 바뀌는 지점이 짝수개 이므로 최소 스왑횟수는 0입니다.

 

만약 문자열이 01또는 10이면 어떻게 해서라도 짝수개를 만들어내지 못하므로 -1을 출력하면 됩니다.

 

만약 양 끝값이 다르다면 왼쪽 끝 문자와 같은 문자를 오른쪽 끝까지 이동시키는 비용과 오른쪽 끝 문자와 같은 문자를 왼쪽 끝까지 이동시키는 비용중 최솟값을 출력하면 됩니다.

def main():
    input=open(0).readline
    n=int(input())
    s=input().strip()
    if s[0]==s[-1]:return print(0)
    elif s in ("01","10"):return print(-1)
    else:
        t=n
        if s[0]=="0":
            for i in range(n):
                if s[i]=="1":
                    t=min(t,i)
                if s[n-i-1]=="0":
                    t=min(t,i)
                
        else:
            for i in range(n):
                if s[i]=="0":
                    t=min(t,i)
                if s[n-i-1]=="1":
                    t=min(t,i)
        print(t)

main()

 

 

후기 & 느낀 점

2솔로 마무리하면서 지금까지 참가한 대회(오픈콘, 버츄얼 포함) 중 가장 적은 솔브를 기록했습니다. 백준 섭종 이후로 오프라인 대회 두 번 나간 것 말고는 PS를 거의 안했으니 어쩌면 당연한 결과일지도 모른다고 생각합니다. 그걸 알면서도 막상 결과를 보니 원래 없던 실력이 더 떨어지고 있다는 게 체감돼서 아쉬움이 크네요.

C번 업솔빙으로 풀이를 보니 양끝값만 비교하면 홀짝성이 결정된다는 게 핵심이었는데 막상 보고 나니 당황스러울 정도로 단순해서 허탈하면서도 신기했습니다. 복잡하게 생각할수록 오히려 멀어지는 게 애드혹의 묘미인 것 같습니다.

문제 자체의 퀄리티는 좋았습니다. 6월 30일에 BCD3이 열릴 예정이라는데 그때는 D번까지는 풀어보고 싶습니다. 종강하면 진짜로 CP 공부를 다시 시작해야겠다고 느꼈습니다. (6/6 수정: 2030년 6월 30일에 열린다고? 하네요???)

 

(+이것은 바람이긴 하지만 BCD 앞쪽(A or B)에 조금더 쉬운문제가 한개정도 있으면 cp초보자들도 조금더 쉽게 할 수 있을 것 같스습니다. 현재 난이도셋도 좋긴합니다)