티스토리 뷰

etc.

Code Monster 2017 본선 후기

킹갓제네럴충무공 박트리 2017.11.02 02:16

호다닥 갈기는 lg cns codemonster 후기이다.


상암 ddmc lg cns에서 11.1일날 했다. 작년과 비슷하게 올해도 수색역에서 건너편으로 넘어가는거 힘들었다.



코오오오오드으으 몬스터어어어! 


티셔츠 받고 갈아입고 과자 쿰척쿰척하고 환경세팅했다.

대회장은 3개인가 4개로 나뉘어져있는거 같았고 한 대회장에 20명 쯤 있는거 같았다. 8x3 24명이넹 대회장 3개인 듯

아무래도 한 곳에서 대회를 안하고 각 방에서 따로따로 치루니까 그냥 시험치는거 같았다. 스코어보드도 없고...



너무 갓갓들이 많은 방이었다. 


이런저런 설명듣고 점심 도시락 냠냠하고 12시 30분부터 4시간동안 대회가 시작되었다!


문제는 4문제 출제되었고 3번까지 1시간 대에 풀고 4번만 2시간 넘게 고민했는데 섭테 1만 해결하였다. 흐규흐규

수상인원이 14명인데 아마 만점이 입상컷인거 같다.


대략적으로 문제 소개 및 내가 접근한 방법을 적어보면


1번은 N(1e5)개의 선분의 길이가 주어진다.

이 선분들 중에서 4개를 선택해 사다리꼴을 만드는데 가장 둘레가 큰 사다리꼴의 둘레를 출력하는 문제이다.


선분 4개의 길이를 a,b,c,d라고 하고 a<=b<=c<=d 라고 정의 하였을 때

사각형을 만들기 위해서는 a+b+c>d 이어야 함은 자명하다. 

d를 밑변으로 하고 a를 윗변(?) 으로 하는 사다리꼴 형태를 생각해보자. 좌변을 b, 우변을 c라고 하였을 때

d선분 왼쪽 끝점에서 반지름 b인 원을 그리는데 오른쪽으로 길이가 a이고 d와 평행인 선분이 붙은 거니까 

왼쪽 끝점에서 오른쪽으로 a만큼 평행이동 하였다고 생각해도 된다.

그리고 d선분 오른쪽 끝점에서 반지름 c인 원을 그렸을 때 이 두 원이 교점이 존재하면 사다리꼴을 만들 수 있는것이다.

교점 존재 여부는 r'-r<=d<=r'+r, (r'>=r) 로 확인 가능하고 여기서 두 원의 중점 사이의 거리는 (d-a)이다. 

r'=c , r=b임은 (a<=b<=c<=d) 로 인해 자명하고

a+b+c>d 인 꼴에서만 사각형을 만들 수 있으므로, d-a<c+b 이고 우측 부등식을 만족한다.

또한 a+c<=b+d임은 (a<=b<=c<=d) 에서 유추해낼 수 있고, 따라서 c-b<=d-a 이므로 좌측 부등식을 만족한다. 

따라서 사각형을 만들 수 있으면 사다리꼴을 만들 수 있다.

가장 긴 선분부터 보면서 a+b+c>d 를 만족하면 답이다.

O(NlogN)


2번은 N(5000)개의 문자에서 K번 이상 등장하는 가장 긴 부분 문자열의 길이를 출력하는 문제이다.

카운트할 때 등장하는 구간이 겹치면 안 됨. ex) ababa 에서 aba는  1,3 에서 등장하지만 3에서 겹치니까 카운트는 1임 


웰노운이고 많은 풀이가 존재한다. 제일 쉬운 문제인 듯

나는 파라매트릭에 kmp 써서 길이 k를 정하고 찾을 문자열 정하고 kmp로 찾았다.

O(N^2logN)


3번은 N(1e6)일 동안 K(5e4)개의 물건? 을 사야한다. k일이 되는 날 i번째 물건의 가격은 a[i]*k +b[i] 이다.

1e6>a[i]>=0, 음수<b<양수(걍 쥰내큼 |1e12|인가?)  

1일부터 N일 동안 매일 1개씩 물건을 살 수 있는데, 그 날 가장 싼 물건만 살 수 있다.(여러개 있다면 그 중 아무거나)

N일이 지난후 K개의 물건을 살 수 있는지? 살 수 있다면 최소 가격을 구하는 문제이다.


문제 읽자마자 컨벡스헐트릭 문제 같았다. 각 1차함수를 y절편으로 소팅하였을 때

더 큰 y절편을 가지는 함수가 더 큰 기울기를 가진다면 가격이 역전될 가능성이 없다. 따라서 고려하지 않아도 되고

그렇다면 우리가 고려하는 함수들은 y절편이 증가함에 따라 기울기가 감소한다.

따라서 가장 y절편이 작은 1차함수에서 다른 함수와 교차 할때는 항상 절편순으로 교차한다.

따라서 O(N)으로 모든 일자에 대해서 가장 작은 값을 가지는 1차함수를 관리할 수 있고, 가격이 항상 증가하므로

구매할 수 있을 때 구매하고 제거하는 식으로 구현하면 여러개 있는 경우나 y절편과 기울기가 같은 경우도 예외처리 가능하다.

O(N+KlogK)


4번은 N(1e5)정점 M(1e5)양방향간선이 있고 임의의 두 쌍의 정점은 항상 도달가능하고
두 쌍의 정점을 연결하는 간선이 여러개 존재 할수도 있다.

여기서 mst(미니멈) 만들수있는 모든 경우에 대해서 임의의 두 리프노드 사이에 mst로 선택되지 않은 기존 그래프 G의 간선이 존재하는지 안하는지 구하는 문제이다.(만들수 있는 모든 mst에 대해서 두 리프노드 사이에 간선이 없다면 참이고, 아니라면 거짓임)

섭테 1은 모든 간선의 가중치가 다르고

섭테 2는 최대 2개만 같고

섭테 3은 최대 3개만 같다


섭테 1은 쉽게 해결가능하다 만들 수 있는 mst가 1개만 존재하므로 그냥 만들고 문제조건을 확인하면 된다. O(MlogM + N)

섭테 2를 해결하면 여기서 예외처리만 더하면 섭테3이 해결될거 같았는데 섭테2를 해결못했다. 흐어어어엉

가중치가 같은 간선 a, b에 대해서

a, b 둘다 mst에 사용되었다면 고려하지 않아도 된다.

a, b 둘다 mst에 사용되지 않았다면 고려하지 않아도 된다.

a또는 b만 사용되었다면 a,b는 서로 교체 가능하고 같은 사이클 내에 존재할 것이다.

mst하나 만들어 보고 여기서 교체 가능한 간선들을 교체해서 새로운 리프-리프 노드를 만들면 불가능이다.

대충 이 정도 생각해보고 모르겠어서 비벼볼까 싶어서 섭테2 받아서 교체가능한 간선들 수를 출력했는데 적긴한데 비빌만한 크기는 아니여서 또 다른 접근도 해보고 흐거ㅓ거거거거겅 했다.


4번에 대한 후문으로는 경우 구해서 백트래킹하면 된다는거랑 랜덤으로 그냥 선택해서 비비는거 있었고

제일 충격적이었던게 섭테 1을 해결한 코드 그냥 내면 3까지 다 뚫린다는 거였다. 예외가 존재 하는뎅..

추가적인 체점이 없었다면ㅠㅠ 그냥 내볼껄...

예외)

4 4

1 2 1

2 3 1

3 4 2

2 4 2

mst 하나는 가능하고 하나는 불가능하다.


총평으로는 문제 난이도가 아쉽다. 물데이터가 아쉽다.

노트북 너무 느리다. 비쥬얼로하다가 컴파일하는데 너무너무너무 오래걸려서 서브라임 켜서했는데 서브라임에서 컴파일하는것도 느리더라 그래서 cmd 켜서 컴파일 했다.

대회같은 느낌이 별로 없다. (노잼이었다는 뜻ㅎ)

음 그래도 기업에서 대학생 대상으로 대회를 열어준다는게 정말 고마운 경험을 시켜주는것 같다.


전리품)


블루투스 키보드이다.

키보드 더이상은~


댓글
댓글쓰기 폼