| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 204 | 56 | 50 | 38.168% |
KOI 도시는 도시를 동서로 가로지르는 큰 강을 중심으로 형성되어 있다. 강의 북쪽과 남쪽에는 각각 $N$개의 마을이 위치해 있다. 북쪽의 마을들은 하류에서부터 순서대로 $A_1, A_2, \ldots, A_N$ 과 같이 식별되며, 남쪽의 마을들은 하류에서부터 순서대로 $B_1, B_2, \ldots, B_N$ 과 같이 식별된다. 고로, KOI 도시에는 총 2ドルN$개의 마을이 존재한다.
KOI 도시의 사람들은 원래 뗏목을 타고 다니며 교류하였으나, 근대화가 진행되면서 강을 가로지르는 다리를 건설하게 되었다. KOI 도시는 하류에서부터 발전하였기 때문에, 맨 처음 건설된 다리는 마을 $A_1$ 과 마을 $B_1$을 이었다. KOI 도시의 사람들은 이렇게 건설된 첫 다리를 0ドル$번 다리 라고 부른다. 이후, KOI 도시는 추가적으로 1ドル$번 다리, 2ドル$번 다리, $\ldots,ドル 2ドルN-2$번 다리를 순서대로 건설하여, 총 2ドルN-1$개의 다리를 건설하였다.
0ドル$번 다리를 지은 이후, 모든 다리는 직전에 지은 다리와 인접한 위치에 건설되었다. 구체적으로, 모든 0ドル \leq i \leq 2N-3$ 에 대해서, 만약 $i$번 다리가 $A_x$ 마을과 $B_y$ 마을을 잇는다면, $i + 1$번 다리는 $A_x$ 마을과 $B_{y + 1}$ 마을을 잇거나, $A_{x + 1}$ 마을과 $B_y$ 마을을 잇는다. 두 경우 중 어떤 것이 결정되었는지는 길이 2ドルN-2$의 문자열 $S$에 기록되어 있다. 만약 $S[i] =$ 'A' 일 경우 $i+1$번 다리는 $A_x$ 마을과 $B_{y+1}$ 마을을 이으며, $S[i] = $'B' 일 경우 $i+1$번 다리는 $A_{x + 1}$ 마을과 $B_y$ 마을을 잇는다. $S$ 에는 정확히 $N-1$개의 'A'와 $N-1$개의 'B' 가 등장한다. 이에 따라 다음과 같은 사실이 성립함을 증명할 수 있다:
KOI 도시는 다리들을 보수하는 공사를 진행하려고 한다. 보수 공사는 2ドルN - 1$개 다리 중 몇 개의 다리를 선택해서 진행한다. 공사는 소음을 유발하기 때문에, 어떠한 마을에 대해 이 마을을 잇는 2ドル$개 이상의 다리가 동시에 공사의 대상이 되는 일은 피하려고 한다. KOI 도시는, 이 조건을 만족하면서 최대한 많은 다리에 공사를 진행하려고 한다. 또한, 향후 예상하지 못한 문제가 생길 수 있으니, 조건을 만족하면서 최대한 많은 다리에 공사를 진행할 수 있는 경우의 수를 10ドル^9 + 7$로 나눈 나머지를 계산하고자 한다. 두 공사가 다르다는 것은, 공사의 대상이 되는 다리의 집합이 다르다는 것으로 정의한다.
당신은 KOI 도시를 도와 이 두 값을 모두 계산하여야 한다. 하지만, 다리의 최대 개수만을 계산하였을 때도 부분 점수를 얻을 수 있다.
여러분은 아래 함수를 구현해야 한다.
array<int, 2> roadwork(string S)
제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.
'A'와 $N-1$개의 'B' 가 등장한다.| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | $N \le 2^1$ |
| 2 | 5 | $N \le 2^3$ |
| 3 | 6 | $N \le 2^5$ |
| 4 | 7 | $N \le 2^7$ |
| 5 | 8 | $N \le 2^9$ |
| 6 | 9 | $N \le 2^{11}$ |
| 7 | 10 | $N \le 2^{13}$ |
| 8 | 11 | $N \le 2^{15}$ |
| 9 | 12 | $N \le 2^{17}$ |
| 10 | 13 | $N \le 2^{19}$ |
| 11 | 15 | 추가적인 제약 조건이 없다. |
각 부분문제에서 다리의 최대 개수만을 올바르게 반환하였을 경우, 40%의 부분 점수를 얻는다.
$N = 2,ドル $S = $"AB" 인 경우를 생각해 보자. 그레이더는 다음과 같이 함수를 호출한다.
roadwork("AB")
아래 그림은 KOI 도시의 구조를 나타낸다.
0ドル$번 다리와 2ドル$번 다리를 공사할 경우 최대 2ドル$개의 다리에 공사를 진행할 수 있다. 2ドル$개의 다리에 공사를 진행하는 방법은 이것이 유일하다. 함수는 $[2, 1]$ 을 반환해야 한다. 만약 $[2, -1], [2, 0]$ 등을 반환할 경우, 다리의 최대 개수만을 올바르게 반환한 것으로 간주된다.
1ドル$개의 다리에 공사를 진행하는 방법이 3ドル$가지 있지만, 이 경우는 최대한 많은 다리에 공사를 진행하지 않기에 세지 않는다.
$N = 7,ドル $S = $"AABBAABBAABB" 인 경우를 생각해 보자. 그레이더는 다음과 같이 함수를 호출한다.
roadwork("AABBAABBAABB")
아래 그림은 KOI 도시의 구조를 나타낸다.
최대 6ドル$개의 다리에 공사를 진행할 수 있다. 그러한 경우의 수는 총 4ドル$가지이다. 함수는 $[6, 4]$ 를 반환해야 한다.
Sample grader는 아래와 같은 형식으로 입력을 받는다.
$i + 1$번째 테스트 케이스에서 roadwork가 반환한 배열을 $C[i]$라고 하자. Sample grader는 다음을 출력한다.
Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.
Olympiad > 국제정보올림피아드 대표학생 선발고사 > 2025 > 1차 선발고사 3번
C++17, C++20, C++23, C++26, C++17 (Clang), C++20 (Clang)