2월 3일에 열린 솔브드 아레나 파티 Div.1에 미러로 참가했다. 대회 장소가 집에서 멀기도 하고 아레나 #10~#16에 전혀 참가하지 않아서(Arena #16 운영 제외) 선정될 확률도 없었던 터라 본 대회에 참가 신청을 하진 않았다. 대회 결과 5솔브로 본 대회+미러 합산 8등을 했다. 막판에 H를 풀었다면 등수가 크게 올랐을 것 같아서 아쉽다. A. 정렬된 연속한 부분수열의 개수 (0:02) 문제의 조건을 만족하는 모든 $(i, j)$에 대해, $[i, j]$가 다음 조건을 만족하는 $[l, r]$ 중 정확히 하나의 부분구간임을 보일 수 있다. $A_l A_l$ $r=N$이거나 $A_r > A_{r+1}$ 다르게 말..
역사적인 solved.ac 아레나 첫 대회에서 모든 문제를 풀어 4등을 했다. 한동안 OI style의 문제들만 풀다 ICPC style의 문제들을 접하니 조금 난감했는데, 다행히도 운이 좋아 좋은 성적을 받았다. 대회가 성공적으로 마무리된 점은 한국 PS계에 상당히 고무적일 것으로 보인다. 아레나 시스템에 대한 다양한 생각을 해봤는데, 이런 이야기들은 후기 끝에 짧게 써 보겠다. A. 양말 짝 맞추기 (0:00:31) 다섯 개의 수 중 한 번 등장하는 수를 찾는 문제이다. 다양한 풀이 방법이 있지만, 다섯 개의 수를 XOR하는 것이 가장 코딩하기 빠르다. 더보기 #include using namespace std; typedef long long ll; int a, b, c, d, e; int main..
역시 지난번의 굿바이 한별 팀으로 참가해 종합 9등을 했다. 나는 정말 최악의 대회를 치른 것 같다는 느낌이었다. 다른 팀원들이 그나마 많이 풀어 줘서 이 정도라도 올라온 것 같았다. CD. Colored-Dealt (0:13:25) 나는 처음에 AB, CD, EF, GH, IJ를 맡기로 했는데, 일단 CD를 읽자마자 쉽다는 확신이 들어서 바로 잡았다. 우선 전부 다 빨간색으로 배정하고, 왼쪽부터 한 개씩 푸른 색으로 바꿔나가는 식으로 최대 가중치 구간을 한 칸씩 이동시킬 수 있다. 이때 인접한 두 쿼리의 차이를 이용해 $N-1$개의 꽃 색을 알 수 있고, 마지막의 경우 첫 번재 쿼리 결과를 이용해 알아낼 수 있다. #include #include "colored_dealt.h" #include usin..
예전에 참가했던 대회 업솔빙은 언젠가는 해야 하는 일이다. 그리고 2023 IOI 선발고사가 가까워진 지금 해보려고 한다. 이미 모든 문제 풀이를 어렴풋이 들은 적이 있지만 기억이 가물가물하기도 하고, 적어도 IOI APIO 기출을 대학에 가기 전에 최대한 풀어놓으려고 한다. 그 뒤로는 OI 문제들보다는 ICPC 문제들에 집중해야 하기 때문에... 간단한 후기 대회 때 사용했던 전략을 간단히 풀어 보자면, IOI 2022 당시 컨디션이 별로 좋지 않았어서 (대회 직후 코로나 확진), 큰 욕심을 내지 않고 섭테주의 전략으로 모든 문제를 풀었다. 사실 컨디션이 좋았어도 섭테 전략으로 가긴 했겠지만, 그랬다면 코딩 속도가 좀 더 빨랐을 것이다. 나는 비교적 구현 속도가 남들보다 빠른 편이라고 생각하기에 평소에..
이번 IOI에 한국 국가대표로 선발이 되어서, 본 대회를 치르게 되었습니다. 코로나19가 계속되는 바람에 올해도 싱가포르 현지에서 대회를 치르지 못하고 우리나라에서 온라인으로 치르게 된 점이 아쉽습니다. 작년에 이어 2년째 IOI에 참가하게 되었는데, 작년과는 느낌이 확연히 다른 대회였습니다. 작년과 다르게 올해는 주변 누구도 성적에 대한 기대를 가지지 않아서 편한 마음으로 시험을 볼 수 있었습니다. 아마 이러한 점도 성적에 영향을 주지 않았나 싶습니다. Day 0 (Practice Session) 연습 세션 문제는 작년과 거의 똑같았습니다. 차이점이 있다면, 무슨 이상한 전처리를 해야 맞는 문제 하나가 간단한 bfs 문제로 바뀌었습니다. 작년에 끝까지 풀지 못했던 문제(Jelly Flavours)를 이..
이번 앳코더 ARC에서 6문제를 다 풀어 전체 5등, Rated 중 1등을 하였습니다. 간단한 후기와 문제 풀이를 해볼까 합니다. A. 2nd Greatest Distance 구현과 케이스처리가 매우 복잡한, 400점짜리 문제 치고는 어려운 문제입니다. 다만 아래와 같은 관찰을 통해 구현을 편리하게 줄일 수 있습니다. 각 정점을 x좌표순으로 정렬했을 때 상위 2개 / 하위 2개 점과, y좌표순으로 정렬했을 때 상위 2개 / 하위 2개 점만이 필요하다. 만약 2번째로 긴 체비셰프 거리가 위 정점들로 이루어지지 않는다면, 두 양끝점 중 하나를 위에서 뽑아낸 (최대 8개의) 점들로 대체했을 때 더 긴 해를 얻을 수 있음이 보장되기 때문입니다. 따라서 위와 같이 8개의 점의 후보를 얻어내고, 나이브하게 2번째로..
APIO 2021은 작년 APIO보다 많이 어려운 셋이었고, 점수도 받기 힘들었습니다. cms 화면 캡처는 깜박하고 못 했지만, 47+100+36=183점을 획득했습니다. 전체 성적은 29등(은메달) / 한국 1등입니다. 인증샷은 APIO 결과 화면으로 대체합니다. 문제의 난이도가 매우 높았고 구현도 힘들었으며, 대회 중에 채점 큐가 터져서 정말 고난의 연속이었습니다. 물론 그 덕에 시간을 1시간 더 받긴 했고, 결과적으로는 이득이었던 것 같습니다. 아래는 문제별로 제가 생각한 최대 풀이입니다. A. 육각형 영역 최종 점수: 47점 총평: 100점 풀이는 바로 나왔지만, 구현이 매우 매우 매우 매우 매우 더러워서 시간 내에 도저히 풀 수 없는 문제였습니다. 구현이 간단한 풀이가 있다면 매우 궁금합니다. ..
PMCC는 수학동아에서 운영하는 수학 사이트인 폴리매스에서 개최하는 코딩 대회로, 2020년 8월에 1회 대회가 열렸고, 2021년 2월에 2회 대회가 열렸습니다. 2회 대회는 1회 대회 때보다 더욱 다양해진 실력의 코더들을 위해 Division 1과 2로 나눠서 운영되었습니다. 준비 과정에서 CMS 서버를 세팅해 주신 whqkrtk04님, 문제 출제를 도와 주신 azberjibiou, blackking26, gunwookim님, 그리고 촉박한 검수 기한에도 불구하고 검수에 힘써 주신 16silver, ainta, gs18115, messi, TAMREF님께 감사의 말씀을 전합니다. 아래는 풀이 ppt 파일입니다. 작성을 도와주신 azberjibiou님과 blackking26님께 다시 감사의 말씀을 전합..