2021 정보올림피아드 1차대회 고등부 2교시 짧은 풀이 + 후기

1 - 야구 시즌

식은(부등식으로) 간단하게 나오는데, 이거를 다시 B에 관한 식으로 바꿀 생각은 못했고 그냥 이분탐색 돌렸다.

아침에 일어나서 명일방주하느라 뇌 과부하돼서 문제 이해하는데 20분은 걸린듯

import sys
input = sys.stdin.readline
 
t = int(input())
while t:
    t -= 1
    
    n,m,k,d = map(int, input().split())
 
    lo = 1
    hi = d
    ans = -1
    now = 0
    mid = lo+hi >> 1
    mc = (m*(m-1))//2
    nc = (n*(n-1))//2
    while lo < hi:
        mid = (lo + hi)//2
        x1 = mid * k * mc * n
        x2 = nc * m * mid * m
        now = x1 + x2
        if now < d:
            ans = now
            lo = mid + 1
        elif now == d:
            ans = now
            break
        else:
            hi = mid
    print(ans)

 

2 - 초직사각형

a, b, c, d에서 증가되는 비율? 이라고 하는게 맞는지는 모르겠지만, 1에 1을 더하는 것과 10에 2를 더하는 것 중에서는 당연히 1에 1을 더하는게 이득이라는 것을 보고, 그냥 하드코딩했다 ㅋㅋ

import sys
input = sys.stdin.readline
 
n, k = map(int, input().split())
ar = list(map(int, input().split()))
 
a = [[],[],[],[]]
ans = []
for i in range(n):
    x, z = map(str, input().split())
    if x=="A": a[0].append(int(z))
    if x=="B": a[1].append(int(z))
    if x=="C": a[2].append(int(z))
    if x=="D": a[3].append(int(z))
 
for i in range(4):
    if len(a[i])==0: continue
    a[i].sort()
    a[i].reverse()
 
i1=0;i2=0;i3=0;i4=0
for _ in range(k):
    x = []
    if i1<len(a[0]):
        x.append(a[0][i1]/ar[0])
    if i2<len(a[1]):
        x.append(a[1][i2]/ar[1])
    if i3<len(a[2]):
        x.append(a[2][i3]/ar[2])
    if i4<len(a[3]):
        x.append(a[3][i4]/ar[3])
    if i1<len(a[0]) and max(x) == a[0][i1]/ar[0]:
        ar[0]+=a[0][i1]
        ans.append(["A", a[0][i1]])
        i1 += 1
    elif i2<len(a[1]) and max(x) == a[1][i2]/ar[1]:
        ar[1]+=a[1][i2]
        ans.append(["B", a[1][i2]])
        i2 += 1
    elif i3<len(a[2]) and max(x) == a[2][i3]/ar[2]:
        ar[2]+=a[2][i3]
        ans.append(["C", a[2][i3]])
        i3 += 1
    else:
        ar[3]+=a[3][i4]
        ans.append(["D", a[3][i4]])
        i4 += 1
 
for i in ans:
    print(*i)

 

3 - 공통 부분 수열 확장

이건 못풀었다

 

설명을 어떻게 해야되지..

 

\(W_{i}\) 사이사이에 남는? 문자열 배열을 X, Y 각각에 대해 구한다.

그리고 각 X, Y에 대해서 찾은 \(2 ( |W| + 1 )\) 개 의 배열을 정렬하고, 이걸 투포인터로 쭉 돌리면 된다.

 

시작점을 끝점으로 잡고 총 두번 돌리면 된다. 오른쪽 끝에서 돌릴 생각을 못해서 틀림

 

 

후기

왜 350점 받고 일반고 은상인지는 모르겠지만, 정말 아쉬웠고, 알고리즘을 늦게 접한게 아쉽기만 하다.. 작년 8월이 아니라 재작년 8월에 시작했다면 더 좋았을텐데