2019 SCPC 1차 온라인 예선 후기

21일 오전 9시부터 22일 오후 9시까지 SCPC가 진행되었습니다. 작년 포스터를 잘못 봐서 토요일로 알고 있었는데 금요일이더군요;;; 토욜 약속을 다 취소하고 금요일로 잡아놔서 밤 샜습니다 ㅠㅠ

저는 SCPC 1차 온라인 예선 후기를 찾아보면서 나오는 블로그들이 너무 갓갓하셔서 [세상은 넓고 잘하는 사람은 많아] 하구 절망했었기 때문에 저도 후기 하나 남겨봅니다.
여러분은 미천한 저를 보면서 희망을 얻어가세요.

#1 오르락 내리락 (제출 2248회 맞은 사람 1059명)
BFS로 누적합-N배열을 미리 만들어 놓으면 각각의 TC들은 O(1)로 계산할 수 있습니다.
O(N * T)

특이한게 제출했을 때 1.0000X초 정도로 틀렸습니다. 계속 내다보면 한 번 즈음은 맞지 않을까 하고 5번 냈는데 안 되더라구요ㅋㅋ 2019-10-26 추가:: 삼성이 시간제한 넘어가버리면 그냥 바로 끊고 TLE 때려서 그렇다구 하네요.
결국 cin을 printf로 바꿔서 맞았습니다. 나중에 공지 뜨네요 ㅋㅋㅋ..
그러나 6번이나 틀려서 제출횟수 패널티 때문에 상당히 긴장했습니다.

#2 공 굴리기 (제출 1323회 맞은 사람 1029명
중딩 수학문제입니다. 직선경로와 회전경로 나누어서 계산했습니다.
R<h일 때 계속 답이 다르게 나와서 한참 고민했는데 (댕청..) R<h인 경우 직선 경로가 찔끔 늘어난다는 점 고려해서 계산하면 됩니다.

#3 점프 (제출 1064회 맞은 사람 107명)
못 풀었습니다 (당당)
Hap 배열을 만들어서 i번째 칸에는 1~i까지 합 넣어두고 (영알못이기 때문에 콩글리쉬 배열명을 씁니다.)
그리디하게 y 부터 y-Hap[upperbound(Hap,Hap+Hap.size(), y)-1] (씨알못이라 문법 잘 못 외워서 틀릴 수도 있습니다.)까지만 대강 구하면 될 것 같았습니다.

근데 나중에 N=20일 때 반례 생기는 거 깨닫고 던졌습니다.
사실 삼성이 10번까지만 제출 가능한데, 9번 즈음 틀릴 때 즈음 자포자기...했습니다. (사실 4번 긁고 개이득~하고 자러 갔습니다 ㅋㅋ

듣기로는 N이 작을 때는 직접 구하고 N이 특정 이상 커지면 위에 풀이처럼 그리디 하면 된다네요.

근데 그 이전에 저는 맞왜tle... 코드에도 문제가 있었나 봐요 흑.. 다 잘했는데

#4 파이프 (제출 160회 맞은 사람 25명)
와..!! 제 수면 시간을 지켜준 고마운 문제입니다. 휴리스틱 문제 보면 다들 피하시는 것 같은데, 저도 그럽니다ㅋㅋㅋ
근데 문제 읽어보니까 출제진이 제안한 답 * 2 이내이면 점수를 준다길래, 그냥 크기 순으로 정렬해서 챠르르륵 이어붙이는 코드 뚝딱하고 제출하니 186점... ㄱㅇㄷ

#5 세포 키우기 (제출 334회 맞은 사람 102명)
하.. 1차는 통과할 것 같고 자러 가야해서 문제만 읽어봤습니다. (못 풀겠다는 핑계 맞습니다.)
문제를 읽어도 아무런 생각이 들지 않았습니다.

345는 맞은 사람이 백 명 아래군요. 특히 4번 25명 ㄷㄷ...저도 그렇고 다들 아직 휴리스틱 기법에 익숙하지 않나봅니다. 저는 유명하거나 쉬운 알골만 공부하기 때문에 푼 사람 수를 보니 아직은 공부 안해도 될 것 같습니다. (따라하지 마세요)

그렇게 저는 4번의 혜자로운 부분점수 받고 386점으로 마감했습니당~ 온2차 분들 깔아드리겠습니다ㅎㅅㅎ