Codeforces Round #531 (Div. 3) A ~ E

codeforces.com/contest/1102

Dashboard - Codeforces Round #531 (Div. 3) - Codeforces

혼자서 풀은 문제: A, C, D, E
풀이만 보고 풀은 문제: B

풀이와 코드까지 전부 본 문제: F

 

 

문제 난이도

A - 800

B - 1400

C - 1200

D - 1500

E - 1700

F - 2000

 

 

B번 문제는 이해하기가 어려워서 풀이를 봤다. 풀이보니까 그냥 좀 더 문제 내용을 이해해볼걸 그랬다.

F번 풀이봐도 이해를 못하겠어서 코드를 보니까 내가 풀을 수준의 문제가 아닌 것 같다.

 

 

 

A. Integer Sequence Dividing

 

n을 입력받으면 1부터 n까지의 수들을 A와 B 두 곳에 적절히 분배하여 |sum(A)-sum(B)|를 최소값으로 만드는 문제이다.

 

 

답을 찾는건 n=9일때 이렇게 연필로 선 그은 것처럼 연결하여

A = { 1 }이면 B = { 9 }이고, A = { 1, 8 }일 때 B = { 2, 9 }로 하여 하나씩 넣어주면 된다. 홀수 마지막 숫자는 1이 있는 곳에 넣어주면 된다.

그러면 A = { 1, 8, 3, 6, 5 }, B = { 9, 2, 7, 4 }로 최소값이 1이 나온다.

 

이렇게하면 n = 1, 5, 9, 13, ... 일때는 답이 1이고, n = 3, 7, 11, 15, ... 일때는 답은 0이다.

 

짝수의 경우에는 모든 수가 1씩 차이나게 짝지어 질 수 있으므로 n이 4의 배수인 짝수이면 0이고, n이 4의 배수가 아닌 짝수이면 1이 나올 것이다.

 

n = 8로 예시를 대보면 위와 같이 1씩 차이나게 할 수 있기 때문에 A와 B에 선에 그은 숫자를 하나씩 선택해주면 A = { 1 }, B = { 2 }이고, A = { 1, 4 }, B = { 2, 3 }이고, .... , A = { 1, 4, 5, 8 }, B = { 2, 3, 6, 7 }로 답이 0이 나온다.

하지만 4의 배수가 아닌 짝수는 1의 차이가 날 수 밖에 없으므로 답이 1이다.

 

이걸 코드로 표현하면 4로 나눌경우 나머지가 1과 2가 나오면 답은 1, 나머지가 3과 0으로 나오면 답이 0이다.

 

n = int(input())
if n%4 in [1,2]:print(1)
else:print(0)

 

 

 

 

B. Array K-Coloring

 

- 각 요소들은 무조건 색깔이 칠해져 있어야함

- 모든 색깔은 최소 한번 이상은 칠해져야함

- i번째 색깔로 칠해진 요소들은 값이 전부 달라야한다.

세번째 조건이 자꾸 해석이 안되서 풀이를 봐버렸다.

 

이 문제는 그냥 모든 숫자를 다 입력받은 다음 파이썬은 리스트를 이용한 스택(C++은 벡터)을 이용하여 [숫자값, 위치, 색깔]을 넣어준다. 이때 처음 값을 넣을 때는 해당칸에 칠할 색깔이 정해지지 않았으므로 [숫자값, 위치, -1]을 넣어준다. 그리고 숫자값은 최대 5000이므로 5000칸 배열 K를 만들어주어서 어떤 숫자가 몇 개 들어오는지 세어본다.

이때 배열 K의 최대값이 입력값 k를 넘어가면 세번째 조건에 위배되므로 무조건 NO이다. 이경우만 아니라면 전부 YES이다.

 

그다음 [숫자값, 위치, -1]을 넣은 리스트를 숫자값을 기준으로 정렬해주고, for문을 이용하여 i%k를 색깔위치에 부여해준다. 색깔 숫자가 0부터 시작하므로 출력할때 i%k + 1을 해주면 된다.

 

그다음 이제 정답을 출력할 배열 ans를 만들고 다시 for문으로 [숫자값, 위치, 색깔]을 저장한 리스트를 이용해 ans[위치] = 색깔+1을 해준다.

이러고 출력하면 끝난다.

 

n, k = map(int,input().split())
D = [*map(int,input().split())]
S = []
K = [0]*5001
for i in range(n):
    S.append([D[i],i,0])
    K[D[i]]+=1
if max(K) > k: print('NO'); exit(0)
S = sorted(S)
for i in range(n):
    S[i][2] = i%k
ans = [0]*n
for i in range(n):
    ans[S[i][1]] = S[i][2] + 1
print('YES')
print(' '.join(map(str,ans)))

 

 

 

C. Doors Breaking and Repairing

 

n, x, y와 문의 내구도를 입력 받고, 나는 x만큼 문의 내구도를 부수는데, 상대방은 y만큼 문의 내구도를 수리할 때, 상대방이나 나나 최선의 선택을 하는 경우 내가 최대 몇 개의 문을 부술 수 있는지 구하는 문제이다.

 

턴이 10^100이기 때문에 x와 y가 10^5이므로 x = 10^5, y = 10^5-1, 어느 문의 내구도가 최대값인 10^5면 10^5턴으로 다 부술 수 있고, n이 10^2이기 때문에 아무리 늦어도 10^7턴내에 문을 다 부술 수 있어서 x > y인 경우 모든 문을 부술 수 있다.

x <= y인 경우 선공이 나부터 문을 부수는 경우이므로 문의 내구도를 정렬한다음, 첫번째 수는 내가 부수고, 두번째 수는 상대방이 수리하고, 세번째 수는 내가 부수고, ... 이러면 서로 최선의 선택을 했기 때문에 이 과정을 for문으로 구현해주면 된다.

 

n,x,y=map(int,input().split())
D = sorted([*map(int,input().split())])
ans = 0
if x > y: ans = n
else:
    for i in range(n):
        if D[i] > x: break
        if i % 2 == 0: ans+=1
print(ans)

 

 

 

D. Balanced Ternary String

 

일단 0, 1, 2의 개수를 세어보고 어떤 수는 얼만큼 제거해야하는지, 어떤수는 얼만큼 추가해야하는지 구한다.

이것은 n//3에 각 숫자의 개수를 빼면 된다. 양수일 경우 그만큼 추가해야하고, 음수일 경우 그만큼 다른수로 교체해줘야한다.

 

그다음 처음엔 s[0]부터 시작해서 s[n-1]로 끝나는 for문으로 2대신 0과 1, 1대신 0을 교체할 수 있게 해준다.

여기서 주의할 점은 2만 교체해서 0과 1로 바꿔야하는 경우, 문제에서 사전순으로 가장 먼저오는 숫자를 출력하라고 했으므로 2를 0으로 먼저 바꾸고, 0으로 다 바꾸면 1로 바꿔야하는 순서가 있다.

 

그리고 s[n-1]부터 시작해서 s[0]으로 끝나는 for문으로 0대신 1과 2, 1대신 2를 교체할 수 있게 해준다.

마찬가지로 여기서 주의할 점은 0을 교체해서 1과 2로 바꿔야하는 경우, 사전순으로 가장 먼저와야하니 뒤쪽은 먼저 2로 채우고, 앞에선 1로 채워야하므로 0을 2로 먼저 바꿔주고, 2로 다 바꿨으면 1로 바꿔야한다.

 

이걸 구현하면 통과한다.

 

n = int(input())
s = [*input()]
a,b,c = 0,0,0
for i in range(n):
    if s[i] == '0': a+=1
    if s[i] == '1': b+=1
    if s[i] == '2': c+=1
na, nb, nc = n//3-a, n//3-b, n//3-c
for i in range(n):
    if s[i] == '1' and na > 0 and nb < 0:
        s[i] = '0'; na -= 1; nb += 1
    if s[i] == '2' and nc < 0:
        if na > 0: s[i] = '0'; na -= 1; nc += 1
        elif nb > 0: s[i] = '1'; nb -= 1; nc += 1
for i in range(n-1,-1,-1):
    if s[i] == '1' and nb < 0 and nc > 0:
        s[i] = '2'; nb += 1; nc -= 1
    if s[i] == '0' and na < 0:
        if nc > 0:s[i] = '2'; na += 1; nc -= 1
        elif nb > 0: s[i] = '1'; na += 1; nb -= 1
print(''.join(s))

 

 

 

 

 

E. Monotonic Renumeration

 

E는 생각 좀 많이했어서 실제 대회였으면 시간내에 못 풀었을 수도 있을 것 같다.

 

일단 숫자가 여러개 들어올 수 있으니 pos_max라는 파이썬 dict(C++이면 map?)을 사용하여 해당 숫자가 나오는 최대 위치를 구하였다.

dict로 만들어준 이유는 10^9이기 때문에 배열로 만들면 메모리가 터지기 때문이다.

 

그다음 출력할 값 ans = 1과 입력받는 수열의 첫번째 값이 언제 마지막으로 나오는지 pos_max를 통해 ans_pos로 저장해두었다.

이러고 for문을 돌려서 어떤 숫자의 값이 pos_max보다 작은 경우, pos_max에 해당하는 b_i의 값과 똑같다는 것이므로 ans만 그대로 두고, ans_pos만 max(pos_max[현재위치], ans_pos)로 갱신해준다.

그러다가 i가 ans_pos를 넘어서면 그때부터 값이 2가지로 나뉘는 것이므로 ans = (ans * 2) %MOD를 해주고 ans_pos의 값을 pos_max[현재위치]로 수정해준다.

 

이러면 통과할 수 있다.

MOD = 998244353
n = int(input())
D = [*map(int,input().split())]
pos_max = {}
for i in range(n):
    pos_max[D[i]] = i

ans = 1
ans_pos = pos_max[D[0]]

for i in range(1,n):
    if i > ans_pos:
        ans = (ans*2)%MOD
        ans_pos = pos_max[D[i]]
    else: ans_pos = max(pos_max[D[i]],ans_pos)
print(ans)