티스토리 뷰
이제 scpc도 3년 차!
1, 2, 4번은 오전에 문제 읽고 풀이가 바로 떠올라서 오후에 바로 구현하였고
3번은 처음에 2-sat인가 했지만 2-cnf식이 안 떠올라서 고민하다가 2-cnf식으로 변형이 되어서 2-sat으로 풀었다.
5번은 정말 도통 몰랐는데 6명 정도 만점을 받은 것 보니 갓 문제였던 것 같고 더 공부해야겠다!!
1번은 스택을 이용해서 풀었고
2번은 그리디를 이용했는데 반밖에 증명을 안 했다 더 생각 해봐야겠다.
3번은 전구가 켜저있거나 꺼져있을 때에 따라 스위치들의 2-cnf식을 세울 수 있고 따라서 2-sat으로 풀 수 있다.
4번은 주어진 단순다각형을 단조 다각형으로 판별할 수 없는 방향벡터 d의 범위는 오목 꼭짓점에서 정의 될 수 있다.
따라서 모든 오목 꼭짓점에서 안되는 범위들을 모으고 이 범위가 [0,2pi)를 다 덮는지 확인하고 답을 출력했다.
'etc. > 대회 후기' 카테고리의 다른 글
한국 대학생 프로그래밍 경시대회 인터넷예선 후기 (3) | 2017.09.26 |
---|---|
카카오 Code Festival 참가 후기 (5) | 2017.09.11 |
삼성 대학생 프로그래밍 경진 대회(SCPC) 2017 본선 후기 (4) | 2017.08.18 |
카카오 Code Festival 예선 참가 후기 (14) | 2017.08.05 |
삼성 대학생 프로그래밍 경진 대회(SCPC) 2017 2차 예선 후기 (9) | 2017.07.16 |
댓글