대회는 말렸습니다. 기존처럼 2시간 동안 문제를 보면서 풀이 2개와 유사풀이 2개를 생각했는데, 1번 2번을 푼 뒤 3번과 5번의 유사풀이를 구현하고 실패하다 보니 어느새 시간이 거의 끝나 있었습니다. 1번: 트리의 경로 a,b에 있는 간선들에 1을 추가해야 하는 쿼리가 주어지는데, 트리를 적절히 만들어서 모든 간선의 값이 짝수가 되게 하도록 해야 합니다. 쿼리들을 간선으로 표현했을 때, 모든 정점의 degree가 짝수이면 됩니다. 홀수인 경우가 있으면 정점에서 뻗어나가는 간선들 중에 어느 하나는 홀수여야 하고, 그런 경우가 없으면 잘 만들어 줄 수 있다. 2번: 어떤 수열의 부분수열 중 모든 원소가 K 이하인 것의 개수를 구하는 쿼리를 여러 번 해야 한다. 이는 유니온 파인드를 사용해 해결할 수 있다...
APIO 2022
이번 APIO는 흥미로운 문제들이 많이 나왔던 대회입니다. 저는 100+60+100=260점을 획득하여, 공동 1등을 하였습니다. A. Mars 이번 대회 문제들 중에서 개인적으로 가장 재미있었던 문제입니다. 컴퓨터에 제약이 있는 흥미로운 문제라는 점에서 IOI 2021 레지스터랑 비슷한데, 안 말려서 다행입니다. 문제 요약: 0과 1로 된 2n+1*2n+1 크기의 정사각형 격자가 주어지는데, 이 격자의 1로 된 연결 요소의 개수를 구해야 한다. 이렇게 하면 너무 쉽기 때문에, 컴퓨터에 제약이 있다. 컴퓨터의 메모리는 2n+1*2n+1 크기의 정사각형 격자이고, 한 칸에 100비트만 저장할 수 있다. 연산의 순서에도 제약이 있는데, 이 컴퓨터는 메모리를 위쪽부터 아래쪽, 왼쪽부터 오른쪽 순서로 수정하는 ..
나는 처음 1시간 동안 문제를 읽고 생각한 뒤, 예상 난이도를 결정하고 문제를 풀기 시작하는 스타일인데 문제를 본 결과 1번은 풀 수 있어 보였고, 2번도 잘 생각하면 풀 수 있어 보였지만, 3번은 잘 생각이 나지 않았다. 그래서 1번을 푼 뒤 2번을 생각하고, 3번은 마지막에 긁기로 했다. 1번은 난이도 순서대로 정렬되어 있는 책 N개 중 K개를 골라서 책의 난이도 합이 A 이상 2A 이하가 되도록 해야 하는 문제인데, 책의 난이도는 S번만 볼 수 있다. 경우의 수는 NCK개가 있었는데, 이를 다 볼 수는 없으므로 2가지로 나누어서 풀었다. 1.가장 작은 거 K-1개와 합쳤을 때 A 이상이 되는 가장 작은 책 하나를 골라, K개를 만든다. 2.1번에 해당되는 책이 없을 경우, 가장 작은 거 K-1개와 ..
57분만에 올솔을 해서 67등을 찍었다. 1. Double or One Thing 어떤 경우에 두 글자를 쓰고, 어떤 경우에 한 글자를 써야 할까? 두 글자를 쓰려면, 뒤에 오는 문자가 결정하는 문자보다 커야 한다. 뒤에 오는 문자가 결정하는 문자보다 작으면 한 글자를 쓰면 된다. 그러면 같은 경우에는 어떻게 해야 할까? 같은 경우에는 다다음 글자, 다다다음 글자......을 보다가 다른 문자가 나오면 결정하고, 뒤의 모든 문자가 같으면 한 글자만 쓰면 된다. #include using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int T; cin >> T; int tc = 0; while (T--) { ..
국가대표가 된 기념으로 선발고사 후기를 써봅니다. 최종 성적: 1차 1위, 2차 3위, 종합 1위로 국가대표에 선발이 되었습니다. 이 글이 선발고사 전략을 세우는 데 도움이 되기를 바랍니다. 문제의 자세한 풀이는 나와있지 않지만, 약간의 스포는 있습니다. 전략: 시작 후 한 시간까지 문제를 읽으면서 긁을 수 있는 섭테나 풀 수 있는 문제를 파악한 뒤에, 이를 얻을 수 있는 점수가 큰 순서대로 짜는 것 1차 선발고사: 시작 후 1시간 정도: 모든 문제를 읽어 보았다. 1번: 최댓값이라 되어 있는 부분을 합으로 잘못 읽어서, 루트질로 뚫지 않으면 어렵다고 생각했다. 2번: 문제를 보자마자 구현이 쉽지 않다는 생각이 들었지만, 39점 풀이는 생각을 할 수 있었다. 3번: 여러 가지 경우의 수를 따져야 하는 매..
우선 몇 달 동안 글을 안 써서 죄송합니다. 대회 결과: 총 7솔 3틀이였고, D번 문제를 퍼솔했다. 꽤 잘 본 편이라고 생각한다. 0:00~0:03 퍼솔을 하고 싶어서 D번 문제를 먼저 봤다. 문제를 보자마자 떠오른 관찰은 정점 번호가 1018 이상이면 연산이 L이냐 R이냐는 필요가 없고, 개수만 필요하다는 것이였다. 이를 이용해서 정점 번호가 260이 넘으면 정점 번호를 260 이하로 만들기 위한 최소 U 연산 수를 저장했고, 최소 U 연산 수가 0인=정점 번호가 260 이하인 경우는 정점 번호를 그냥 저장했다. #include using namespace std; #define int long long signed main() { int N, M; cin >> N >> M; string s; cin..
Codeforces Round #754 (Div. 2)
0:00~0:01 A번을 생각했다. 수 하나를 늘리고 다른 수를 줄이는 연산으로는, 합이 원래 a,b,c와 같은 모든 a,b,c의 쌍을 만들 수 있다. 만약 a+b+c가 3의 배수이면 a+c=2b, 아니면 a+c=2b±1의 꼴로 만들 수 있다. a+c=2b가 가능하면 답은 0, 아니면 답은 1이다. 구현은 1분만에 끝낼 수 있었다. #include #include #include using namespace std; signed main() { int T; cin >> T; while (T--) { int a, b, c; cin >> a >> b >> c; if ((a + b + c) % 3 == 0) cout N; string s; cin >> s; int i; vectora; int c = 0; fo..