티스토리 뷰

공부

제 5회 kriiicon

구사과 2017.08.14 23:47

(5/1 16:53 초판)

(5/4 LM 풀이 추가, RST 약간 수정)

(8/14 크리님의 생일을 맞아서 다시 풀어보고 있다. YZ 풀이 추가. RST 풀이 약간 추가)


범수형이 검수하러 간 틈을 타서 몰래 껴들어갔다. 

팀 이름은 내가 AcornCkiGs14004Team으로 지었다. 하지만 ainta가 지은 기만 팀명에 능욕당했다. 이럴 줄 알았으면 ↑우리보다못하는팀 으로 바꾸고 나올 걸 그랬다...

아쉬움 없을 만큼 하고 나왔기 때문에 아주 즐거웠다. 

사실 극후반부에 서버가 터져서 PQ 제출에 문제가 있었다. 열심히 제출해도 안 돼서 상당히 짜증났지만, 알고 보니 내 제출이 4시간 59분 59초에 기적적으로 큐에 들어가서 2점을 득점했었다 (...) 그래서 안 짜증났다.


후기는 그냥 좀 재미있던 것만 간략하게 쓰려고 한다. 몇 문제는 스포일러도 있다 (물론 가려놨다).

ABC

한 10분 쯤에 dotorya님이 격침했다.


DE

출제자 풀이가 틀린 문제였다. 그게 얼마나 심각했냐면 예제 2가 안 나왔다 (...)  "정수 점만 가져갈 수 있습니다" 라는 조건으로 겨우 살렸지만 dotorya님이 날렸던 20분은 되찾지 못했다. ㄹㅇ루노답


HI

재밌는 문제다. 나중에 풀어봐야지


JK

ainta랑 같이 돌았던 opencup에 똑같은 문제가 있었다. k번째를 안 찍는 거 빼고 전부 똑같았다. 난 이걸 그 전에 풀어봤기 때문에 풀 수 있었지만 어째 그 때도 인타는 신기하게 잘 풀더라. 


LM

Dynamic MST로 비비다가 실패했다. 사실 별로 승산이 없는 접근이기도 했다 ㅋㅋ 크리님한테 정해 스포일러를 들었는데 아주 멋진 문제였다.

풀이

NO

재밌는 문제였다.

풀이

RST

대회 때는 자비없는 2점 서브태스크의 상태를 보고 생각조차 하지 않았으나, 끝나고 보니 아주 신기한 문제인거 같다.

풀이를 보고 이해는 했는데 수식편집기의 보조가 없이는 풀이를 쓸 수가 없다. 그리고 난 수식편집기를 어찌 쓰는지 잘 모른다. 고로 크리님 블로그를 참고하자..

대충 키워드만 설명하자면, 결국 DP를 구하는 것이 행렬 연산과 역행렬 연산의 조합이라 쿼리 당 O(53^3)에 해결할 수 있고, 이 행렬 / 역행렬 연산을 잘 분석해 보면 굉장히 단순한 형태라는 것을 더 관찰하면 이를 쿼리 당 O(53)까지 줄일 수 있다.


YZ

CERC2015 Looping Labyrinth 문제의 약한 버전이라고 한다. 대회 중에는 상수가 풀었다.

더보기


'공부' 카테고리의 다른 글

RUN@KAIST 8/2 방학 연습 풀이  (0) 2017.08.16
RUN@KAIST 7/30 방학 연습 풀이  (2) 2017.08.15
제 5회 kriiicon  (0) 2017.08.14
RUN@KAIST 7/23 방학 연습 풀이  (0) 2017.08.08
RUN@KAIST 7/20 방학 연습 풀이  (0) 2017.08.07
OI Checklist 2017  (0) 2017.08.06
댓글
댓글쓰기 폼
공지사항
Total
217,120
Today
420
Yesterday
403