2021 한국 정보 올림피아드 1차 대회가 2021년 5월 15일에 온라인으로 진행되었습니다. 모두 수고하셨습니다.
1교시
1. 상금 배분
첫 문제를 푸는 데 생각보다 오래 걸렸습니다. 가능한 경우가 얼마 없으므로 모두 따져 주면 A팀이 이길 확률은 \(\frac{13}{16}\)이고 B팀이 이길 확률은 \(\frac{3}{16}\)입니다. 답이 13억 원임을 쉽게 알 수 있습니다.
2. 구슬 경로의 수
구슬이 지날 수 있는 서로 다른 경로의 개수는 '↙' 네 개와 '↘' 세 개를 배열하는 경우의 수와 같습니다. 그 값은 \({}_7\mathrm{C}_3=35\)입니다.
3. 동전과 확률
마찬가지로 모든 경우를 따져 보면 답은 6입니다. 저는 실수해서 틀렸습니다.
4. 발표 순서
열심히 따지면 답을 구할 수 있습니다. 과정은 다음과 같습니다.
· A로 시작하는 발표 순서는 \(5!=120\) 가지가 있습니다.
· B로 시작하는 발표 순서 또한 \(5!=120\) 가지가 있습니다.
· CA로 시작하는 발표 순서는 \(4!=24\) 가지가 있습니다.
· CBADEF는 그 다음 발표 순서입니다.
따라서 답은 265입니다.
5. 돌 무더기 게임
문제의 돌 무더기 게임은 '님 게임(Nim Game)'으로 알려져 있고, 많은 연구가 되어 있습니다. 일반적으로 이러한 상황에서, 돌 무더기의 돌의 개수를 모두 bitwise XOR한 값이 0이면 B가, 0이 아니면 A가 항상 승리한다고 알려져 있습니다. 이에 대한 증명은 관련 글이나 논문을 찾아보시기 바랍니다. 주어진 돌의 개수가 적으므로 모든 경우의 수를 따져서 답을 구할 수도 있습니다. \(1⊕2⊕3=0\)이므로 B가 항상 승리합니다.
6. 직소 퍼즐
튀어나온 부분의 개수가 서로 다른 조각은 서로 다른 형태이므로, 튀어나온 부분의 개수에 따라 서로 다른 형태의 조각의 개수를 셀 수 있습니다.
| 튀어나온 부분의 개수 | 서로 다른 조각의 수 |
| 0 | 1 |
| 1 | 1 |
| 2 | 3 |
| 3 | 4 |
| 4 | 3 |
| 5 | 1 |
| 6 | 1 |
따라서 서로 다른 조각은 모두 열네 개입니다.
7. 삼각형 위의 격자점
두 양의 정수 \(a\), \(b\)에 대하여 \((0,0)\)과 \((a,b)\)를 잇는 선분 위의 격자점의 개수는 경계를 포함하여 \(\mathrm{gcd}(a,b)+1\) 개입니다. 따라서 구하는 점의 개수는 \(\mathrm{gcd}(155,29)+\mathrm{gcd}(210,150)+\mathrm{gcd}(55,121)=42\) 개입니다.
8. 숫자 추측
모든 경우를 따져 정답을 찾을 수 있습니다.
| \(a\) | \(b\) | \(a+b\) | \(a\times b\) | 비고 |
| \(1\) | \(1\) | \(2\) | \(1\) | 곱이 유일하므로 불가능 |
| \(1\) | \(2\) | \(3\) | \(2\) | 곱이 유일하므로 불가능 |
| \(1\) | \(3\) | \(4\) | \(3\) | 곱이 유일하므로 불가능 |
| \(1\) | \(4\) | \(5\) | \(4\) | 가능 |
| \(2\) | \(2\) | \(4\) | \(4\) | 곱과 합이 서로 같으므로 불가능 |
| \(2\) | \(3\) | \(5\) | \(6\) | 곱이 유일하므로 불가능 |
| \(2\) | \(4\) | \(6\) | \(8\) | 곱이 유일하므로 불가능 |
| \(3\) | \(3\) | \(6\) | \(9\) | 곱이 유일하므로 불가능 |
| \(3\) | \(4\) | \(7\) | \(12\) | 곱이 유일하므로 불가능 |
| \(4\) | \(4\) | \(8\) | \(16\) | 곱이 유일하므로 불가능 |
따라서 \(a=1\), \(b=4\)이고, \(a^2+b^2=17\)입니다.
9. 항아리
흰색 돌의 개수가 짝수라면 흰색 돌을 둘씩 모두 꺼내어 \(\mathrm{jug}(b,w)=\mathrm{jug}(b+\frac{w}{2},0)\)과 같이 만들 수 있습니다. 이제 검은색 돌을 둘씩 꺼낼 수 있는 만큼 꺼내면 한 번 꺼낼 때마다 검은색 돌의 개수가 하나씩 줄어들고, 결국 \(\mathrm{jug}(b,w)=\mathrm{jug}(1,0)=B\)입니다. 한편, 흰색 돌의 개수가 홀수라면 흰색 돌을 둘씩 꺼낼 수 있는 만큼 꺼내어 \(\mathrm{jug}(b,w)=\mathrm{jug}(b+\frac{w-1}{2},1)\)과 같이 만들 수 있습니다. 이제 검은색 돌을 둘씩 꺼낼 수 있는 만큼 꺼내면 위와 같은 이유로 \(\mathrm{jug}(b,w)=\mathrm{jug}(1,1)=\mathrm{jug}(0,1)=W\)입니다. 따라서 일반적으로 흰색 돌의 개수의 기우성이 B와 W를 결정합니다. 자세히는, 흰색 돌의 개수가 짝수라면 B이고 흰색 돌의 개수가 홀수라면 W입니다. 따라서 답은 B, W, W입니다.
10. 중심 노드 찾기
중심 노드일 가능성이 없는 정점을 모두 색칠합시다. 처음에는 모든 정점이 색칠되지 않았습니다. 다음 과정을 거치면 \(n-1\)회의 질의를 통해 확정적으로 중심 노드를 찾을 수 있습니다.
1. 색칠되지 않은 서로 다른 두 정점 \(a\), \(b\)에 대하여 \(\mathrm{query}(a,b)\)를 질의합니다.
2. 질의의 답이 yes이면 정점 \(b\)의 진입 차수가 1 이상이므로 정점 \(b\)를 색칠합니다. 질의의 답이 no이면 정점 \(a\)의 진출 차수가 \(n-1\) 미만이므로 정점 \(a\)를 색칠합니다. 이 과정에서 반드시 하나의 정점이 색칠됩니다.
3. 위를 \(n-1\) 회 반복하면 색칠되지 않은 정점이 하나뿐입니다. 중심 노드를 찾았습니다.
그런데, 적어도 \(n-1\) 회의 질의는 거쳐야 합니다. 중심 노드를 확정하는 방법은 다음 두 경우 중 하나입니다.
중심 노드를 제외한 모든 정점이 중심 노드가 아님을 보이는 방법
중심 노드가 중심 노드가 맞음을 보이는 방법
첫 번째 방법으로는 중심 노드를 제외한 \(n-1\) 개의 정점이 중심 노드가 아님을 보여야 하므로 적어도 \(n-1\) 회의 질의가 필요합니다. 또한, 두 번째 방법은 중심 노드의 진입 차수가 0이고 진출 차수가 \(n-1\)임을 보여야 하므로 적어도 \(2n-2\) 회의 질의가 필요합니다.
따라서 답은 \(n-1\)입니다.
11. 두 번 이상 지나는 경로 세기
실제로, 절대 지나갈 수 없는 길을 제거하면 길은 이렇게 생겼습니다.
위에서, 빨간 길은 지나갈 경우 절대 문제의 조건을 만족할 수 없는 길입니다. 다음과 같이 잡겠습니다.
$$O_X=\{①,②\}$$ $$O_Y=\{③,④,⑤\}$$
경로는 ①, ②, ③, ④, ⑤ 중 둘 이상의 장소를 지나야 합니다. 다음과 같이 경우를 나누겠습니다.
1. \(O_X\)의 두 정점을 지나는 경우
불가능합니다. 경우의 수는 0입니다.
2. \(O_X\)에서 하나의 정점을 지나고, \(O_Y\)에서 하나 이상의 정점을 지나는 경우
\(O_X\)에서 하나의 정점을 지나는 경우의 수는 \(5\)입니다.
\(O_Y\)에서 하나 이상의 정점을 지나는 경우의 수는 \(10\)입니다.
곱의 법칙에 따라, 경우의 수는 \(5\times10=50\)입니다.
3. \(O_X\)의 정점은 지나지 않고, \(O_Y\)의 둘 이상의 정점을 지나는 경우
③과 ④를 지나야 합니다. 경우의 수는 \(3\)입니다.
따라서, 전체 경우의 수는 53입니다.
12. 사각형 세기
사각형을 놓치지 않게 주의하면서 세야 합니다. 결과는 다음과 같습니다
| 사각형 | 개수 |
 |
\(3\) |
 |
\(12\) (뒤집기 포함) |
 |
\(3\) |
 |
\(6\) |
 |
\(6\) |
따라서, 찾을 수 있는 직사각형은 모두 서른 개입니다.
13. 첫 월급
선물 상자를 \(i\) 개 구매하는 데 최소한 \(f_i\) 원이 필요하다고 합시다. 다음이 성립합니다.
$$f_i=\begin{cases}\infty&(i<0)\\0&(i=0)\\\mathrm{min}(f_{i-1}+175,f_{i-3}+400,f_{i-5}+700)&(\text{otherwise})\end{cases}$$
각각의 \(f_i\)의 값을 계산하면 다음과 같습니다.
| \(i\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) |
| \(f_i\) | \(175\) | \(350\) | \(400\) | \(575\) | \(700\) | \(800\) | \(975\) | \(1100\) | \(1200\) | \(1375\) |
위 표를 역추적하면 선물 상자를 하나씩 한 번, 셋씩 세 번 구매하면 모두 \(1375\) 원을 사용하여 열 개의 선물 상자를 구매할 수 있으며, 이가 최적입니다.
14. 하노이의 탑
별도의 설명이 필요 없습니다. 나이브하게 풀 수 있습니다. 움직임의 횟수를 최소화할 필요가 없으므로, 내키는 대로 진행할 수 있습니다.
15. 2등을 찾아라!
15. 2등을 찾아라!
다음과 같은 경우에는 학생이 2등을 할 수 없습니다.
· 간선을 거슬러 올라가 도달할 수 있는 정점이 두 개 이상입니다.
· 들어오는 차수가 0인 학생은 본인이 유일합니다.
정답은 다음과 같습니다.
| 1일차 | 2일차 | 3일차 | 4일차 |
 |
 |
 |
 |
| 1, 2, 3, 4, 5, 6, 7, 8 | 1, 3, 4, 5, 6 | 3, 5 | 3 |
16. 천사와 악마
이 문제도 설명할 게 별로 없습니다. 모든 천사와 악마에 대하여, 출발지로 가능한 정점의 집합의 교집합을 나이브하게 구해 주면 됩니다.
17. 단조증가 수열
기울기를 이용한 동적 계획법 최적화를 적용하는 대표적 문제입니다. 백준 온라인 저지에도 비슷한 문제가 있습니다.
\(f_{i,j}\)를 \(i\)째 수를 \(j\)로 바꿀 때, \([1,i]\)의 수들이 단조 증가하게 만드는 최소 연산의 수로 둡시다. 편의상 \(f_{0,j}=0\)으로 둡시다. 다음이 성립합니다.
$$f_{i,j}=min_{0\leq k\leq j}(f_{i-1,k})+|j-a_i|$$
\(i\)의 값을 정해 두고 위 함수의 개형을 그려 보면, 놀랍게도 그래프의 기울기가 항상 감소하다가 증가합니다. 그 까닭은 \(f_{i,j}\)는 V자 형태의 \(|j-a_i|\)들의 합이기 때문입니다. 추세를 따라가며 함수를 그려 나가면 \(f_{10,j}\)는 \(j=8\)일 때 \(19\)의 최솟값을 가짐을 알 수 있고, 역추적을 통해 문제의 답을 구할 수 있습니다.
18. 삼각형 게임
나이브하게 풀 수 있습니다.
19. 팀 구성
일반적으로, 이 문제는 트리에서의 동적 계획법을 통해 풀 수 있으나, 휴리스틱이 정해인 것 같습니다. 저는 실수해서 여러 개 틀렸습니다.
| 정답 | 실력의 합 |
 |
\(8\) |
 |
\(6\) |
 |
\(7\) |
 |
\(6\) |
 |
\(6\) |
 |
\(5\) |
 |
\(6\) |
 |
\(5\) |
 |
\(7\) |
 |
\(3\) |
20. 2행 정렬
마지막 문제 치고는 나이브로 풀립니다. 움직임의 횟수를 최소화할 필요가 없으므로, 적당히 적은 개수의 칸을 활용하여 나머지 칸을 정렬할 수 있습니다. 저는 부분 점수 긁고 순열 사이클 분할을 하다가 시간이 끝나서 못 풀었습니다.
2교시
약 45분 동안 세 문제를 풀었습니다. 모든 소스 코드는 C++17로 작성되었습니다.
1. 야구 시즌
문제
KOI 야구 리그에는 각각 \(M\) 개의 팀으로 이루어진 \(N\) 개의 지역 리그가 있습니다. 곧, 모두 \(NM\) 개의 팀이 있습니다. 이들이 시즌을 맞아 서로 다른 팀끼리 경기를 하기로 했습니다. 단, 하나의 지역 리그 안에서는 팀의 쌍마다 \(A(\geq1)\) 회, 서로 다른 지역 리그 사이에서는 팀의 쌍마다 \(B(\geq1)\) 회의 경기를 진행해야 합니다. 이때, \(1\) 이상의 정수 \(k\)에 대하여 \(A=kB\)입니다. 리그의 전체 경기 수가 \(D\) 개 이하가 되게 하면서 가장 많은 경기의 수를 알고 싶습니다. \(T\) 개의 각 테스트 케이스마다 경기의 수를 출력하는 프로그램을 작성해야 합니다.
$$1\leq T\leq1\,000$$ $$2\leq N, M, k\leq100$$ $$1\leq D\leq1\,000\,000\,000$$
풀이
문제를 잘 해석하면, 지역 리그 안에서의 경기의 수는 \(N\times\frac{M(M-1)}{2}\times KB\)이고 서로 다른 지역 리그 사이에서의 경기의 수는 \(NM\times\frac{M(N-1)}{2}\times B\)이므로 리그 전체 경기의 수 \(S=(N\times\frac{M(M-1)}{2}\times k+NM\times\frac{M(N-1)}{2})\times B\)임을 알 수 있습니다. 따라서, \(S'=N\times\frac{M(M-1)}{2}\times k+NM\times\frac{M(N-1)}{2}\)이라고 하면 \(B=\lfloor\frac{D}{S'}\rfloor\)일 때 \(S\)의 값이 \(D\)의 값을 넘지 않는 최댓값이 됩니다. 단, \(D<S'\)이면 \(B=0\)이고, 이는 조건 \(B\geq1\)에 맞지 않으므로 이때는 \(-1\)을 출력해야 합니다. 이걸 그대로 구현하면 테스트 케이스당 \(O(1)\), 모두 \(O(T)\) 시간 안에 문제의 답을 구할 수 있습니다.
#include <cstdio>
int t, n, m, k, d;
int main() {
for (scanf("%d", &t); t--; ) {
scanf("%d%d%d%d", &n, &m, &k, &d);
long long x = 1LL * n * m * (1LL * k * (m - 1) + 1LL * m * (n - 1)) / 2;
if (x > d) puts("-1");
else printf("%lld\n", d / x * x);
}
}
2. 초직사각형
문제
사차원 공간에 네 축상의 변의 길이가 각각 \(A\), \(B\), \(C\), \(D\)이고 \(ABCD\)의 부피를 가지는 초직사각형이 있습니다. 처음에 이 초직사각형의 각 변의 길이는 독립적으로 \(A_0\), \(B_0\), \(C_0\), \(D_0\)입니다. 이 초직사각형의 부피를 최대화하기 위하여 주어진 \(N\) 개의 카드 중 \(K\) 개를 골라 사용할 것입니다. \(N\) 개의 카드 중 \(i\)째 카드에는 문자 \(T_i\)와 양의 정수 \(U_i\)가 적혀 있는데, 이는 카드를 사용하면 변 \(T_i\)가 \(U_i\)만큼 길어짐을 의미합니다. 초직사각형의 부피를 최대화하는 카드의 사용 순서 목록을 출력하는 프로그램을 작성해야 합니다.
$$1\leq K\leq N\leq200\,000$$ $$1\leq A_0,B_0,C_0,D_0,U_i\leq1\,000\,000$$ $$T_i\in\{A,B,C,D\}$$
풀이
먼저, 네 축의 변의 길이가 독립적이고 덧셈의 교환 법칙이 성립하므로 카드의 사용 순서는 초직사각형의 부피에 영향을 주지 않습니다. \(N\) 개 카드의 목록에서 초직사각형의 부피를 최대화하는 몇 개의 카드 목록만 골라 내면 되빈다. 여기서, 현재 상태에서 카드를 사용했을 때의 초직사각형의 부피가 가장 큰 카드를 먼저 사용(시행)하는 탐욕법이 성립합니다. 그 이유는 다음과 같습니다.
1. 시행의 순서는 상관없습니다.
2. 같은 축 상에서 초직사각형의 크기를 바꾸는 시행은, 더 긴 길이를 늘리는 시행을 먼저 할수록 이득입니다.
3. \(A\)축과 \(B\)축의 길이를 늘리는 시행 중 가장 긴 길이를 늘리는 시행이 독립적으로 각각 \(\Delta_A\), \(\Delta_B\)라고 합시다. 또한, \(A\)축, \(B\)축, \(C\)축, \(D\)축의 길이가 각각 독립적으로 \(a\), \(b\), \(c\), \(d\)라고 합시다. \(C\)축과 \(D\)축을 아무리 늘려도 \((a+\Delta_A)bcd\)와 \(a(b+\Delta_B)cd\) 사이의 대소 관계는 바뀌지 않습니다. 따라서, \(\Delta_A\times b\geq a\times \Delta_B\)이면 \(A\)축의 시행을, 아니면 \(B\)축의 시행을 먼저 할수록 이득입니다. (비율로 생각할 수도 있습니다.)
4. (3)의 시행을 여러 번 할 때도 성립합니다. 만일 여러 번의 시행 중 한 번의 시행이 \(B\)축의 시행을 했을 때 최적이지만 탐욕법에 따라 \(A\)축의 시행을 했다고 가정합시다. (1)에 따라 시행의 순서가 상관없으므로 \(B\)축의 시행 이후에는 \(A\)축의 시행만 등장했을 것입니다. 그런데 마지막의 \(A\)축의 시행을 \(B\)축의 시행으로 대체했을 때 더 좋은 해가 구해지므로 모순입니다.
5. 일반적으로 \(X\)축과 \(Y\)축에 대하여도 성립합니다. (\(X\neq Y\), \(X,Y\in\{A,B,C,D\}\))
탐욕법을 적용하면 \(O(N\mathrm{log}N)\)의 시간 안에 문제의 답을 구할 수 있습니다. 실수 연산이나 임의 정밀도 연산 없이 깔끔하게 답을 구할 수 있습니다. 저는 처음에 여러모로 마음에 들지 않게 구현했기 때문에 남는 시간에 다시 깔끔하게 구현했습니다.
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int n, k;
long long a[4];
int _lt[4];
vector<int> v[4];
int main() {
scanf("%d%d%lld%lld%lld%lld", &n, &k, a, a + 1, a + 2, a + 3);
for (int i = 0; i < n; i++) {
char t;
int x;
scanf(" %c%d", &t, &x);
v[t - 'A'].push_back(x);
}
for (int i = 0; i < 4; i++) sort(v[i].begin(), v[i].end(), [](const int &a, const int &b) {
return a > b;
});
while (k--) {
vector<pair<int, int>> vt;
for (int i = 0; i < 4; i++) if (_lt[i] < (int)v[i].size()) vt.push_back({ i, v[i][_lt[i]] });
sort(vt.begin(), vt.end(), [](const pair<int, int> &x, const pair<int, int> &y) {
return x.second * a[y.first] > y.second * a[x.first];
});
a[vt[0].first] += vt[0].second;
printf("%c %d\n", 'A' + vt[0].first, vt[0].second);
_lt[vt[0].first]++;
}
}
3. 공통 부분 수열 확장
문제
두 문자열 \(X\), \(Y\)의 공통 부분 문자열 \(W\)가 주어집니다. \(W\)에 어떤 문자를 추가한 문자열 역시 \(X\)와 \(Y\)의 공통 부분 문자열이면, \(W\)는 확장 가능합니다. \(T\) 개의 각 테스트 케이스마다 문자열 \(W\)가 확장 가능한지를 판별하는 프로그램을 작성해야 합니다. (\(len(A)\)는 문자열 \(A\)의 길이입니다.)
$$1\leq T\leq100$$
모든 테스트 케이스에서 \(len(X)\)의 합은 200\,000 이하이다.
모든 테스트 케이스에서 \(len(Y)\)의 합은 200\,000 이하이다.
문자열 \(W\)는 두 문자열 \(X\), \(Y\)의 공통 부분 문자열이다.
$$X_i,Y_i\in\{a,b,c,\cdots z\}$$
풀이
문자열 \(W\)와 문자열 \(X\)를 왼쪽부터 비교하여 \(W_i\)와 \(X_j\)가 매치된다면 \(x\_left_i=j\)라고 하고, 문자열 \(W\)와 문자열 \(X\)를 오른쪽부터 비교하여 \(W_i\)와 \(X_j\)가 매치된다면 \(x\_right_i=j\)라고 합시다. 마찬가지로, 문자열 \(W\)와 문자열 \(Y\)를 왼쪽부터 비교하여 \(W_i\)와 \(Y_j\)가 매치된다면 \(y\_left_i=j\)라고 하고, 문자열 \(W\)와 문자열 \(Y\)를 오른쪽부터 비교하여 \(W_i\)와 \(Y_j\)가 매치된다면 \(y\_right_i=j\)라고 합시다. 또한, 편의상 \(x\_left_0=y\_left_0=0\), \(x\_right_{length(W)+1}=length(X)+1\), \(y\_right_{length(W)+1}=length(Y)+1\)로 두겠습니다. 그러면 다음 성질이 성립합니다.
$$x\_left_i\leq x\_right_i$$ $$y\_left_i\leq y\_right_i$$
공통 부분 수열 \(W\)가 확장 가능하다면, 적어도 하나의 \(i\)에 대하여 경계를 포함하여 \(X_{x\_left_i+1}\)과 \(X_{x\_left_{i+1}-1}\) 사이, 그리고 \(Y_{y\_left_i+1}\)과 \(Y_{y\_left_{i+1}-1}\) 사이에 공통된 문자가 하나 이상 존재합니다.
따라서, 정수 \(1\leq i\leq length(W)+1\)마다 문자열 \(X\)의 구간 \([x\_left_i+1,x\_left_{i+1}-1]\)와 문자열 \(Y\)의 구간 \([y\_left_i+1,y\_left_{i+1}-1]\)에 포함된 각 문자(a, b, …, z)의 개수를 각각 안다면 문제를 해결할 수 있습니다. 자세히는, 위 두 구간에 공통으로 포함된 문자가 하나 이상 존재한다면 문자열 \(W\)는 확장 가능합니다. 이는 두 문자열 \(X\)와 \(Y\)에 대하여 각각 \(l\), \(r\)을 두어 \(l\), \(r\)을 증가시키며 구간 \([l,r]\) 나타난 각 문자의 개수를 관리하는 방식으로 스위핑하여 선형 시간인 \(O(\sum(len(X)+len(Y)+26len(W)))(=O(26\mathrm{max}(len(X),len(Y))))\) 시간 안에 해결할 수 있습니다.
#include <cstdio>
#include <cstring>
int X, Y, W, k;
int t, x_left[200006], x_right[200006], y_left[200006], y_right[200006];
char x[200006], y[200006], w[200006];
int cnt1[26], cnt2[26];
int main() {
for (scanf("%d", &t); t--; ) {
scanf("%s%s%s", x, y, w);
X = strlen(x), Y = strlen(y), W = strlen(w);
k = 0;
for (int i = 0; i < X; i++) if (k < W && x[i] == w[k]) x_left[k++] = i;
k = 0;
for (int i = 0; i < Y; i++) if (k < W && y[i] == w[k]) y_left[k++] = i;
k = W - 1;
for (int i = X - 1; i >= 0; i--) if (k >= 0 && x[i] == w[k]) x_right[k--] = i;
k = W - 1;
for (int i = Y - 1; i >= 0; i--) if (k >= 0 && y[i] == w[k]) y_right[k--] = i;
for (int i = 0; i < 26; i++) cnt1[i] = cnt2[i] = 0;
int l1 = 0, r1 = -1;
int l2 = 0, r2 = -1;
for (int i = 0; i <= W; i++) {
int _l1 = (i ? x_left[i - 1] + 1 : 0), _r1 = (i < W ? x_right[i] - 1 : X - 1);
int _l2 = (i ? y_left[i - 1] + 1 : 0), _r2 = (i < W ? y_right[i] - 1 : Y - 1);
while (r1 < _r1) cnt1[x[++r1] - 'a']++;
while (l1 < _l1) cnt1[x[l1++] - 'a']--;
while (r2 < _r2) cnt2[y[++r2] - 'a']++;
while (l2 < _l2) cnt2[y[l2++] - 'a']--;
for (int i = 0; i < 26; i++) if (cnt1[i] && cnt2[i]) {
puts("1");
goto next;
}
}
puts("0");
next:;
}
}
후기
올해 정보 올림피아드는 1교시도, 2교시 문제도 좋은 문제들이 나온 것 같습니다. 1교시 문제는 예상과 다르게 꽤 쉬웠고, 2교시 문제는 브론즈, 골드, 골드로 예상되어 난이도 분포도 적절했던 것 같습니다. 그러나 아쉽게도 1교시에 실수를 많이 해서 모두 476.7 점으로 예상되어 금상은 못 받을 것 같습니다. 더 열심히 해서 2차 대회에서는 좋은 결과를 거둘 수 있도록 해야겠습니다.
결과
모두 476.6 점으로 에상 외로 금상을 받고 2차 대회에 진출했지만 아쉬운 마음을 감출 수 없습니다. 지인들의 상위 분포 비율로 추정했을 때 8등인 것 같습니다. (공동 1등의 분포 비율은 상위 약 \(0.133869\%\)입니다. 곧, 상위 \(x\%\)라면 \(\lfloor\frac{x}{0.133869}+\frac{1}{2}\rfloor\) 등입니다.) 전체 응시자 수는 747 명으로 추정됩니다.
| 분류 | 시상 비율 | 시상 인원(추정) |
| 금상 | 상위 \(1.5\%\) 이하 | \(11\) 명 |
| 은상 | 상위 \(7.5\%\) 이하 | \(45\) 명 |
| 동상 | 상위 \(25\%\) 이하 | \(130\) 명 |
| 장려상 | 상위 \(35\%\) 이하 | \(75\) 명 |
| 무상 | 상위 \(100\%\) 이하 | \(486\) 명 |
| 합계 | \(100\%\) | \(747\) 명 |
