KimHwon

https://www.acmicpc.net/problem/13466

시작점과 정수 N, R개의 직선이 주어진다. 시작점에서 직선을 따라 가다가 교차점을 만나면 오른쪽으로 돈다. N번 회전을 했을 때 어느 직선에 있는지 찾는 문제다.

N이 10^10이나 되기 때문에 단순한 시뮬레이션은 어려울 것처럼 보인다. 그런데 직선이 100개로 매우 적기 때문에 같은 교차점을 계속 순회할 것이라고 추측해 볼 수 있다.

잘 생각해 보면 교차점에서 무조건 오른쪽으로만 회전하므로 지나간 경로는 볼록다각형 형태로 나타날 것이다. 100개의 직선으로 만들 수 있는 꼭짓점이 가장 많은 볼록다각형 즉, 최대한 다양한 교차점을 지나는 경로는 100각형 형태다. 따라서 최대 100개의 교차점만 지나간다는 뜻이고, 시작점으로 돌아올 때까지만 시뮬레이션을 할 수 있다.

R이 작으므로 O(R^2)으로 각 직선끼리의 교점을 다 구한다. 각 직선마다 어느 지점에서 누구와 교차하는지 저장해 두고, 그 교점으로 정렬해두면 쉽게 구현할 수 있다.(vector<Cross> adj[]) lower_bound() 또는 upper_bound()를 잘 활용하면 어떤 직선에서 교점을 알 때, 그 교점에 바로 왼쪽이나 오른쪽으로 인접한 다른 교점을 O(log(R))에 찾을 수 있다.(Cross getNext(const Cross& me, int& dir)) 찾은 새로운 교점에 연결된 다른 직선에 대하여, 같은 방식으로 인접한 또다른 교차점을 찾아 나가면 된다. 시작한 직선으로 돌아올 때까지를 한 사이클이라고 하면, 사이클의 N % (사이클 길이) 번째 직선이 답이다.

모든 교점에 대하여 인접한 교점을 찾는데 총 O(R log(R))이지만 맨 처음에 모든 직선에 대한 교점을 만드는데 O(R^2)이므로, O(R^2)으로 해결할 수 있다.

코드

www.acmicpc.net/problem/15004

시점과 종점, 여러 원들이 주어진다. 시점에서 원 내부만 지나면서 종점에 도착하고자 할 때 최단 경로의 길이 (또는 불가능한지)를 구하면 된다.

일단 자명한 점은 시점에서 종점으로 직선으로 가는 경우가 아니라면 최단경로는 무조건 원과 원 사이 교점을 지나야 한다는 것이다. 문제에 제시된 그림에 메모했다. (파랑)

잘 생각해보면 코너를 돌 때 최단으로 이동하는 방법은 코너에 최대한 붙어서 이동하는 것이다. 즉, 코너가 되는 지점인 교점을 지나쳐야 한다.

N이 25밖에 되지 않으므로 원들 사이 모든 교점을 구하고, 각 교점들과 시점, 종점을 모두 잇는 선분을 만든다. 선분을 따라 이동하는 최단 경로를 다익스트라 등으로 구할 수 있다. 여기서 각 선분이 가능한지 즉, 원 바깥으로 나가지 않는지 판정하는 것이 중요하다.

원과 원 사이 교점을 구하는 식은 여기를 참고하여 O(N^2)으로 모든 원 사이에 교점들을 다 찾았다.(tuple<int, Point, Point> intersect(Circle c1, Circle c2) 함수) 다시 N^2 = M개의 각 교점들을 O(M^2)으로 선분을 만들어보고 가능한지 체크한다.(bool incLine(Line ln, vector<Circle> &cir) 함수) 주의할 점은 시점에서 교점으로, 또는 종점에서 교점으로, 시점에서 종점으로 바로 갈 수도 있으므로 시점과 종점도 포함해서 생각해야 한다. 선분을 만들 수 있다면, 그래프에 간선으로 추가하고 다익스트라를 사용해서 최단 경로를 찾는다.(ld dijkstra(ll start, ll end))

최종적으로 시간복잡도는 O(ElogV)인데, 여기서 E = M^2 = N^4, V = N^2 이므로 O(N^4 log N)이다.

코드

역시 에듀는 마음이 편안하다. 하지만 그렇다고 엄청 잘 풀지는 못해서 블루 복구는 못했다.

A. Review Site

upvote하는 사람과 downvote하는 사람은 고정이고, 영화를 보지 않은 사람을 최대한 upvote쪽으로 몰아야 한다. 서버가 2개이므로, 한 서버 쪽으로 upvote하는 사람을 다 보내고 다른 서버 쪽으로는 downvote하는 사람을 다 보내버리자. 그리고 영화를 보지 않은 사람을 upvote만 있는 서버로 보내면, 전부 upvote를 하게 된다.

B. GCD Length

gcd(x, y)를 g, x/g = x', y/g = y'이라고 하자. x', y', g가 모두 소수라면 다른 예외사항 없이 항상 조건을 만족한다. 따라서 g를 c자리 소수, x'을 a-c+1자리 소수, y'을 b-c+1자리 소수로 정한다. 이 때, 곱셈을 해서 자리올림이 생기면 안되므로 가장 작은 소수로 정해야 할 것이다. 1~9자리 가장 작은 소수는 울프람알파로 찾아서 하드코딩하고, x'과 y'이 같으면 gcd가 달라질 수 있으므로 x'을 가장 작은 소수, y'을 두번째로 작은 소수로 정한다.

C. Yet Another Card Deck

같은 숫자가 여러 개 있어도, 가장 위에 있는 숫자만 움직이므로 인덱스만 저장해두고 좌표압축으로 줄여줄 수 있다. 압축한 수열을 b라고 하면 adj[i]를 b_i 앞에 있는 원소라고 정의해보자.

만약에 쿼리가 3이 들어왔다면, 저장해 두었던 3의 (압축하기 전) 인덱스를 출력한다. 그리고 맨 앞으로 옮겨야 하는데, 인접 리스트로 모델링하면 손쉽게 핸들링할 수 있다. 그림에서처럼 3의 앞에 있는 원소는 adj[3]의 멤버들(초록)이다. 이들 뒤에 있던 3이 앞으로 이동했으므로, 각 멤버들의 인덱스를 +1 하고, adj[]도 업데이트해준다.(파랑)  각 쿼리에 대해 같은 방식으로 계속 진행해 나가면 된다.

D. Min Cost String

인접한 두 문자 한 쌍을 한 요소로 생각해보자. 이 한 쌍을 간선으로 모델링해보면 다음과 같다.

세 개의 문자가 있을 때 나올 수 있는 모든 요소들은 aa, ab, ac, ba, bb, bc, ca, cb, cc로 총 9가지이다. 이들을 간선으로 만들면 루프+완전그래프 형태가 된다.(파랑)  따라서 문제를 재해석하면 루프+완전그래프에서 가능한 같은 간선을 지나지 않으면서 순회하는 방법을 찾는 문제가 된다. 각 정점마다 짝수개의 간선이 추가되므로 이 그래프는 무조건 한붓그리기가 가능하고, 오일러 경로가 답이 된다. dfs등으로 오일러 경로를 따라가면서 문자열을 만들고 조건에 맞는 길이만큼 출력하면 된다. 문자열보다 더 긴 길이가 필요하면, 문자열을 한 번 순회하는 것을 한 사이클로 생각하고 여러 번 순회하면 된다.

아이디어는 금방 떠올랐으나 오일러 경로를 순회하는 방법을 몰라서 복잡하게 구현했는데, Hierholzer's Algorithm이라는 dfs 비스무리한 아주 웰노운한 방법이 있다고 한다.

E. Colorings and Dominoes (업솔빙)

Green55의 해설을 듣고서야 이해했다. 풀이는 다음과 같다. 먼저 어떤 연속된 두 블록을 딱 고정해놓고 생각해보자. 세로로 두 칸을 고정했다면 파란색으로 칠하고 1점을 얻는게 확정이고, 나머지 칸은 상관이 없다. 따라서 모든 경우의 수에서 저 두칸에서 얻을 수 있는 점수는 2^(남은 o의 개수)이다. 당연히 서로 겹치는 사건이 존재하는데, 여기서 "가로 두 블록을 R로 고정했음"이라는 사건과 "세로 두 블록을 B로 고정했음"은 겹치지 않으므로 서로 독립적이다. 왜냐하면 어떤 한 칸이 가로 두 블록을 채우면서 세로 두 블록을 채울 수는 없기 때문이다. 그러면 결국 겹치는 사건들은, 연속되게 존재하는 칸에서만 발생한다는 것을 알 수 있다. 그럼 결국 우리가 궁금한 것은 "n칸이 연속되게 존재할 때, 이 칸에서 얻을 수 있는 점수의 합"이 된다. 백트래킹으로 완전탐색을 짜서 돌린 후 oeis에 치면 예쁜 점화식이 나오니까 가져다 쓰자. 찾은 점화식을 f(n)이라 하면, 결과적으로 답은 f( (연속된 o의 갯수) - 1 ) * 2^( (o의 총 갯수) - (연속된 o의 갯수) ) 의 합이 된다.

애초에 겹치는 사건 분류를 못해서 풀진 못했지만, oeis를 활용한 답이라니 정신이 혼미해진다. 에디토리얼 뜨기 전에 댓글들을 살펴보니 다들 oeis로 풀은 것 같았다. 에디토리얼의 정해는 마찬가지로 완전탐색 돌린 후, 규칙을 잘 찾으란건데... 확률이 1/4, 1/4 - 1/8, 1/4 - 1/8 + 1/16, 1/4 - 1/8 + 1/16 - 1/32, ... 이런 형태로 나타난다고 한다.

업솔빙 도중에 오버플로우가 안잡혀서 여러 번 틀렸는데, 템플릿을 구해서 사용했더니 바로 AC 받았다.

어려웠고 결과적으로 망했다. 역시 외부 연계 라운드는 무섭다. 민트로 똑떨함

A. Array and Peaks

일단 가능한 많은 peak이 존재하려면 peak 좌우에 더 작은 값들이 위치해야 한다. 그러면 한칸 걸러 한칸씩 peak이 등장하는 상태가 최대이고, 따라서 최대 floor( (N-1)/2 )개의 peak이 존재할 수 있다. 반대로 가장 적게 peak이 존재하는 경우는, 정렬된 상태면 하나도 없는 상태가 된다. 주어진 peak 갯수만큼, 최대로 만드는 전략으로 채운다. 빈 자리들에 오름차순으로 남은 수들을 채워 넣으면 된다.

B. AND Sequences

제일 극단적인 케이스를 생각해보면 a1 = a2 & ... & an 또는 a1 & ... & an-1 = an 일 것이다. 그런데 and 연산을 잘 생각해보면 비트가 꺼질 수는 있어도 켜질 수는 없다. 즉, a1 = a2 & ... & an 이면서 a1 & ... & an-1 = an를 만족하려면 a2 & ... an-1을 a1 또는 an과 and 연산 했을때, a1이나 an의 비트를 꺼서는 안된다. 따라서 a1 = an이 만족하고, a1 = an = a1 & ... & an-1 = a2 & ... & an 이다. a1 & ... & an-1 = a2 & ... & an 이면 a1 & ... & an = a1 & ... & an-1 = a2 & ... & an 이다.
여기까지 관찰을 하고, 구현을 하면 된다. a1 & ... & an을 구하고, 각 원소의 등장 횟수를 센다. a1과 an을 고정하고 a2~an-1에 잘 채워 넣는다고 생각해보면, a1과 an에 하나씩 원소를 배정해보면서 구할 수 있다. 어떤 원소가 2개 이상이면서 a1 & ... & an와 같으면 (즉, a1 = an = a1 & ... & an-1 = a2 & ... & an) 조건에 일치한다. 이 상태의 경우의 수는 (cnt)P(2) * (N-2)! 이다. 페르마 소정리 등을 사용해 경우의 수를 잘 계산하면 된다.

분명 B번인데 뭔가 잘못돼가고 있다는 느낌이 들었다... 체감은 한 C번인데 그냥 A번 풀지 말고 탈주할까 싶었다.

C. Add One (업솔빙)

각 숫자들이 변하는 형태는 독립적이므로, 따로 떼어놓고 생각해도 된다. 또한 어떤 숫자 'k'는 '0'이 k번 연산을 한 후와 동치이므로, 0으로 시작할 때의 규칙만 찾으면 된다. 완전탐색 코드를 짜보면 증가량이 이항계수 모양으로 나타난다... 까지 관찰을 하고 못풀었다.
Green55의 풀이는 다음과 같다. 여기서 '0'은 10번 연산을 하면 '1' 과 '0'으로 쪼개지니까 ('0'이 m초 지난 자릿수) = ('1'이 m-10초 지난 후 자릿수) + ('0'이 m-10초 지난 후 자릿수) 이다. ('1'이 m-10초 지난 후 자릿수) 는 위에서 말했다시피 ('0'이 m-9초 지난 후 자릿수) 이다. 그러면 ('0'이 m초 지난 자릿수) = ('0'이 m-9초 지난 후 자릿수) + ('0'이 m-10초 지난 후 자릿수). 이를 dp식으로 표현하면 dp[m] = dp[m-9] + dp[m-10]이다. 그에 더해, naive한 수열이 이항계수 비스무리한 형태면, 점화식이 선형일 확률이 매우 높으므로 벌래캠프로 해결할 수 있다.

대충 규칙이 있을거라곤 생각했지만, DP를 확실히 못하긴 한다. 연습 좀 더 해야겠다.

overflow에 안전한 int 자료형

struct mint {
    int val;
    mint() { val = 0; }
    mint(const ll& v) {
        val = (-MOD <= v && v < MOD) ? v : v % MOD;
        if (val < 0) val += MOD;
    }

    friend ostream& operator<<(ostream& os, const mint& a) { return os << a.val; }
    friend bool operator==(const mint& a, const mint& b) { return a.val == b.val; }
    friend bool operator!=(const mint& a, const mint& b) { return !(a == b); }
    friend bool operator<(const mint& a, const mint& b) { return a.val < b.val; }

    mint operator-() const { return mint(-val); }
    mint& operator+=(const mint& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
    mint& operator-=(const mint& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
    mint& operator*=(const mint& m) { val = (ll)val*m.val%MOD; return *this; }
    friend mint ipow(mint a, ll p) {
        mint ans = 1; for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans;
    }
    friend mint inv(const mint& a) { assert(a.val); return ipow(a, MOD - 2); }
    mint& operator/=(const mint& m) { return (*this) *= inv(m); }

    friend mint operator+(mint a, const mint& b) { return a += b; }
    friend mint operator-(mint a, const mint& b) { return a -= b; }
    friend mint operator*(mint a, const mint& b) { return a *= b; }
    friend mint operator/(mint a, const mint& b) { return a /= b; }
    operator int64_t() const { return val; }
};