-주의- 이 문서는 매우 불친절하기 때문에 궁금한 것이 있다면 댓글로 달아주세요.

이 문서는 답안 중 하나를 제시하는 것 뿐, 다른 답안이 있을 수 있다는 것을 염두에 두셨으면 좋겠습니다.

P = LCM(2, 3, ..., 1000) 이라고 정의합시다. 중국인의 나머지 정리에 의해, n은 다음과 같은 형태로만 나타납니다.

n = Pk - 1 (k는 정수)

이유를 생각해보면, n = -1일 때 성립하고, P = 0 (mod 2) ... P = 0 (mod 1000) 이기 때문입니다.

네. 뭔가 이상하다는 것을 느끼셨을 겁니다. n = -1일 때 성립하니까 답은 -1입니다.

추가로, P가 433자리이기 때문에, -1이 아닌 가장 짧은 n은 433자리입니다.

이 때문에 -1 이외에는 답이 될 수 없습니다.

실수 연산을 쓸 때는 조심해서 써야 한다는 것을 의도한 문제입니다.

math.h에 정의되어 있는 acos 함수에서 리턴값은 다음과 같습니다.

-1 <= x <= 1 : acos(x)

otherwise : NAN

정수 10만개를 실수 자료형을 사용하여 더하고 빼는 과정에서 오차가 발생하기 때문에,

모든 수의 총합이 이론적으로 정확히 -1인 경우에도 -1.000004342 와 같이 표현될 수 있습니다.

그리고 이 수는 -1보다 작기 때문에 acos의 값이 NAN이 되면서, assert문을 통과합니다.

즉, 정수 10만개의 총합을 100이나 -100으로 맞추고, 여러 번 실험하여 오차의 부호를 맞추면 풀리는 문제입니다.

자매품으로 sqrt 함수의 음수 처리가 있습니다.

문제 설명은 장황하지만, 결국 백트래킹 코드 반례데이터 만들기입니다.

코드를 잘 보면, 1번 정점부터 순서대로 색을 칠해보는 형태입니다.

정점이 최대 50개고, 정점이 많을수록 이득이니까 정점 50개짜리 그래프를 만드는 것이 좋겠습니다.

먼저 컴퓨터가 삽질을 많이 할 것 같은 계획을 세워봅시다.

계획: 컴퓨터가 5번 정점에서 색을 잘못 칠한 후 이것을 49번째까지 알아차리지 못하다가, 50번째에서 알아차리게 하자.

컴퓨터는 5번 정점을 수정하기 전까지 6~49번 정점을 열심히 다시 칠할 것이고, 이러면 시간초과가 날 것 같습니다.

저 계획을 성사시키려면 두 가지가 필요합니다.

1. 5번 정점을 잘못 칠할 것.
2. 6~49번 정점의 색으로 가능한 것이 여러개일 것.

제가 만든 그래프는 아래와 같습니다.

1~4번은 1~4번 색으로, 5번은 3번 색으로 칠해지기 때문에 50번을 칠할 수 없습니다.

6~49번 정점은 자유롭게 해 줘도 상관이 없습니다.

플로이드가 성립하는 이유에 대해 알면 쉽게 풀 수 있는 문제입니다.

플로이드 코드의 D[i][k] + D[k][j]에서 알 수 있듯, k는 최단경로의 중간에 거쳐가는 노드를 의미합니다.

k가 n인 경우를 처리하지 않았다는 것은, 최단경로의 중간에 n이 포함된 경우가 처리되지 않았다는 것과 같습니다.

이제 최단경로 9700개가 정점 n을 지나가게 그래프를 구성하면 답이 되겠습니다.

네. 정점 n에 다른 정점들을 주렁주렁 매달면 정확히 9702개만큼 다른 그래프를 만들 수 있습니다.

실수 오차에 대한 두 번째 문제입니다.

convex hull을 gram scan 방법으로 구할 때, atan2로 각도를 저장하여 정렬하는 것은 많이 불안정한 방법입니다.

atan2의 반환 자료형은 double이기 때문에,

atan2(1000000001, 1000000002) 와 atan2(1000000002, 1000000003)의 값은 정확하게 같습니다.

즉, (10억1, 10억2), (10억2, 10억3)은 atan2를 사용하는 경우 각도순 정렬이 불가능합니다.

최대한 std::sort를 틀려보이게 문제를 작성하려 했습니다.

문제에 나와있는 정렬 조건은 (0, 0)을 중심으로 하는 CCW와 형태가 동일합니다.

즉, 지구이가 해야 하는 일은 점 N개를 x축과 이루는 각도로 정렬하는 문제입니다.

먼저 이 문제는 (0, 0)이 입력으로 들어올 수 있으며, (0, 0)은 어느 위치에 있어도 문제가 없다는 것을 알아야 합니다.

정렬이 제대로 되어 있다는 것은 (0, 0)을 제외한 다른 모든 점들은 각도순 정렬이 되어있다는 것입니다.

(0, 0)이 정렬에서 미치는 영향은 이런 느낌입니다.

(0, 0), (0, 1), (1, 1) ; (0, 1) (1, 1)의 두 배열을 merge한다고 가정하면,

0 * y_j >= x_j * 0을 만족하기 때문에 두 번째 배열의 원소가 먼저 빠지게 되고,

(0, 1), (1, 1), (0, 0), (0, 1), (1, 1) 순서로 결과가 나오게 됩니다. 물론 정렬은 되어 있지 않습니다.

std::sort를 호출할 때 오퍼레이터 정의가 잘못되어있으면 런타임 에러를 내지만,

위와 같은 특수한 경우 런타임 에러도 안내고, 정렬도 안되는 희안한 경우도 있습니다.

조심하세요.

벨만포드 알고리즘에 대하여 알고 있다면, 매우 쉽게 풀 수 있는 문제입니다.

벨만포드 알고리즘은 최단경로를 구성하는 간선의 개수를 하나씩 늘려나가는 방식으로 동작합니다.

즉, 이 문제를 맞추기 위해서는 간선 V-1개짜리의 최단경로를 만들되, 음수사이클이 없는 그래프를 만들어야 합니다.

이것은, 직선그래프에서 모든 간선의 가중치를 -1로 하면 됩니다.

간선을 순서대로 갱신하기 때문에, 간선의 입력 순서를 신경써야 합니다.

다음과 같은 다항식을 찾으면 풀리는 문제입니다.

1. f(x) = 0 (mod 10억7)의 해집합에 29, 31, 37, 41, 43, 47, 53, 59, 61, 67가 포함.
2. f(x)의 모든 다항식 계수는 -25~25
3. f(x)의 차수는 30만 이하

1번을 해결하려면 f(x) = (x-29)(x-31) ... (x-67)을 하면 되겠습니다만, 2번 조건을 만족하지 않습니다.

위 다항식의 문제점은 29, 31, ..., 67이 25에 비해 엄청나게 크기 때문에, 최종 결과물의 계수 또한 엄청나게 큽니다.

반대로 생각해서, 곱하는 다항식의 계수를 +-1로 매우 작게 만들면 될 것 같지 않나요?

그래서 생각한 것은, x = p일 때 (x^a +- x^b +- 1) = 0이 되는 다항식 10개를 찾은 후, 곱하면 되겠습니다! 와아..

비둘기집의 원리에 의해, 적어도 100자리 정도에서도 답은 있기 때문에 이것이 최적의 방법은 아닙니다.

문제 코드 이름이 힌트입니다. pseudo prime으로 검색하면 많은 내용을 찾을 수 있습니다.

먼저, a^(x-1) = 1 (mod x)를 (x, a) = 1인 모든 a에 대하여 만족하는 수를 Carmichael number라고 부릅니다.

이것을 OEIS에서 검색하면, 이것 말고도 많겠지만, http://oeis.org/A033502 에 나온 수로 풀 수 있습니다.

하지만, 대회 시간 12시간에 약 2.5억까지 모든 수를 다 해보는 방식으로 해도 답을 구할 수 있습니다.

단순히 DFS를 구현한 후, 디닉으로 바꾸기 위해 BFS를 추가하는 형태의 코드입니다.

이런 식으로 잘못 구현하기 쉬울 것 같아서 문제로 만들어 봤습니다.

제 해답은, 완전그래프 구성하고 간선 가중치를 랜덤으로 배정하면 됩니다.

놀랍게도 매우 잘나옵니다.

먼저, 세제곱으로도 충분히 2억을 넘길 수 있습니다.

실제로 대회에서 맞은 4명 중 3명이 N^3 그래프를 구성하여 2억을 넘겼습니다.

하지만 네제곱이니까 문제를 내지 않았을까요.

그래프는 많이 복잡합니다. 그래도 한번 해봅시다.

정점 8개짜리 그래프입니다. 빨간 간선은 capacity 1짜리 간선입니다.

첫 번째 Blocking flow를 흘린 후 모습입니다. (역간선 중 쓸모없다고 판단되는 간선은 그리지 않았습니다)

두 번째 Blocking flow step입니다.

세 번째 Blocking flow step입니다.

그리고 쓸모없는 간선 몇개를 지우면 아래 그래프처럼 됩니다.

정점 X, Y를 각각 정점 248개짜리로 바꾼 후, source를 4, sink를 3으로 생각하고 재귀적으로 그래프를 구성해가면 됩니다.

추첨과 상품 증정은 ICPC 직후에 해보도록 하겠습니다.