Codeforces Round 946 (Div. 3) Upsolving

지난주 첫 앳코더에 이어 첫 코드포스 div.3 참가해보았다.
A,B는 무난히 풀었고 C에서 시간을 많이 써 D를 제대로 구현하지 못 하고 끝나고 말았다. 그래도 div.2보다는 훨씬 할만했고, 앳코더 ABC와 비슷한 느낌이었다. 목표는 블루(1600)퍼포는 멀었지만 지금 퍼포먼스면 그레이딱지는 땔 수 있을거같아 기쁘다!

A. Phone Desktop

5X3 격자에 최대한 많은 x,y 아이콘을 넣어 최소한의 화면을 만드는 문제다.
문제를 읽자마자 그리디 문제구나 느낌이 왔지만 아직 그리디 문제를 많이 접하지 못해 구현에서 살짝 애를 먹었던 것같다.

풀이 시간 : 23분

AC를 받은 제출코드

import sys
 
input = sys.stdin.readline
 
for tc in range(int(input())):
    x,y = map(int,input().split())
    ans = 0
 
    while x !=0 or y != 0:
        if y >= 2:
            y -= 2
            if x >= 7:
                x -= 7
            else:
                x = 0
            ans += 1
        elif y == 1:
            y -= 1
            if x >= 11:
                x -= 11
            else:
                x = 0
            ans += 1
        else:
            if x >= 15:
                x -= 15
            else:
                x = 0
            ans += 1
    print(ans)

처음 짠 코드는 너무 이쁘게 코드를 짜려고하다가 실패해서 while문으로 남은 x,y 아이콘이 0이 될때까지 반복시켜 단순 수학적으로 최대한 많은 아이콘들을 0으로 만드는 코드를 짜서 제출하였다.

B. Symmetric Encoding

규칙에 맞게 문자열을 정렬 후 재배열하는 간단한 문제였다.
다만 문자열 N의 범위가 1≤𝑛≤2*10**5였기 때문에 딕셔너리를 사용해 시간복잡도를 줄였다.

풀이 시간 : 10분

AC를 받은 제출코드

import sys
 
 
for tc in range(int(sys.stdin.readline().rstrip())):
    n = int(sys.stdin.readline().rstrip())
 
    s = list(sys.stdin.readline().rstrip())
    set_s = sorted(list(set(s)))
 
    dic = {}
 
    for i in range(len(set_s)):
        dic[set_s[i]] = set_s[len(set_s)-i-1]
 
    for i in range(len(s)):
        s[i] = dic[s[i]]
 
    print(''.join(s))

문제에서 요구한 규칙에 맞게 set을 이용해 중복된 문자를 줄이고 dictionary를 이용해 각각의 문자에 대한 value값을 저장해주고 난 후 문자열 S를 재배열해주면 된다.

C. Beautiful Triple Pairs

코드포스 커뮤니티를 보니까 나 말고도 C가 생각보다 어려웠다는 말이 많았다. 나 역시 발상부터 어려웠던 것 같다.

문제는 자체는 정수 배열에서 길이 3씩 슬라이싱한 튜플들중 아래 3개의 조건들 중 하나를 만족시키는 2개 튜플의 순서쌍의 개수를 구하는 문제였다.

• 𝑏1≠𝑐1 and 𝑏2=𝑐2 and 𝑏3=𝑐3

• 𝑏1=𝑐1 and 𝑏2≠𝑐2 and 𝑏3=𝑐3

• 𝑏1=𝑐1 and 𝑏2=𝑐2 and 𝑏3≠𝑐3

이 문제 역시 배열의 길이 N의 범위가 3≤𝑛≤2*10**5였다.
하지만 시간제한이 4초였기 때문에 완전탐색으로 처음에 제출해보았는데 TLE가 떴다. 그 후 Dictionary로 푸는 풀이로 바꾸어 AC를 맞을 수 있었다.

풀이 시간 : 63분

TLE를 받은 제출코드

import sys
 
 
for tc in range(int(sys.stdin.readline().rstrip())):
    n = int(sys.stdin.readline().rstrip())
 
    arr = list(map(int,sys.stdin.readline().rstrip().split()))
 
    combi = []
 
    ans = 0
 
    for i in range(n-2):
        temp = arr[i:i+3]
        combi.append(temp)
 
    for i in range(len(combi) - 1):
        x, y, z = combi[i]
        for j in range(i + 1, len(combi)):
            a, b, c = combi[j]
            if x != a and y == b and z == c:
                ans += 1
            elif x == a and y != b and z == c:
                ans += 1
            elif x == a and y == b and z != c:
                ans += 1
 
    print(ans)

시간복잡도가 N^2이기 때문에 TLE를 받았다.

AC를 받은 제출코드

import sys
 
 
for tc in range(int(sys.stdin.readline().rstrip())):
    n = int(sys.stdin.readline().rstrip())
 
    arr = list(map(int,sys.stdin.readline().rstrip().split()))
 
    combi = []
 
    count = {}
    count_1 = {}
    count_2 = {}
    count_3 = {}
 
    ans = 0
 
    for i in range(n-2):
        temp = arr[i:i+3]
        combi.append(temp)
 
    for i in range(len(combi)):
        x, y, z = combi[i]
        count[(x,y,z)] = count.get((x,y,z),0) + 1
        count_1[(x,y)] = count_1.get((x,y),0) + 1
        count_2[(y,z)] = count_2.get((y,z),0) + 1
        count_3[(x,z)] = count_3.get((x,z),0) + 1
 
    for triple in combi:
        x,y,z = triple
        ans += count_1[(x,y)] - count[(x,y,z)]
        ans += count_2[(y,z)] - count[(x,y,z)]
        ans += count_3[(x,z)] - count[(x,y,z)]
        
    print(ans//2)

순서쌍 (x,y,z)의 중복방지와 x==y==z 예외를 막기 위한 count와 각 순서쌍을 dictionary로 만든 후 ans에 각 순서쌍에 대한 개수를 더해주고 (x,y,z)순서쌍에 개수를 빼주어 ans // 2를 하였다.

D. Ingenuity-2 (Upsolving)

C번 풀다 시간이 없어서 대회가 끝나고 풀었다. 그냥 깡구현이다.
N + S의 횟수가 홀수거나 E + W가 홀수면 NO를 출력하고 번갈아가며 이동시켜주다 이동한 좌표가 같고, R과 H가 1번이상 움직이면 정답을 출력, 아니면 NO를 출력해주면 된다.

Upsolving하여 AC를 받은 제출코드

import sys

for tc in range(int(sys.stdin.readline().rstrip())):
    n = int(sys.stdin.readline().rstrip())
    order = list(sys.stdin.readline().rstrip())

    dic = {'N': 0, 'E': 0, 'S': 0, 'W':0}

    p,q,r,s = 0,0,0,0
    ans = []
    sign_1 = True
    sign_2 = True
    sign_3 = True
    sign_4 = True

    a_1 = 0
    a_2 = 0

    for a in order:
        dic[a] += 1
    if (dic['N'] + dic['S']) % 2 == 1 or (dic['E'] + dic['W']) % 2 == 1:
        print("NO")
    else:
        for a in order:
            if a == "N":
                if sign_1:
                    ans.append("R")
                    p += 1
                    a_1 += 1
                    sign_1 = False
                else:
                    ans.append("H")
                    r += 1
                    a_2 += 1
                    sign_1 = True
                dic[a] -= 1
            elif a == "S":
                if sign_2:
                    ans.append("R")
                    p -= 1
                    a_1 += 1
                    sign_2 = False
                else:
                    ans.append("H")
                    r -= 1
                    a_2 += 1
                    sign_2 = True
                dic[a] -= 1
            elif a == "E":
                if sign_3:
                    ans.append("H")
                    s += 1
                    a_2 += 1
                    sign_3 = False
                else:
                    ans.append("R")
                    q += 1
                    a_1 += 1
                    sign_3 = True
                dic[a] -= 1
            else:
                if sign_4:
                    ans.append("H")
                    s -= 1
                    a_2 += 1
                    sign_4 = False
                else:
                    ans.append("R")
                    sign_4 = True
                    q -= 1
                    a_1 += 1
                dic[a] -= 1
        if p == r and q == s and a_1 * a_2 > 0:
            print(''.join(ans))
        else:
            print("NO")