오늘 세종정올 본선에 참여하고 왔다.
자리배치가 세과영이 일반고를 포위하는 형태였다
일반고그만괴롭혀!!!!!!!!
점수는 500점 중 434점.
ABCDE 중에 ABCE 풀고 D를 34점 긁었다.
세과영애들이랑 맞춰보니까 6등쯤 될거같다는데
동상컷이 6등까지라 긴장이 됩니다 ㅠㅠ
1번
1번은 배열하나주고 구간 [s,e] 에서 소수의 합을 구하는 문제.
범위가 타이트하지 않아서 그냥 나이브하게 에라토스테네스 쓰면 됨
시간복잡도는 O(QN + N^2)
2번
2번은 길이가 M인 구간 내에 있는 서로 다른 숫자의 개수.
슬라이딩 써서 쭉 밀면 된다.
O(N)
3번
3번은 최소한의 바꾸기 연산으로 등차수열을 만드는 문제
어떻게만들까 하다가
등차수열 -> 일차함수 로 잡고
점 두개 nC2 해서 고른다음에
그걸로 일차함수 만들어서 일차함수위의 점 갯수의 최대값을 구했다.
시간복잡도는 O(N^3)
이게 뇌절풀이라고 하던데
이거밖에 안떠오름 ㅠㅠ
4번
dp인거같은데 정확히 다 풀진 못함.
dp[i][j][k] =>
i번째까지 컵가지고 뭔갈 했을때 &
컵스택이 J개 &
지금 들고있는게 k일때의 최대 점수값.
이렇게 잡고
- 바로앞 컵을 버리고 점수유지
- 지금컵을 쌓아서 스택을 늘림
- 점수 정리 하고 새 스택을 만듬
으로 나눠서 박으면 서브태스크 한개,
여기다가 메모이제이션 하면 서브태스크 두개
섭태 두개 긁고 34점 만들었다.
5번
같은 학교의 익명의 토마토는 모스를 박았다 하던데
범위가 묘하게 작아서
그냥 나이브하게 된다
구간전체를 완탐해줘도 뚫린다
O(Q(N+M)) 에 뚫림을 확인, 100점을 만들었다.
중간에 테스트케이스 오류도 있었고
불명확한 문제 지문이나
채점서버 렉이 심하다던가
암튼 여러모로 다사다난한 셋이었다.
난이도적으로는 3 4번이 어려웠던듯?
3번은 이상하게 뇌절친건가
암튼 그랬다.
개인적으로 대회 취급이 가면갈수록 짜진다 생각함
차피 세과영 교내대회 언저리라서 그런가 싶기도한데
갠적으론 몇년전에 상품같은거 받아서 잘 쓰고 있는지라
상품이라던지 돌아왔으면 좋겠네요
올해에는 usb조차 없던데 좀 슬픕니다 ㅠ
화요일날 대회결과로 최종적으로 동상 받는게 결정이 되었습니다.
