어제 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의 범위는 오목 꼭짓점에서 정의 될 수 있다.따라서 모든 오목 꼭짓점에서 안되는 범위들을 모으고 ..