Codeforces Round #305 (Div. 1)

어쩌다 보니(?) 에디토리얼을 쓰게 되었습니다.

처음으로 코드포스에서 2위를 하고, IGM이 되었습니다. 2015 IOI에서도 이 정도로 할 수 있었으면 좋겠습니다.

배점이 750-1000-1750-1750-2500이었습니다. A는 현재까지 본 1A 문제들 중 두 번째로 어렵고, C가 D보다 어렵다고 느꼈습니다.

문제를 풀기만 해서 풀이는 처음 써 봅니다. 즐겁게 감상해주세요 :)

A - Mike and Frog

h=a가 되는 최초의 시각을 p, 그 다음으로 h=a가 되는 최초의 시각을 q라고 합시다. 그러면 시각 th=a라는 것과 적당한 음이 아닌 정수 s에 대하여 t=p+s(q-p)라는 것이 동치임을 알 수 있습니다.
따라서 h_1,a_1에 대한 p_1,q_1h_2,a_2에 대한 p_2,q_2를 구한 뒤, 음이 아닌 정수 s_1,s_2에 대하여 t=p_1+s_1(q_1-p_1)=p_2+s_2(q_2-p_2)를 만족하는 최소의 t가 답이 됩니다. p_1,q_1,p_2,q_2는 최대 2m이고, 최소의 t는 연립합동식을 해결함으로써 구할 수 있습니다. 총 시간복잡도는 O(m)이 됩니다. 몇 가지 예외(q가 존재하지 않는 등)에 대해서는 따로 처리를 해 주어야 합니다.
이 문제에서 답이 32-bit integer를 넘어갈 수 있기 때문에 64-bit integer 등을 사용해야 합니다.

B - Mike and Feet

문제에서는 크기가 x인 그룹들 중 대해 최대 strength를 묻고 있지만, 저는 반대로 strength가 a_i 이상인 가장 큰 그룹을 찾는 식으로 접근했습니다.
a_i가 큰 순서대로 보면서, 현재까지 나온 수들로 이루어진 그룹들 중 i를 포함하는 가장 큰 그룹을 찾습니다. 이를 위해서 Union-Find 자료구조를 사용했습니다. 만약 i-1이 이전에 나온 수라면 i-1i를 합치고, i+1이 이전에 나온 수라면 i+1i를 합칩니다. 이를 수행한 뒤 i가 포함된 Union의 크기가 곧 i를 포함하는 가장 큰 그룹의 크기입니다. Union의 크기와 a_i를 기록한 뒤, 마지막에 정리하여 출력해주면 됩니다. 총 시간복잡도는 O(n \log n)이 됩니다.

C - Mike and Foam

포함-배제의 원리와 a_i의 소인수가 최대 6개라는 점을 이용해서 풀었습니다.
먼저 1 이상 500,000 이하의 모든 수에 대하여 소인수의 개수가 짝수인지 홀수인지를 판별합니다. 이는 에라토스테네스의 체를 변형하여 빠른 시간 안에 구할 수 있습니다. 쿼리가 들어올 때마다 포함-배제의 원리를 이용하여 답을 구할 수 있습니다. 예를 들어 새로 추가되는 수가 10이라고 하면, 이는 소인수가 2와 5 두 개임을 알 수 있습니다. 그러면 서로소인 쌍의 개수는 예전에 추가된 수 중 (1의 배수의 개수)-(2의 배수의 개수)-(5의 배수의 개수)+(10의 배수의 개수)만큼 증가합니다. 이를 배열을 만들어 세고, a_i의 소인수가 최대 6개이므로 2^6=64번의 참조로 쿼리의 답을 구할 수 있습니다.

D - Mike and Fish

x좌표가 같은 점들에 대해서 간선을 잇지 않은 두 점끼리 간선을 가능한 한 많이 이어줍니다. 예를 들어 x좌표가 3인 점들의 y좌표가 2, 5, 6, 8, 9라면 2와 5, 6과 8 간에 간선을 이어줍니다. (2와 8, 6과 9를 이어도 상관없습니다) y좌표가 같은 점들에 대해서도 똑같은 작업을 해 줍니다. 이렇게 만들어진 그래프는 이분그래프임을 알 수 있습니다.
여기서, 아직 방문하지 않은 임의의 점을 잡고 DFS를 합니다. 깊이가 홀수이면 붉은색을, 짝수이면 푸른색을 칠합니다. 이를 모든 점을 다 방문할 때까지 반복합니다. 이분그래프이므로 이렇게 색을 칠했을 때 인접한 두 정점 간에는 색이 다르다는 것을 알 수 있습니다. 또한 x좌표 또는 y좌표가 같은 점들 간에 간선을 가능한 한 많이 이었기 때문에 붉은색 점과 푸른색 점의 개수 차이가 많아야 1임을 알 수 있습니다. 총 시간복잡도는 O(n)입니다.

6개의 댓글이 있습니다.
  • JongMan
    JongMan

    IGM 멋져요!


    2년 전 link
  • username
    username

    크으 IGM 크으으으


    2년 전 link
  • Namnamseo
    Namnamseo

    IGM 멋져요!!


    2년 전 link
  • VOCList
    VOCList

    ㅋ ㅑ


    2년 전 link
  • kcm1700
    kcm1700

    IGM! 축하해요!


    2년 전 link
  • restart
    restart

    C, D코드를 참조했는데 정말 명확하고 간단하게 문제를 해결하시더라구요! 문제풀이 시간도 굉장히 짧구요.. 특히 D는 Editorial보다도 간명한 해법이네요! 많이 배웠습니다.


    2년 전 link
  • 댓글을 남기시려면 로그인하세요.