kim16의 블로그

서론* UCPC 2026에 octane, ComPhyPark과 팀을 이루어 참가했습니다.* 팀명은 [군인 군인 대학원생]이었습니다.* 예선 후기는 octane의 블로그에서 확인할 수 있습니다.https://octane-kr.github.io/posts/ucpc-2026-preliminary/ UCPC 2026 예선 후기 - 코끼리 뿌우올해 UCPC는 gs20036, ComPhyPark과 함께 출전했다. 지난 3년간은 내가 빡겜 팀을 구할 만큼 실력이 뛰어나지도 않고, UCPC는 약간 친한 친구들이랑 놀러 나가는 대회라고 생각을 했어서 높은 등수를 받octane-kr.github.io * 예선 12등으로 본선에 진출하는 데는 성공했으나, 본선 등록, 즉 1.5차예선에서 탈락했습니다.* 따라서, 본선에는 참..

안녕하세요.벌써 2주째 Pseudo-다이아스트릭을 이어나가고 있습니다.지금까지 9문제 해결했고, 풀_문제 셋에는 5개가 남아 있습니다.서론저번 주에 이월된 문제는19730번. Sightseeing Tour28320번. Flip it and Stick it2209번. 버스 터미널입니다.이 중 19730번, 28320번을 해결했습니다.2209번은 유의미해 보이는 관찰을 했고 풀이를 내서 구현했지만 반례만 확인하고 WA를 받았습니다.19730번. Sightseeing Tour월요일에 태그를 깠더니 "2-sat"과 "제곱근 분할법"이 나왔습니다.2-sat은 어떻게 활용하는지 바로 나왔지만, 제곱근 분할법은 어디에 써야 하는지 모호했습니다.금요일에 우연히 Leejseo님의 블로그를 보게 되었고 2-sat의 응용을..

안녕하세요.주말에 백준 한두 문제 풀고 침대에 누워만 있는 것이 너무 비생산적이라 느껴져서 코포도 조금씩 돌기로 했습니다.총 2개의 셋을 돌았고 하나는 선방 하나는 폭망했습니다.Codeforces Round 1082 (Div. 1)토요일에 충분히 최근인 딥1 대회를 찾아서 쳤습니다.다른 부대이지만 같은 생활관을 쓰는 ComPhyPark과 같이 돌았는데, 저는 4솔을 했고 ComPhyPark은 5솔을 했습니다.A1번 (00:03 WA, 00:05 AC)주어진 배열을 여러 개의 구간으로 나누어서 한 개의 구간에서는 맨 앞에 있는 수로부터 다른 모든 수를 만들 수 있게 해 봅시다.그러면 각 구간은 다음 조건들을 만족해야 합니다.조건 1: 구간의 맨 앞에 있는 원소가 나머지 원소들보다 strict하게 작아야 한..

안녕하세요.이번 주부터 Pseudo-다이아스트릭 챌린지를 시작했습니다."풀 문제" 셋에 매일 다이아 문제를 하나씩 추가한 뒤 셋의 크기를 충분히 작게 유지하는 것이 목표입니다.이번 주에는 7개의 문제를 새로 받아서 4개를 풀어냈고, 현재 셋의 크기는 3입니다.위에 보이는 뇌절의 흔적은 밑에서 설명하겠습니다.월요일33764번. Election Queries를 뽑았습니다.관찰 1) (소 x가 받은 vote의 수) + (소 y가 받은 vote의 수) >= (하나의 소가 받은 vote 수의 최댓값)이면 (x,y)는 head cows가 될 수 있다.이 관찰을 토대로 소들을 받은 vote의 수들에 따라 관리해야겠다는 발상을 할 수 있습니다.관찰 2) k표를 받은 소들 중 그 번호가 최대인 소의 번호, 최소인 소의 ..

2월 9일~2월 15일 코드포스 후기입니다.버추얼만 5번 돌아서 마참내 오렌지를 달성했습니다.이제 당분간 코드포스를 안 할 예정인데, 그 이유는 밑에 설명하겠습니다.Codeforces Round 1078 (Div. 2)A번n - n/w가 답입니다.체감 난이도: B2B번각 bank마다 transition되지 않고 남아 있어야만 하는 루비의 수를 구합니다. 남아 있어야만 하는 루비의 수가 최댓값인 은행으로 모든 루비를 보내는 것이 최적입니다.체감 난이도: S5~S3C번관찰: n이 주어졌을 때 가능한 Informativity의 값은 n의 약수들 뿐이다. 즉 최대 O(sqrt(N))가지의 Informativity만 확인하여도 충분하다.Informativity가 정수 x로 주어졌을 때, 한 문자 c가 존재해서 한..

앞으로는 매주 많은 양의 셋을 돌고 후기를 한 번에 적으려고 합니다.오늘은 이 6개의 셋에 대해서 후기를 작성하겠습니다.Codeforces Round 1076 (Div. 3)A번 풀이는 굳이 작성하지 않겠습니다.체감 난이도: B3B번일반적으로 [1, 가장 큰 원소의 위치]를 flip하면 되는데, 가장 큰 원소의 위치가 1인 경우 그 원소를 떼놓고 뒤쪽 배열만 생각하면 됩니다.체감 난이도: S4~S3C번a[i] = max(a[i+1], b[i])를 뒤에서부터 적용하면 됩니다.체감 난이도: S3~S2D번관찰: Difficulty를 a[i] 중 하나로 하는 것이 최선이다.배열 a를 정렬하고, Difficulty를 a[i] 중 하나로 정한 뒤 i번과 그 뒤의 검들로 몇 스테이지까지 갈 수 있나 확인합니다. (아..

1월 3일부터 오늘까지 돈 셋들에 대한 이야기입니다.https://codeforces-anytime.firebaseapp.com 이라는 사이트를 통해서 버추얼을 돌았습니다.그 결과는 아래 사진으로 대체하겠습니다. Codeforces AnytimeYou are rated anytime in Codeforcescodeforces-anytime.sonoapp.page제 코포 레이팅이 2300인걸 고려하면 너무 처참한 성과입니다.모든 셋에서 A~C 사이에서 이상한 방법으로 WA를 쌓다가 D~E 풀이 발상을 못하거나 or 구현이 터져서 망했습니다.제가 푼 문제들에 대해서 풀이는 따로 적지 않도록 하겠습니다.다음과 같은 사실들을 관찰했습니다.- 구현 실수가 너무 많았습니다. 이중 포문 돌리면서 매개변수를 i와 i로..

새해 첫 셋으로 ICPC 2025 Manila Regional을 돌았습니다.https://codeforces.com/gym/106262#9+1333/13으로 온사이트 기준 11등, 코포 기준 8등을 받았습니다.ICPC 2025 Manila Regional의 풀이를 다수 포함하고 있으니, 팀 연습을 도실 분들은 여기서 뒤로가기를 눌러주시면 감사하겠습니다.대회 시작 (00:00~01:00)지금까지 돌았던 셋들 중 유의미하게 많은 셋이 A번을 가장 쉬운 문제로 두었습니다. A번부터 읽기 시작했습니다.A번(00:02 AC)풀이는 굳이 적도록 하지 않겠습니다.체감 난이도: B3이어서 D번을 읽었고, Probable한 풀이가 나와서 짜기 시작했습니다. (스포: 틀린 풀이입니다.)10분정도 박았는데 예제도 제대로 안..

월요일과 화요일에 각각 앳코더 ARC와 코포 딥2를 돌았습니다.https://atcoder.jp/contests/arc060 https://codeforces.com/contest/2158전자는 3솔/4솔로 2600, 후자는 4솔/7솔로 2300 정도 되는 퍼포먼스를 냈습니다.앳코더의 경우 2016년 셋이라 퍼포먼스가 높게 찍힌 것 같습니다.ARC 060부터 간단하게 후기 쓰겠습니다.C번(00:04 WA, 00:06 AC)문제 조건을 보았을 때 (i, i번째 카드 중 고른 카드의 수, 고른 카드들에 적힌 수의 합)을 가지고 dp를 돌리면 될 것 같이 생겼습니다.마지막에 경우의 수를 셀 때 어딘가 잘 못 세서 WA를 하나 받았지만 금방 고치고 6분만에 AC가 나왔습니다.체감..

어제에 이어서 다시금 딥2를 돌았습니다.https://codeforces.com/contest/2173결과는 약간 빠른 4솔로 2050~2100 사이의 퍼포가 나왔습니다.여담으로 사지방 컴퓨터에 크롬 확장 프로그램을 설치할 수가 없어서 비슷한 성과를 거둔 사람들의 레이팅 변화를 가지고 퍼포를 어림했습니다.A번 (0:01 AC)단순 구현 문제가 나왔습니다. 풀이는 생략하겠습니다.체감 난이도: B1B번 (0:04 AC)Idea: i번째 라운드가 끝나고 얻을 수 있는 점수의 최댓값을 mx[i], 최솟값을 mn[i]라고 하면, mx[i+1]과 mn[i+1]은 mx[i],mn[i], a[i],b[i]에 관한 식으로 나타낼 수 있다.엄밀한 증명을 할 수는 있지만 굳이 넣지는 않겠습니다.이 아이디어를 가지고 구현해서..