jkrt2 blog

이전 글에도 언급한 바가 있으나, dojoi.xyz에 처음으로 문제를 출제해보았습니다. 원래 UCPC에 낸 문제였다 떨어졌던 문제였는데, 인생 처음으로 만들어본 문제를 대회에 쓰자면 좀 양심이 죽어버리는 거 같아서 처음에 일반 문제로 신청했으나, 나중에 dadas08님이 대회 문제로 쓰는 것이 어떠냐 물어보면서 대회에 쓰이게 되었습니다. 이 기회에 세팅도 처음으로 해봤습니다. 폴리곤이 생각보다 처음에 고려해야 할 사항이 많아서 제미나이를 여러 번 혹사시키고 다른 분들 도움도 받아보고, 심지어 대회 시작 3시간 전 (그 당시 SCSC에서 돌아오는 길이라...)에 세팅을 하기도 했습니다. 그래서인지 솔직히 데이터도 약간 부족한 부분이 은근 있었던 것 같습니다. 이거도 그나마 세팅하기 쉬웠던 문제들이였는데, ..

출처: KOI 본선 2010 5번난이도 (Personal): Platinum III - IV태그: Bitmasking, Constructive 문제:(a,b)와 (c,d)가 서로 붙어있는 그레이 코드 (매 인접한 수마다 비트가 하나씩만 다른 원형 배열)을 만들어라. 풀이: 일단 본문의 그레이 코드 예시를 살펴보자.000 - 001 - 011 - 010 - 110 - 111 - 101 - 100각 빨간색 위치는 어느 비트에서 달라지는지를 나타낸다. 편의상 1의 자리를 1번째 비트, 2의 자리를 2번째 비트, 4의 자리를 3번째 비트... 라고 하겠다. 그러면 순서대로 1 - 2 - 1 - 3 - 1 - 2 - 1인데, 이는 하노이 탑의 이동 순서와 동일함을 알 수 있다. 대체로 n개의 비트에 대해서 이 순..

카이런 (https://jkrt2.tistory.com/10) 참가가 얼마 안 됐지만 계속 달린다. 이번에는 서울대다. 이 대회가 원래였으면 오프라인 대회 기준으로 라스트 댄스였을텐데 며칠 전에 입대 연기라는 대형참사가 터져서 의도치 않게 PS 수명이 조금 늘어났다... UCPC 팀원도 구해야 할 거 같다. 그나마 요즘 폼이 상승세인 게 다행이라 하자 ㅋㅋ; 아무튼 Division 1에 배정됐다. 지난 SCSC 대회가 열렸을 당시에는 PS는 시작하지도 않았을텐데, 어쩌다 딥2하고 딥3을 건너뛰었다. 다름이 아닌 코포 레이팅 때문인데, 몇 달 전에 2번 연속으로 최고점이 찍혀서 2100을 간신히 넘긴 적이 있었다. 그 뒤 곧바로 20층으로 내려가고 그 뒤 7번 연속 20층 레이팅을 넘어서 20층 퍼포를 찍..

마지막에 글을 쓴 게 3월인데 그 이후 BOJ 서비스 종료라는 매우 큰 일이 일어났다. 이 일에 대해서 글을 작성하려고 했는데 뭔가 내가 말빨이 좋은 사람이다 그런 건 전혀 아니여서 (블로그 다른 글을 보면 알겠지만 상당히 내용이 중구난방이기도 하다) 작성은 딱히 하지 않았다. 근데 벌써부터 그 사이트가 그리운 건 한마음인지 슼보에서도 백준그리워요 닉이 난무했다. Good Bye BOJ 대회는 잘 치른 거 같고 오랜간만에 몰고 회원분들을 만나서 반갑기도 했다. 다시 BOJ 섭종으로 넘어가면, 이제 여러 대회들이 갑작스러운 섭종 소식을 듣고 열 수 있는 새로운 플랫폼을 탐색하거나 심지어 만드려는 움직임이 여럿 보였는데, 이런 상황에서도 대회를 열고 PS/CP 활동을 유지시키려는 분들에게 고마움이 든다.대회..

난이도: Platinum I (체감상 Diamond V)태그: #애드혹, #해구성, #많은조건분기 좀 무식하게 푼 거 같긴 하지만 오랜만에 어려운 문제 하나 풀었고 원래 풀이와도 약간 다른 것 같아서 생각 과정과 함께 올려봅니다. Statement Solution / Thought Process Subtask 1 (N = 17)을 보고 백트래킹을 해야 되겠다 생각했습니다. 구현 과정은 그렇게 어렵진 않습니다. N = 17이 되는 것을 확인하였으나, 홀수는 N = 11부터 되고, 짝수는 N - 1일 때 제외하고는 (전체 배열을 보면 안 된다는 것이 자명하게 보입니다.) 안 된다는 점을 파악했습니다. N이 작을 때 (그래서 앞으로 이야기하는 케이스는 모두 N>17를 전제로 합니다. 그래서 이가 큰 수에도 ..

ICPC 전부터 어떻게 참가할지에 대해서 고민이 많았던 대회였습니다. 현재는 1B1P1O1N(...)이 된 3Blue1Nutella의 a_cedia님이 입대를 하셔서 팀원이 모자란 상태라 처음에 출제할지 생각했는데 문제가 너무 애매해서 버렸습니다.그렇게 시간이 지나도 팀원을 못 찾았으나 dong5995님이 팀 제안을 하게 되었습니다. 사실 이 분이 코포 블루셔서 파란색으로 이름을 나타내긴 했...는데 코포쪽에만 약하신 거지 기하 같은 곳에서의 체급은 엄청납니다. 괜히 아챔 진출하신 게 아니죠 ㅋㅋ! 그래서 나머지 한 분을 찾고 있었는데 dong5995님의 제안으로 이 분에게 PS를 가르침받고 계셨던 치대 동기 분인 ehehfdlvy4님하고 같이 원내생진료실 [술자 | 어시스트 | 환자] 팀을 맺게 되었습..

뭔가 글 두 개로 쓰긴 애매할 거 같아서 하나로 묶었습니다. 온사이트 신청을 안 해서 온라인으로 나가게 되었습니다. Div. 1은 하다가 힘없이 털릴 거 같아서 Div. 2로 갈아타서 봤습니다. (원래 Div. 2는 내부인 대상으로만 한다고 하네요...)밥 먹고 나자 대회가 시작해있어서 허겁지겁 컴퓨터를 키긴 했는데 A를 보니까 구현이 막막하게 생겨서 그냥 끌리는 문제 하나로 넘어갔습니다. 이 당시 저는 난이도 오름차순 정렬이라는 사실을 모르고 있었습니다. 0:22 - H [First Solve, +1]대강 생각해보니까 K의 위치는 정해져있으므로 이들부터 옮긴 뒤 모든 P를 (끝쪽이 아닌) 한 뭉치로 옮기기 위해서는 최대한 중앙값 근처로 접근해야 한다는 아이디어가 빨리 잡혔습니다. 그런데 처음에 중앙값을..

ICPC Regional도 어느새 일주일이 지나고 제 첫 개인 프로그래밍 대회에 나가게 되었습니다.엄청난 구현 삽질로 7솔 날려먹은 게 아직도 아쉬운데 이번에는 제발 안 그랬으면 합니다.그런 걸 잡아줄 팀원이 없어서 걱정되긴 하지만, 그래도 그나마? 이번에 저한테 유리한 점은 난이도 순으로 문제가 나옴을 알고 있어서, 문제 푸는 순서는 확실히 잡힐 것 같습니다. 그리고 세트가 5시간이 아닌 3시간이라 스피드상으로는 유리할 것이라 생각했습니다.팀노트는 어차피 인터넷 검색 가능하다 해서 ICPC 때 쓴 코드 몇 개 대충 복붙해놓은 거 썼습니다. 옷은 올해 Regional 때 받은 파란 셔츠를 입고 왔는데, 대회 진행자 conu님이 그에 맞춰서 작년 Regional 옷을 입게 되었습니다. 작년 네온 오렌지 색..

Difficulty: Diamond III Connected Profile을 배우기 전 BOJ 1648 (격자판 채우기, Platinum III)를 먼저 보고 오시는 것을 추천드립니다. 해당 문제에서의 DP 아이디어 중 가장 많이 쓰이는 것이 비트필드를 이용하여 최근 M칸의 state를 DP 요소로 잡는 것인데, 이 문제 역시 이와 비슷한 양상을 띄고 있습니다.이 문제 역시 최근 M칸의 state를 저장하는 것이 핵심입니다. 여기서는 이들의 연결 관계 또한 트래킹하는 것이 중요합니다. 연결된 Profile이 여러 개 있으면, 이를 M개 칸에 나타나는 순서대로 1, 2, 3...이라 합니다. N, M은 한 자리 자연수이므로 State는 한 자리 수로 나타낼 수 있습니다. 즉, M칸의 state를 길이 M..

2025 ICPC 예선 후기에서 팀원 소개를 한 바가 있으니 참고바랍니다.그 동안 팀연습을 하는데 6솔만 뚫고 7솔 이후에는 항상 고전해서 이번에는 꼭 뚫고 싶었습니다. a_cedia님이 본선 준비 기간 도중 퍼플을 찍고 애드혹 플레 푸는 능력이 늘어나서 내심 기대를 하고 있기도 했습니다.어쩌다 열차를 예비소집날 오전 7시에 잡아서 (지금 생각해보니까 왜 이리 일찍 잡았지라는 생각도 했음...) 그 때 밤을 새고, 본선 전 날에는 12시간을 자서 컨디션은 오히려 괜찮았던 것 같았습니다. 팀노트는 전하고 거의 비슷하게 했는데, 팀연습을 하는 도중 제가 넣은 Aho-Corasick 코드에서 트라이는 만들어두고 정작 핵심인 KMP식 구현은 만들어두지도 않았다는 점을 알게 되어서 수정하게 됐습니다. 그 외에도 ..