A, C는 많이 어렵지 않게 풀었다. B 풀이가 상상이 안되어서, B에 많은 시간을 사용했다. D는 B를 푼 이후 문제를 읽고 문제 풀이 전략을 구상하였는데, 아이디어만 남긴 채 다 풀지는 못 하였다. E1, E2는 문제를 읽지 않았다. A는 00:02에, C는 00:39에, B는 01:21에 풀었다. D는 콘테스트 종료 후에 풀었다. E1, E2는 풀지 못했다.
1542A Odd Set
두 수의 합이 홀수가 되기 위해서는 홀수와 짝수가 짝지어져야 하므로 홀수와 짝수의 개수가 각각 과 같은지 확인하면 된다.
1542B Plus and Multiply
문제에서 주어진 집합을 라고 하자. 이다. 다음을 관찰하자.
이다.
에 대해,
이다.
따라서 이다. 한편 모든 꼴의 수는 항상 와 같이 표현되므로 의 원소이고 이다.
을 늘려가며 이 음이 아닌 의 배수가 되는 이 존재하는지 확인하여 인지 판정할 수 있다.
1542C Strange Function
을 의 최소공배수라고 하자. 은 가 의 배수이면서 의 배수가 아닌 것과 동치이다. 으로 정의하자. 에서 의 배수의 개수는 이므로, 구하려는 답은
이다. 이때 이면 이다. 이를 만족하는 가장 작은 를 라고 하자. 식을 다시 써 보면
이고, 이는 쉽게 계산 가능하다.
1542D Priority Queue
각 + x 기호에 대해 이 가 답에 어떻게 기여하는지 상상하는 것이 하나의 풀이 전략이 될 수 있다. 각 에 대해, 배열 를 할당한다. 이는 우선순위 큐 에 현재 보다 먼저 나가는 원소의 개수를, 그러한 상황을 만드는 의 부분 문자열의 개수에 대응시킨다. 같은 값에 대해서는 나중에 들어온 것이 먼저 나간다고 가정할 수 있다. 주어진 명령들을 순서대로 순회하면서 + x 이전의 명령들과 + x 이후의 명령들에 대해 에 적절한 연산들을 취하여 가 그 목적에 맞도록 바꿀 수 있다. 에 남아있는 항을 모두 더하고 이를 와 곱하여 답을 저장할 변수에 더한다. 이를 모든 + x 명령에 대해 반복하여 답을 얻을 수 있다. 의 크기를 으로 잡으면, 이 방법의 시간 복잡도는 이 된다. 이므로 충분히 사용할 수 있는 풀이이다.
