https://codeforces.com/contest/2031199등으로 간신히 100등대 선방완료11시에 조기퇴근신난다사실 9시 28분까지 침대에 붙어서 릴스 보다가9시 32분쯤에 일어나서 분주하게 컴퓨터 키는데 레지를 안 걸어놨더라 망했는데? 그러니까 팀원이 엑스트라 레지 걸고 D부터 ㄱㄱ 이러길래 ㅇㅋ 하고 시작했다(내가 팀원 중 최약체인 관계로 코포를 안 치면 고로시를 당한다) 일단 내가 A,B,C 미는 속도가 남들보다 많이 느리다는 거를 알아서 오렌지를 가려면 그냥 E를 꾸준히 풀어야겠다는 생각을 요즘 한다 E번그래서 E부터 읽고 시작했다. E를 읽고 5분~10분 정도 고민한 것 같다.그냥 아무 생각이 안 들어서 멍때리다가, isomorphic의 정의가 root가 고정된 상태에서 정의된다는 거..

https://atcoder.jp/contests/arc177/tasks/arc177_d Ob 1) 서로 쓰러뜨릴 수 있는 관계라는 것은 그 사이에 있는 모든 도미노 사이사이 간격이 H 이하라는 것Ob 2) 간격이 H 이하인 도미노들은 각각 묶어서 생각해도 된다. 서로 다른 그룹에 속한 도미노는 영향을 줄 수 없음 Todo 1) 그룹끼리 일단 묶어놓기 Ob 3) 예제 설명의 수형도를 잘 관찰하자. 수형도가 중도에 끊기지 않는 완전 이진 트리 형태가 되도록 변형시킨다면, 동일한 시나리오가 몇 번 중복되었는지가 그 시나리오가 발생할 확률을 나타낸다. 즉, '무의미한 무너뜨림'을 전부 중복으로 세어주도록 하자. Ob 4) 아무튼 한 그룹에 대해서 잘 세어주는 것은 관찰한 사실을 바탕으로 monotone sta..

https://codeforces.com/contest/2028/problem/E Ob 1. 마녀는 Alice가 위치한 정점의 자식 정점들 중에서 minimum depth가 가장 작은 서브트리를 갖는 곳으로 이동시키는 것이 최적이다.Ob 2. Alice는 무조건 윗방향으로 뒤도 안 돌아보고 올라가는 것이 최적이다. 어떤 정점 $x$에서 리프에 닿지 않고 잘~ 움직이다가 정점 $x$에서 처음으로 $\text{par}(x)$에 이동시키는 확률을 생각하자.이 확률은 오로지 $x$의 서브트리의 구조에 의해서만 결정되므로 계산하기 쉬울 것으로 기대된다. 정확히는, $x$의 minimum depth에 의해서만 결정된다. 왜냐하면 마녀의 이동은 무조건 그 방향으로 고정되기 때문이다. 그러면 depth에 따른 확률을 ..

뭐 아무튼 그래서 버스는 잘 잡아타고 본가에 올 수 있었다. 웰컴키트 및 간식코너 칫솔세트, 후드집업, 빼빼로, 머그컵 정도 받은 것 같다. 펜과 종이가 자리에 넉넉하게 놓여있었는데, 사소한 부분이지만 마음에 들었다. 스타벅스 아이스아메리카노/핫아메리카노 및 얼음컵 등이 편리하고 넉넉하게 비치되어 있었고, 냉장고에는 몬스터와 다양한 음료들이 가득했다. 샌드위치도 인당 하나씩 있었는데..! 이 정도로 잘 챙겨두실 줄 몰라서 서브웨이를 먹고 온 터라 먹기 애매해서 아쉬웠다. 다음에는 샌드위치와 간식들이 비치된다고 메일 안내에 같이 적어주시면 좋을 것 같다. 굉장히 푸짐한 편이므로 생색을 이빠이 내셔도 괜찮을 것 같다는 생각이다. 덕분에 시작 전에 왼손에 아아 오른손에 몬스터를 쥐고 마시는 호사를 누릴 수 있..

11월 6일, 재학 중인 한양대학교에서 가장 멋진 건물인 정몽구 미래자동차센터?에서 열린 CodeRun 본선에 참가했다. 이모저모 이 대회는 현대자동차에서 만든 것 같고, 세션을 쭉 들어보니 연구장학생을 모집하려는 취지로 대회를 만든 것 같았다. 사실 대회를 주최하는 기업들은 구인이라는 분명한 목표가 있는데, 참가자들은 보통 홍보 세션에 딴짓을 한다. 그래서 순수하게 ‘알고리즘을 좋아하는 취업 같은거 잘 모르는 새내기 참가자 시선’에서 봤을 때는, 해당 직군에서 마주할 수 있는 챌린징한 현업 문제들과 그때의 해결 과정 같은거를 소개하면 더 재미있게 들을 것 같다는 생각이 들었다. 뭐… 진짜 아직 진로 걱정을 build 하지 않은 막무가내 새내기라서 뭣 모르는 소리일 것 같긴 하다. 예선 3시간 동안 4문..

지문이 짧길래 저번에 카페에서 떠들다가 핸드폰 메모장을 이용해서 대충 풀이를 내봤는데 흥미로웠다.어제 메모장 정리하다 메모를 발견해서 구현해보았다. 일단 문제 자체가 너무 점화식으로 잘 표현될 수 있을 거라는 느낌을 풍긴다.이 문제의 어려움은 $n+1$개의 직사각형 중 $n$개는 정확히 계단 모서리에 하나씩 걸치지만 딱 한 개의 직사각형은 중앙 어디에든 위치할 수 있다는 점에 있다. 따라서 중앙 어디에든 위치할 수 있는 직사각형의 위치를 고정시킨다면 문제가 수월해질 것이다. 고정했다고 생각하고 문제를 바라보면, 직사각형의 두 변을 연장해서 가능한 답의 꼴들을 찾아볼 수 있다.무조건 두 변 중에 한 변의 연장선은 어떤 조각도 가로지르지 않는다는 관찰이 핵심적이다. 이를 이용하여 약간의 포함배제를 적용하면 ..

https://mathsciforstudent.tistory.com/390 그새 또 잔뜩 만들어 왔다. 2월에 비해 새로 추가된 문제는 [지워진 ETT], [코드마스터 2024], [찬물 샤워], [코드마스터, 슬라이딩 퍼즐 마스터, 보드게임 마스터], [물탱크 알바(Hard)], [Simple Tree Decomposition Problem]이 있다. [지워진 ETT]는 SUAPC 2024s에 출제한 문제로, 아마 문제 구상은 [Sieve Game] ~ [신촌방위본부: 지하 벙커의 비밀]과 비슷한 시기에 했던 것 같다. 아마 KAIST 2023 Mock Competition의 Call for Tasks에 넣어서 떨어졌나 그랬을 것이다. azberjibiou님과 songc님만이 검토하였고 당연히 이 내용..

오랜만의 문제 풀이이다.KSAAC 2023 summer에 출제된 테마파크 문제이다. $s$의 서브트리를 기준으로, 어떤 두 간선도 조상-후손 관계에 있지 않은 간선 집합들을 관리해두면, $s$와 부모를 잇는 간선과 비교해서 써먹을 수 있을 것 같다. $s$와 부모를 잇는 간선에서의 비용을 $w_s$라고 하자. 당연히 $s\ge 1$일 때만 정의할 수 있다. 서브트리 속 여러 정보를 효율적으로 관리하는 것은 보통 스몰투라지 기법이 잘 먹힌다. 풀이를 조금 더 구체화해보자. 우선, 각 정점은 자신보다 윗쪽에 있는 간선들과 교류가 생기므로 일반적으로 트리 문제를 풀 때 $s$의 서브트리에 정점 $s$를 포함하는 것과는 달리, 정점 $s$는 제거하는 식으로 값들을 정의하자. $\ell_s:=$ 정점 집합 $s^..

안녕하세요, 블로그 주인 김도훈입니다! 제가 고등학교 3학년 때 끙끙대며 만든 중고등학생 대상 대회가 올해에도 2회 차로서 이어서 열리게 되었습니다! 올해도 제가 대회 전반에 걸쳐 작년의 퀄리티를 유지하려고 열심히 노력하고 있으니… 많은 관심 부탁드립니다! 전국 중고등학생 대상으로 오프라인 대회, 코드마스터 2024가 열립니다! 대회는 8월 31일, 송도고등학교에서 진행됩니다. https://boj.kr/songdo2023에서 작년 문제들을 확인하실 수 있고, 작년과 비슷한 구성으로 출제될 예정입니다.자세한 내용은 포스터와 QR 코드 [신청 링크]를 통해 확인하실 수 있습니다. 대회에 관한 여러 최신 정보를 인스타 @code_master2024 에 공지할 예정이니 참고해주세요. 감사합니다.