사라진 블로그! 연락 주시면 새로운 블로그 알려드립니다 ~

30일 오후 2시부터 5시까지 KCPC가 진행되었습니다. 대회 끝난지 하루도 안된 따끈따끈한 후기 쪄왔습니다
사실 과제가 많지만 저는 모릅니당 ㅎㅎ 개인전 & 오프라인은 너무 오랜만이라 재밌었습니당~ 야호!

타전공이기도 하고 신입생이기도 해서 올해는 타전공/신입생 부문으로 출전했습니당~!!
이 글은 절대 학습용/교육용 글이 아닌 뉴비보며 희망 얻어가세요~ 급의 발로 쓴 후기입니다. 저도 언젠가 성장하면 좋겠군요.

퍼솔 AC Pass 결국틀

#A 평생 새내기가 되고 싶은 유신이 (first-year) (3분 1try)
단순 구현..! 퍼솔했습니당ㅎㅎㅎㅎ(스코어보드에 1등 띄우는 거 처음이라 신났어요 >__<

#B 피카츄 라이츄 (pika) (9분 3tries)
코포도 KCPC도 B에서 삽질하는 징크스가 있는 듯 합니다ㅠㅠ
단순 구현은 맞는데 N이 날짜인 줄 알고 반복문 돌리다가 1틀
피카츄 경험치가 음수가 되는 거 모르고 1틀
ㅎㅎㅎㅎㅎㅎ 문제 좀 읽자
제가 2틀해서 이렇게 생각하는 건 절대 아니겠지만
문제가 어딘가 잘못되었다고 생각하는데
저는 경험치가 낮아지는 포켓몬 게임을 본 적이 없습니다 ㅎ..

#C KCPC는 무엇의 약자일까? (acronym) (14분 1try)
사실 문자열 보고 처음에 쫄았습니다.
설마 아호코라식...! 일 리는 없지만 설마 트라이 ...?? 둘다 절대 시간 내에 구현 불가능 ~
작년까지 문자열 입출력을 못받던 저는....ㅎ ㅎㅎ kmp도 최근에 공부했기 때문에ㅎ ㅎㅎ 머든 나오면 거릅니다.
다행히 단순 오토마타 문제였습니다. 후 뇌절말고 구현해야죠

3솔브한 시점에서 문제가 난이도 순이라는 걸 눈치챘어야 했지만 그러지 못했죠. ㅎㅅㅎ

#D 초코칩 케이크 (cake)
슬슬 어려운 문제가 나올 시점이라고 생각했습니다.
숭고한 캠프에서 세그먼트 트리를 진행했던 분이 문제에 등장하셨는데, 여기에 N제한이 30만이나 되길래
아 세그먼트 트리 문제구나! (<-아니었음) 이따 풀어야지하고 잠시 ㅌㅌ했습니다.

#E 함정에 빠진 이동관 (trap) (33분 1try)
누가봐도 단순 BFS! 뇌절말고 열심히 짰습니다.
초반이라 구현 속도도 준수했고 D를 건너뛴 덕분에 퍼솔을 먹었습니다.
근데 1등님 6분컷한 거 보고 좀 소름...

D 잠깐 다시 읽었는데 딱히 생각 안나서 또 패스

#F 대자보 (poster)
어 혹시 정수론? 점화식? 네모는 수학이 시러시러~ㅂㅂ
나중에 챙기러 돌아올까 했지만 다른 문제들에 막혀서 시간없어서 얘는 여기서 ㅂㅂ~

#G 신앙 (faith) (2tries)
빨간약 한 놈 씩 몰빵해주면서 s-h순으로 정렬해놓고 위에서부터 s-h>0인 경우에 파란약 먹이면 될 거 같았는데
풀이 자체는 어렵지 않아보이긴 합니다...만 맞왜틀
몇 번 더 틀리고 나중에 봐야지 하고 넘어갔습니다.

#H 얼마나 예뻐? (pretty)
안 예뻐요. 트리. 전위순회. ㅂㅂ

문제를 안 읽고 넘긴 건 이게 유일한데 마지막에 보니 다들 이거 붙잡고 있어서 쪼끔 후회.....ㅎ

#I ㅇㅇ (oo)
역톨레미로 후다닥 점 분류했는데 답을 출력할 때 보니까 외심의 좌표도 출력하라 하네요 ㅎㅎㅎ
꼼수따윈 통하지 않는... 문제 좀 읽자.
역톨 없어도 세 점 주면 외심 내놓는 함수 (이거 약간 뇌절...) 짜면 분류도 똑같이 할 수 있죠 ㅎㅎㅎ 머한거지
구현하기도 싫고 지금까지 뭐했나 싶어서 뇌절하다가 스코어보드 보니까 케이크가 많이 풀렸길래 잠시 Pass

#D 케이크 (66분 1try)
ㅎㅎㅎㅎ 쉬운 문제라는 걸 인지하니 풀이도 바로 떠올라서 뚝딱
너무 늦게 풀긴 했지만 다른 친구들도 나름 어디선가 삽질하고 있었는지 3등이었습니다. (문제는 이 때가 66분이었는데, 이 뒤로로 맞은 문제가 없.... ㅎㅎ )

빠가사린가.. 이 때는 진짜 문제가 난이도 순이라는 걸 조금이나마 눈치챘어야 합니다.
이 시점에서 5솔/3등이었는데 1,2등이 너무 막강하고 다른 5솔이 한 명밖에 없었기 때문에
남은 시간 동안 어떻게든 G를 고치고 I나 계속 풀어야지~ 라는 전략을 세웠습니다.
둘 중 하나만 이루면 성공하는 전략이었으나, 둘다 망해서 전략은 실패했죠

다시 G를 잠깐 보긴 봤습니다만 아무리 생각해도 반례가 떠오르지 않았습니다 ㅎㅎ
F랑 H는 끝까지 관심을 못 주었습니다 ㅠ 미안해..

#I ㅇㅇ (oo) (5tries)
2시간 이상 꼬라박았네요. 호감상으로 잘생긴 문제였습니다. 열심히 외심 구하는 공식을 짰습니다. 수직이등분선이 수평/수직일 때, 세 점이 한 직선 위인 경우 등 열심히 고려하고
대회 시작하고 두 시간 즈음 되서 완성하고 제출했는데 틀렸습니다. 틀렸습니다. 틀렸습니다. 틀렸습니다. 틀렸습니다.
ㅎㅎ 문제 인성이 참.....(제 실력의 문제죠) 이때 던지고 H를 보던 G를 고치던 해야했습니다 ㅎㅎㅎㅎ..

1시간 남은 시점에서 5솔브들이 많아졌고, 다들 무언가 시도하고 있었기에 어떻게든 하나를 풀어야 안전(?)해지는데
G는 도저히 반례를 모르겠고 F도 잠깐 봤는데 모르겠고 H는 읽기 싫었습니다.
I는 여전히 시도하는 사람이 없길래 출제자 심심할까봐, I랑 마지막까지 놀았습니당.

그렇게 저는 G랑 I를 끝까지 틀리고 5솔브/3등으로 마감햇습니당!
66분 이후로 푼 게 없는데 기도메타 성공해서 등수 3등 고정~~ㅎ

나중에 풀이 설명해주는데
아직도 G틀린 이유는 잘 모르겠습니다 흑....
I는 1. long double 미사용 2. 외심의 범위가 10^6 바깥일 수 있음의 두 가지 이유로 틀린 듯 합니다 ㅎㅎ
실수 문제 보면 맨날 넘겨서 잘 몰랐는데
double이 만능 짱짱맨이 아니란 걸 처음 알았습니다. 아니 10^12가 될 리가 없었죠 ㅎ 생각이 없었네요
그리고 문제 좀 읽자

개인전 오프라인 오랜만인데 문제가 많아서 좋았습니다.
저는 혼자 두면 네모 하고 싶은 거 다 해~~ 편식 모드이기 때문에 풀고 싶은 문제를 잡고 시간을 열심히 꼬라박는데
문제 선택에 많은 자유도가 있었기에 더더욱 즐길 수 있었지 않나 싶습니다.

기도메타 성공한 것도 너무 좋습니다. 제 실력에서 최고등수가 3등이라고 생각했는데 딱 그렇게 나왔네요 ㅎㅎㅎ
GI를 둘다 틀려버린게 아쉽지만, 둘 중 하나를 푼다고 해서 제 등수가 변하는 건 아니라서요ㅎㅎㅎ

대회후기 요약:
모두가 행복한 대회를 만들고 싶었다고 강조하셨는데,
모두가 행복한 대회는 모두가 무언가를 얻어가는(받아가는) 대회가 아닌가 싶습니다. (속마음::기념품 안 준 게 아깝...
각자 나름의 무언가를 얻어갔을 것 같은데
저는 I랑 2시간 즐겁게 놀았고, 무엇보다 20만원 너무 좋습니다 행복합니다~

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차 분들 깔아드리겠습니다ㅎㅅㅎ