Codeforces Round #694 (Div. 2) A ~ C

codeforces.com/contest/1471

Dashboard - Codeforces Round #694 (Div. 2) - Codeforces

 

풀은 문제: A, B

틀린 문제: C

못 풀은 문제: D, E, F

- 풀이만 보고 풀은 문제:

- 풀이와 코드 전부 본 문제: 

 

난이도

A - 900

B - 1100

C - 1300

D - 1900

E - 2500

F - 2200

 

 

C번은 0.004초 차이로 통과했는데 Fast io를 사용해서 추가제출을 안한 내 잘못....

빠른 입력을 사용할 떄와 사용하지 않을 때의 시간을 비교해보니 최대 3배 차이가 나는 문제도 있다. 코포 풀 때 무조건 써야할 것 같다.

 

 

 

 

A. Strange Partition

 

최소값은 x로 나누어질때만 최대한 다 더해주면 되고, 최대값은 x로 나누어 떨어지지 않을때 최대한 다 더해주면 된다.

 

코드는 min_num과 max_num이라는 값에 배열의 값을 하나씩 더해준다.

그러다가 min_num은 x로 나누어 떨어진다면 min_ans += min_num // x 를 하여 더해준다. 

max_num은 x로 나누어 떨어지지 않을때마다 max_ans += max_num // x + 1을 하여 더해준다.

 

그리고 while문이 끝나면 min_num과 max_num에 남은 수를 다시 처리하여 min_ans와 max_ans의 값을 갱신시켜주고 출력해준다.

 

for _ in range(int(input())):
    n,x=map(int,input().split())
    D = [*map(int,input().split())]
    y = 0
    min_num = 0
    max_num = 0
    min_ans = 0
    max_ans = 0
    while y < n:
        min_num += D[y]
        max_num += D[y]
        if min_num % x == 0:
            min_ans += min_num//x
            min_num = 0
        if max_num % x != 0:
            max_ans += max_num//x + 1
            max_num = 0
        y += 1
    if min_num % x == 0:
        min_ans += min_num//x
    else:
        min_ans += min_num//x+1
    if max_num % x == 0:
        max_ans += max_num//x
    else:
        max_ans += max_num//x+1
    print(min_ans,max_ans)

 

 

 

B. Strange List

 

nx를 x로 나누어서 나누어 떨어진 수를 x개만큼 넣어주는 것인데, 하나씩 넣으면 시간 초과가 난다.

그래서 숫자 nx가 ny개 있으면 [ nx // x, ny * x ] 로 큐에 넣어준다.

예제를 예시로 들자면 [4, 6, 8, 2]는 각각 한 개씩 있으므로 [4,1], [6,1], [8,1], [2,1]이고, [4,1]을 처리하면 [6,1],[8,1],[2,1],[4//2, 1*2]가 된다.

q에 원소를 하나 빼낼때마다 ans에 값을 더해주고, nx가 x로 나누어 떨어지지 않으면 더 이상 큐에 값을 넣지 않고 빼기만하여 ans에 값을 더해주고 출력해준다.

 

from collections import deque
input=__import__('sys').stdin.readline
for _ in range(int(input())):
    n,x=map(int,input().split())
    D = [*map(int,input().split())]
    q = deque()
    for i in range(n):
        q.append([D[i],1])
    ans = 0
    err = 0
    while q:
        nx, ny = q.popleft()
        if nx % x != 0: err = 1
        ans += nx*ny
        if not err: q.append([nx//x,ny*x])
    print(ans)

 

 

 

C. Strange Birthday Party

 

친구를 n명 초대하고, 선물은 m가지 종류가 있는데 각각 한 개만 살 수 있다고 한다.

이때 주인공은 친구에게 1번부터 k배열에 부여된 번호까지의 선물을 한 개 선물해주거나, k배열에 부여된 번호에 해당하는 선물을 현금으로 줄 수 있다고 한다. 이때 주인공이 준비해야할 최소의 돈은 얼마인지 구하는 문제이다.

 

각 친구의 번호와 현금으로 줄 때 선택할 수 있는 금액을 리스트에 넣어주고, 현금으로 줄 때를 기준으로 내림차순으로 정렬을 해준다.

그리고 이 친구들은 현금을 주는 것보다 싼 선물을 사주는게 무조건 이득이므로 선물을 사준다. 그렇게 선물을 가장 싼 것부터 하나하나씩 채워가다가 선물을 사줘도 되지만 이미 해당 선물을 다른 사람한테 선물해준 경우엔 현금을 주면 된다.

 

코드는 main함수만 보면 된다.

 

import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter, OrderedDict
import threading

def main():
    for _ in range(int(input())):
        n,m=map(int,input().split())
        k = [*map(int,input().split())]
        c = [*map(int,input().split())]
        D = []
        gift = [0] * m
        num = 0
        for i in range(n):
            D.append([i,c[k[i]-1]])
        D.sort(key = lambda a:a[1],reverse=True)
        ans = 0
        for i in range(n):
            idx, x = D[i]
            if gift[k[idx]-1] != 0: ans += x
            else:
                ans += c[num]
                gift[num] = 1
                num += 1
        print(ans)


BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    """sys.setrecursionlimit(400000)
    threading.stack_size(40960000)
    thread = threading.Thread(target=main)
    thread.start()"""
    main()