Codeforces - Problemset (rating 1000-1400) 문제 밀기

원래 고통스러운 여정엔 귀여운 썸네일이 제격

 

 

< 23.09.09 >

1851C- Tiles Comeback (1000)

https://codeforces.com/problemset/problem/1851/C

Problem - 1851C - Codeforces

 

Tag : Greedy

 

---

< 23.09.04 >

1850F - We Were Both Children (1300)

https://codeforces.com/problemset/problem/1850/F

Problem - 1850F - Codeforces

 

Tag : Bruteforce, Implementation, Math, Number Theory

이 문제는 본 대회 때 시간이 부족해서 못 푼 문제이다. 아마 내 기억상으로 문제 좀 읽어보다가 너무 피곤해서 + 시간이 얼마 안남아서 포기했던 것 같은데...? 업솔빙 하는 겸 다시 풀어보았다!

브루트포스를 사용해, 배수인 지점에 모두 cnt를 1씩 더해주면 된다. 본 대회에서 문제를 처음 접했을 때, 나는 GCD나 LCM 관련 문제인 줄 알고 어렵게 돌아갈 뻔했는데 다시 보니 중첩 for문으로도 충분히 돌아간다. 문제 입력 범위는 꽤 컸는데 제한 시간이 3초로 넉넉하게 주어져있었다. 아마 이 부분을 꼼꼼하게 체크하지 않아서 나처럼 돌아갈 가능성이 있었던 문제이다.설마 나이브하게 브루트포스로 다 도는거겠어? 라고 의심이 드는 문제들은, 범위를 꼼꼼하게 보고 한 번쯤 트라이 해 볼만한 것 같다. 특히 div3이어서 더더욱..!!

import sys
input = sys.stdin.readline
T = int(input())

for i in range(T):
    N = int(input())
    arr = list(map(int, input().split()))
    cnt = [0]*(N+1)
    res = [0]*(N+1)

    for j in range(N):
        if arr[j] <= N:
            cnt[arr[j]] += 1
    for j in range(1, N+1):
        for k in range(j, N+1, j):
            res[k] += cnt[j]
    print(max(res))

---

< 23.09.03 >

1849B - Monsters (1000)

https://codeforces.com/problemset/problem/1849/B

Problem - 1849B - Codeforces

Tag : Greedy, Math, Sorting

본 대회 때 python으로 정직하게 우선순위 큐를 구현해서 TLE 받은 문제이다...! 물론 나도 엄청난 범위의 입력을 보고 정직한 PQ로는 안뚫리겠지 싶었지만 혹시나 해서 제출해봤던 코드인데 역시나... 물론 나이브한 PQ 말고, PQ에 mod 처리를 조금 해주면 금방 AC를 맞을 수 있다.

나중에 살펴보니 mod를 활용한 그리디-정렬 풀이가 제일 많이 보였다. 체력이 줄어들 때 나누어 떨어지는 경우나 나머지가 있는 경우를 각각 처리해주면 된다.

아래는 pypy3 으로 AC를 받을 수 있는 코드이다.

import sys
input = sys.stdin.readline
T = int(input())

def MOD(A, K):
    if A%K == 0:
        return -K
    return -(A%K)

for i in range(T):
    N, K = map(int, input().split())
    H = list(map(int, input().split()))

    arr = [(MOD(value, K), i) for i, value in enumerate(H)]
    arr.sort()
    print(*[arr[i][1] + 1 for i in range(N)])

 

1850E - Cardboard for Pictures (1100)

https://codeforces.com/problemset/problem/1850/E

Problem - 1850E - Codeforces

Tag : Binary Search, Geometry, Implementation, Math

이건 본 대회 때 여러 번 시도해서 맞은 문제이다. 처음에 문제를 보자마자 이분 탐색, 매개 변수 탐색이 떠올랐고 생각한대로 구현해서 제출했다. 그런데 범위가 생각보다 더 커서 TLE 을 몇 번 받았다. 최적화를 위해 탐색 범위를 sqrt(N) 으로 줄이고, 코드도 최대한 줄여서 AC를 받았다.

아래는 pypy3 으로 AC를 받을 수 있는 코드이다.

#binary search? parametric search?
import sys
input = sys.stdin.readline
T = int(input())
 
for _ in range(T):
    n, c = map(int, input().split())
    nums = list(map(int, input().split()))
    start, end, target, res = 0, int(c**0.5), c, 0
 
    while start <= end:
        mid = (start + end)//2
        tmp = 0
        for k in range(len(nums)):
            tmp += (nums[k] + mid*2)**2
 
        if tmp == target:
            res = mid
            break
        if tmp < target:
            start = mid + 1
        else:
            end = mid - 1
    print(res)