티스토리 뷰

호에에엥 오늘 카카오 코드 페스티벌 예선전이 열린다.

사실 지금 대회 1시간 30분 정도 남았는데 미리 후기 쓰고 쉬려고 한다.


작년에는 프로그래머스? 플랫폼에서 대회가 진행되었는데 올해는 BOJ에서 개최되었다.

비교적 친숙한 플랫폼이어서 좋았고 본선도 BOJ에서 하지 않을까 싶다. 하지만 작년 본선 컴퓨타가 리눅스 환경이었는데

코드블럭 폰트가 너무 극혐이라서 웹코딩했는데 올해는 어쩔지 모르겠다.


문제들 난이도는 작년보다 어려운 것 같고 올해 본선 진출자는 64명이라고 한다. 현재 글을 쓰는 시점에서는 내가 13등이라 이변이 없지 않는 한 진출하지 않을까 싶다.

체감 난이도는 A=B<D<C<E<<F 인것 같다. 간략하게 풀이 적어보겠다.


A번은 문제 잘 읽고 그대로 구현하는 문제이고 쉽게 하는 방법은 잘 모르겠다. 나는 그냥 다 타이핑했다.

배열크기 잘못잡아서 1WA 맞고 AC받았다.


B번은 K이상 연속하는 구간 잡아서 가장 표준편차가 작은 구간을 찾으면 된다. O(N^3) 으로 그냥 뚝딱뚝했다.


C번부터 약간 헬인데 문제에서 주어진 조건문의 길이를 최대한 줄여보자 라는 문제이다.

생각해야 하는 케이스가 좀 많다.


먼저 피연산자가 둘다 정수인 경우에 항상 가능하거나 항상 불가능하다. 항상 불가능하다면 4글자로 false를 표현할 수 있다. (ex: 1==0) 

항상 가능하다면 조건문에 영향을 주지 않는 논리식이다. 삭제 가능하다.


다음 ==으로 묶인 단항식은 하나의 컴포넌트로 묶어보자. 이 컴포넌트 내에 정수가 2개 이상 존재하면 항상 불가능이다.

따라서 4글자로 false를 표현 해도 동치이다.


이 후 이 컴포넌트를 표현할 때 필요한 논리식은 컴포넌트의 크기를 n이라고 했을 때 n-1개면 된다. n-1개의 논리식은 해당 컴포넌트에서 단항식의 길이가 가장 작은애를 기준으로 잡고 나머지를 다 기준에 연결해주면 된다. 그렇게 하면 전체 길이의 합이 최소가 된다.


다음으로 ==으로 묶인 컴포넌트 끼리 !=로 서로 다름을 표현해 준다. 두 컴포넌트가 만약 같다면 항상 불가능이다. 두 컴포넌트에 여러개의 !=이 존재하더라도 한번만 연결해주면 된다. 연결 할 때는 각 컴포넌트에서 단항식의 길이가 가장 작은 애 끼리 연결한다.

마지막으로 !=로 연결할 때 예외가 하나 있다. 각 두 컴포넌트에 정수인 단항식이 한 개씩 존재한다면 두 컴포넌트는 !=로 연결하지 않아도 자명하게 다름이 보장된다. 삭제 가능하다.

대충 위와 같은 케이스들을 생각해서 그대로 구현하면 되고 나는 union-find 자료구조에 root가 무적권 단항식의 길이가 가장 작도록 merge했다.


D는 체크포인트 끼리 이동가능한지 여부를 판단하는 문제인데 쿼리문제고 슥샥속 보면 왠지 주어진 체크포인트들을 트리로 표현할 수 있을 것 같은 느낌이 강렬하게 드는 문제이다. 각각의 체크포인트에서 다른 모든 체크포인트까지의 거리는 사실 필요 없고 x축,y축으로 인접한 것 총 4개만 간선을 만들어 주면 된다. union-find로 관리하면서 거리가 가장 짧은것 부터 n-1개 간선 뽑으면 된다. 

위와 같은 방법으로 트리를 만들면 이제 lca 웰노운 문제가 된다. 정점 u부터 정점 v까지 경로상에 가장 가중치가 큰 간선을 구하면 되는 문제로 바뀌고 O(logn) 방법이 잘 알려져 있다. 모르면 공부해 보자.

나는 체력회복하는걸 고려안하고 거리로 생각해서 한 번 틀렸다. 


E번도 트리에서 으쌰으쌰하는 문제인데 보자마자 pbs(패러럴 바이너리 서치?)로 슥샥속이네 라고 생각했다. 가수 s[i]에 대해서 평균점수가 j를 넘는 최소시간 k[i]를 정의하고 k[i]의 범위 le[i],ri[i]를 정의하면 pbs로 뚝딲뚝 풀린다. pbs를 모른다면 공부해보자. 다른 풀이도 있는지는 잘 모르겠다. 

배열크기로 1번틀리고 목표치 초과인데 이상으로 생각해서 3번틀렸다.


F번은 주어진 히스토그램에서 L모양 최대 직사각형 만드는 문제이고 못 풀었다. 대충 생각해본 풀이는 임의의 한 수평선 잡아서 거기서 직사각형 그리고 그 직사각형 오른쪽 또는 왼쪽으로 최대 직사각형을 구해 연결하는걸 모든 수평선에 대해서 하면 그게 최대일 것 같은 느낌이 든다. 

그래서 이제 어떤 수평선 i의 왼쪽에 연결된 최대 직사각형을 cht로 구할 수 있을 것 같은데 새로운 수평선이 추가 될 때 마다 그 수평선 보다 높은 수평선들이 삭제되어야하고 해서 어떻게 하는지 잘 모르겠다. 동적 cht인가? 잘 모르겠다. 왠지 고민해도 이 문제는 못 풀것 같아서 ㅈㅈ쳤다.


집에서 예선 참가했는데 너무 더워서 죽을것 같다. 카페갈 걸 그랬다 ㅜㅜㅜ

본선 갈 수 있으면 좋겠다. 

고럼 이만 ~

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함