2022 서울사이버대학교 프로그래밍 경진대회 (SCUPC)

2022 서울사이버대학교 프로그래밍 경진대회 (SCUPC)

A - 빅데이터? 정보보호!

N과 문자열의 길이만 보면 된다.

00:02 AC

 

B - 멘토와 멘티

정렬

00:04 AC

 

D - 은?행 털!자 1

map<ll, ll>과 T - X

00:09 AC

 

C - 비즈네르 암호 해독

구현

00:17 AC

 

E - 은?행 털!자 2

D번과 유사하게 접근하면 된다.

upper_bound로 T - X 이하인 원소를 찾아준다.

그리고 순회하면서 필요 없는 원소는 적절히 지워주면 된다.

00:27 AC

 

G - 최빈값과 쿼리

전혀 다른 문제이지만 E번과 유사하게 접근하면 된다.

먼저 x가 K번 등장하는 연속된 부분 수열을 모두 찾자.

이때 수열은 x로 시작해서 x로 끝나야 한다.

전처리를 마친 후 offline query를 곁들이면 끝이다.

map에서는 수열의 시작 인덱스와 길이를 관리하면 된다.

00:45 WA

00:49 WA

 

현재 수열의 시작 인덱스보다 큰 key가 존재한다면 해당 수열은 무시해야 한다.

00:59 WA

iterator 사용이 미흡하였다.

01:04 AC

 

F - 간단한 수학 문제

nHr을 구해야 하는데 overflow가 문제가 된다.

__int128 타입을 사용하고 X를 초과하면 계산을 중단하도록 하면 된다.

02:19 AC

 

푸는 데 한 시간이 넘게 걸렸다.

첫 번째 이유는 내가 수학에 약하기 때문이다.

수학 능지가 박살 나서 수식만 보면 뇌세포가 파업을 한다.

 

두 번째 이유는 잘못된 가정을 하였기 때문이다.

nHr은 nCr과 마찬가지로 계산이 오래 걸린다.

C(100000, 99999)의 계산 과정을 생각해보면 된다.

결과는 100000이지만 99999번의 곱셈과 나눗셈이 필요하다.

 

따라서 nHr을 매번 계산하면 TLE를 받는다고 생각하였다.

그래서 nHr은 한 번만 구하고 이후에는 이 값을 조금씩 변형해서 사용하도록 하였다.

물론 가능한 풀이이지만 수식에 약한 나에게는 적절하지 않았다.

 

대회 종료 후 알게 된 사실인데 매번 새로 값을 구하더라도 전혀 문제가 없다.

r = min(r, n - r)을 이용하면 계산은 상당히 빨리 끝난다.

물론 C(100000, 50000)와 같은 계산은 오래 걸리겠지만 그 전에 X를 초과하므로 문제가 되지 않는다.

 

H - LFIS (not solved)

Pass

 

I - 점호 (not solved)

Pass

 

J - 레이무의 순간이동 연습 (not solved)

Pass

 

K - 모모의 아지트에 잠입하자! (not solved)

Pass

 

끝

끝