jjang36524의 블로그

https://www.acmicpc.net/problem/30009

NYPC Round 2가 어떻게 이뤄질지, 어떤 전략을 사용하는 것이 좋을지 소개해 드리겠습니다. 진행 Round 2는 Round 2-A, Round 2-B 두 개로 나누어집니다. Round 1에서 150점 이상을 받아 통과했으면 이 두 대회에 모두 참가할 수 있고, Round 2-A에서 높은 점수를 받은 N명과, 앞 N명을 제외하고 Round 2-B에서 높은 점수를 받은 N명이 본선에 진출하게 됩니다. 정확한 N은 아직 알려지지 않았지만, 작년에는 총 44명이 본선에 진출하였습니다. 각 Round 2는 3시간 동안 진행되며, 총 4문제가 있습니다. 대회 중 인터넷에 공개되어 있는 코드는 사용할 수 있지만, 대회 시작 이후 나온 자료는 사용할 수 없습니다. 문제별로 여러 부분문제들이 있기 때문에, 이를 ..

Round 1에 대하여 NYPC는 Round 1, 2-A, 2-B, 본선 4개의 라운드로 나누어지는데, 이 중 가장 먼저 보고 가장 난이도가 쉬운 대회가 Round 1입니다. Round 1은 일반적 알고리즘 대회와 다른 여러 특징들이 있는데, 1.대회 시간이 몇 시간이 아닌 5일이다. 2.다음 라운드 진출 커트라인이 절대평가로 정해진다. 3.대회 도중에 책이나 대회 시작 전에 올린 블로그 등을 참고할 수 있다. 4.코딩이 필요없고 손이나 시뮬레이터 등으로 풀 수 있는 문제가 나온다. 이렇게 4가지 정도가 대표적인 특징이라 할 수 있습니다. Round 1의 난이도 Round 1은 프로그래밍을 잘하지 못하는 사람도 참가할 수 있는 만큼 쉬운 문제들이 주로 출제됩니다. 작년 대회의 본선 커트라인은 250점인데..

1번: 티어:Silver 4 최근 5년 전국본선에 나왔던 고등부 문제 중 가장 쉬운 문제라 생각됩니다. 풀이는 뒤에서부터 생각하면 쉽게 나오는데, 도착 지점에서의 속력은 0으로 고정되어 있으므로, 도착 직전 지점의 속도는 최대 1이 됩니다. 이런 식으로 왼쪽으로 가면서 속도를 1씩 올리다가, 속도 제한에 걸리는 경우만 속도를 제한에 딱 맞게 조절해주면 됩니다. 2번: 티어:Platinum 2 고등부 2번은 반대로 어려운 문제입니다. 2번 문제부터 풀기 어려워지는 경향이 커지기 때문에, 부분점수를 긁는 연습을 열심히 하면 동상에 도움이 될 수 있습니다. 부분문제 1:x,y,z의 쌍은 O(N^3)개가 있으며, 각 쌍에서 답을 체크하기 위해서는 포함되는 S의 원소들이 포함되었는지 아닌지를 완점 탐색으로 체크하..

8문제 중 6문제를 푸는 데 성공하며 2551점까지 레이팅을 끌어올렸습니다. A번 평소 A번보다는 어려운 느낌이 있던 문제였습니다. 먼저 0 타입의 스킬과 1 타입의 스킬을 정렬한 뒤, 0 타입 스킬의 개수1 타입 스킬의 개수이면 00001010 순서로 배열하면 됩니다. #include using namespace std; #define int long long int vis[100100]; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int T; cin >> T; while (T--) { int N; cin >> N; int i; vectora, b; for (i = 0; i > vis[i]; } in..

이번 IOI에서 Day1 27등, Day2 18등, 종합 22등의 성적을 거두어 금메달을 받게 되었습니다. 제가 대회를 치르면서 어떤 풀이를 생각했고, 어떤 전략을 사용했는지를 써 보겠습니다. Day 1 시작~1시간 30분 평소에 하던 대로, 1시간 30분까지는 구현을 하지 않고 풀이만 생각한 뒤에, 구현은 그 뒤에 몰아서 하기로 했습니다. A번은 dp식을 잘 세우면 누적합이나 세그먼트 트리로 풀 수 있어 보이는 쉬운 문제라 생각을 했고, B번은 재밌어 보이는 인터렉티브 형식이지만 너무 잡으면 망할 듯한 문제, 3번은 41까지는 쉽고 그 뒤는 어려운 문제라 생각을 했습니다. 1번을 무조건 풀어야 한다고 생각해서 30분~1시간 30분까지는 1번만 생각했습니다. 1번의 최적해는 그물의 길이가 증가하다가 감소..

1번과 4번은 푼 문제여서 2번과 3번 두 문제를 생각했고, 그 중 2번을 풀었습니다. 2번: 문제를 요약하면 A[i]=3,A[j]=2,A[k]=1 or A[i]=1,A[j]=2,A[k]=3인 i,j,k 쌍을 최대한 고르는데, 한 인덱스는 한 번만 쓸 수 있는 문제입니다.구현이 발상에 비해 간단한 편인 그리디 문제입니다. 가장 먼저 할 관찰은 A[i]=3,A[j]=2,A[k]=1인 것을 몇개 쓰고, A[i]=1,A[j]=2,A[k]=3인 것을 몇 개 쓸지를 투 포인터로 체크해야 한다는 것입니다. 그 다음으로는 A[i]=3,A[j]=2,A[k]=1인 것의 개수와 A[i]=1,A[j]=2,A[k]=3의 개수가 주어졌을 때, 이게 가능한지를 O(N)에 체크해야 합니다. A[i]=2인 i를 보면서, 3,2,1 ..

문제를 1시간 동안 보고 느낀 생각과 문제 요약: 1번: a