오늘은 카카오 코드 페스티벌이 있었다. 1시부터 7시까지 6시간 동안 6문제를 푸는 온라인 예선전이었다. 문제를 푸는 방식이 탑코더와 비슷하게 함수를 구현하는 방식이었다. 채점환경도 clang이고 약간 낯선 환경이었지만 뭐 크게 상관없었다. 6문제를 A, B, C, D, E, F로 보면 난이도는 A < B < E < D < F < C 순으로 보인다. C가 의외로 생각해줘야 하는 예외가 많고 F는 비교적 풀이만 생각해내면 구현은 어렵지 않을 것 같았다. 대회 결과는 { A,B,C,D,E } 5문제를 해결하였고, 아마도 본선에 진출할듯싶다. 간단하게 풀이를 적어보자면 A. 2차원 맵에서 색칠된 부분이 몇 개인지 최대로 색칠된 영역은 몇 칸인지를 구하는 문제였다. 간단한 2차원 플러드필 문제이다. B.2차원 ..
어제 scpc 2차 예선을 봤다.1번 문제 읽고 이건 나중에 풀어야겠다 싶어서 2번을 읽었다.열심히 오래 달리는 문제였는데 마침 이번 주에 확장된 유클리드 호제법 문제를 풀면서 디오판토스 방정식을 푸는 걸 정리해둬서 그걸 이용해서 풀었다.그리고 3번을 읽고 흐음 서브테케는 할 수 있을 듯 해서 다시 1번을 돌아가 1번을 제대로 읽고 점화식을 조금 적어보니까 6가지 상태에서 (A->B, A->C, B->C, B->A, C->B, C->A) 마지막 단어에 대한 정의가 내려지기에 그걸 이용해 풀었다.다시 3번을 대충 O(240(n+m)logn) 복잡도에 풀어서 냈는데 아무래도 해쉬맵을 이용하고 복잡도 자체가 너무 크기에 불가능한 방법이었던 것 같다. 47점을 긁고 10번 제출이 끝날 때까지 이런저런 최적화를 ..
이제 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의 범위는 오목 꼭짓점에서 정의 될 수 있다.따라서 모든 오목 꼭짓점에서 안되는 범위들을 모으고 ..