UCPC Journey to Daejeon 팀원이고, ICPC도 같이 나가게 될 팀원 gs22006, iccodly와 같이 참가했다.E번 (22min, solved by jjang36524)난이도: Gold I문제 요약: 길이 $n \leq 500$의 수열이 있다. 원소를 하나씩 지우는데, 지우는 과정에서 수열의 인접한 두 수가 같은 순간이 한 번이라도 있으면 안 된다. 이때 수열을 지우는 $n!$개의 방법 중 조건을 만족하는 방법을 구하여라.풀이: 비어 있는 배열에서 원소들을 채우는 것으로 바꿔 생각할 수 있다. $dp[i][j]$를 $i~j$번째 원소가 maximal한 지워진 원소들의 구간일 때 이 구간을 채우는 방법 $(j-i+1)!$개 중 조건을 만족하는 개수라 하자. $i-1$번째 원소와 $j+..
러시아 북서부 리저널 NWWRC의 2023년 대회에 혼자 참가해서 공식 대회 기준 3등, 버추얼 스코어보드 기준 4등을 했다.A(1min)예상 티어: Bronze 3문제 요약: 정렬된 $a_1, a_2, a_3, a_4$ 길이의 막대가 주어졌을 때, 이 막대들을 x축이나 y축에 평행하게 배치해서 만들 수 있는 내부 공간의 최대 넓이를 구하라.풀이: 만들 수 있는 도형은 직사각형이 유일하고, 한 변의 길이는 $a_1$로 고정, 다른 한 변의 길이는 $a_3$이 최대이므로 $a_1*a_3$이 답이다. 평행 배치 조건이 없었으면 재밌는 기하 문제가 됐을 수도 있는데 현재 상태로는 노솔 방지용 문제 D(11min)예상 티어: Silver 1문제 요약: $d대회 중에 사용한 풀이는 다음과 같다.자릿수의 합이 $d..
9문제 중 총 6문제를(A,B,C,D,E,G) 풀어서 1등을 할 수 있었다. 6솔이 총 6명이였고, 나와 페널티 8분 차이인 사람도 있어서 짜릿한 대회였다고 할 수 있다.A번(7min)최근 진행된(저는 아쉽게도 본선 진출에 실패했다) NYPC 코드배틀의 일부를 가져온 문제였다. 다시 굴릴 주사위를 선택하는 경우는 총 32개이고, 다시 굴린 주사위에서 나올 수 있는 결과는 최대 7776가지이니브루트 포스로 각 32개의 다시 굴릴 주사위 집합마다 모든 가능한 결과들의 평균을 구하고, 이들의 최댓값을 찾는 방식으로 구현하면 풀 수 있다.기존 코드 사용이 허용되는 대회여서 코드배틀의 코드를 컴퓨터에서 가져오는 게 최선의 전략일 수도 있었으나, 로컬에서 코드를 찾는 것이 오래 걸릴 것이라 판단하여 시도하지 않았다..
2023년~2024년 동안 입시 준비로 PS를 거의 하지 못한 뒤 대학생이 되어 PS를 다시 하게 되었고, 첫 팀 대회로 UCPC 2025에 나갔다.팀원은 jjang36524, sorohue, heeew이다.A번 (253min, -3)초반에 내가 잡으면서 A~D 중 가장 쉬운 문제이고 답은 항상 (리프의 개수+1)/2 라고 판단한 뒤 단순한 DFS 기반 컨스트럭션을 했는데, 틀렸다. 이후 DP를 기반으로 한 컨스트럭션으로 한번 더 틀린 후 솔브팀이 매우 적은 것을 보고 더 이상 잡으면 페널티가 많이 쌓일 것으로 판단하여, 다른 문제로 갔다.이후 내가 다른 문제들을 생각하는 동안 heeew가 컨스트럭션을 만들고 있었고, 이를 통해 문제를 풀 수 있었다.B번 (205min, -5)1시간 30분이 지난 상황에..
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문제가 있습니다. 대회 중 인터넷에 공개되어 있는 코드는 사용할 수 있지만, 대회 시작 이후 나온 자료는 사용할 수 없습니다. 문제별로 여러 부분문제들이 있기 때문에, 이를 ..
NYPC Round 1 소개+2022년 풀이
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의 원소들이 포함되었는지 아닌지를 완점 탐색으로 체크하..