본문 바로가기
728x90

분류 전체보기

 (32)
IOI 2024 Message 풀이 간만에 좋은 문제를 풀어서 블로그에 정리한다.정해를 들었는데, 이 풀이는 정해가 아니라 별해라고 한다. 나는 이 풀이가 정해보다 조금 더 쉽다고 생각한다. 문제 요약https://www.acmicpc.net/problem/32265A는 B에게 길이가 $1$ 이상 $1024$ 이하인 이진 문자열 $S$를 보내야 한다. 보내는 방법은 다음과 같다.길이 $31$의 이진 문자열을 보낸다. 단, 이 중에서 미리 정해진 $15$비트는 임의의 값으로 변경된다. 이 위치는 고정되어 있으며, A만이 알고 있다. 또한, 문자열을 보낸 직후 문자열의 일부 값이 변한 후 최종적으로 B에게 전송된 문자열을 알 수 있다.편의상 A가 전송한 값이 B에게 그대로 전달되는 $16$개의 비트를 진짜 비트, 그렇지 않은 것들을 가짜 비트..
제 2회 피갤컵 후기 제 2회 피갤컵에 참가했다.1회 후기: https://flappybird.tistory.com/74 제 1회 피갤컵 후기ps 갤러리에서 대회를 연다고 해서 참여해보았다.  나보다 잘하시는 분들이 꽤 많이 참가하셨는데, 운이 좋아서 이길 수 있었다. 아마 G를 빨리 푼게 크게 작용했던 것 같다. 또한 운 좋게 추첨에flappybird.tistory.com 5등했다. 전체적인 퀄리티에 대해서 말하자면, 1회 피갤컵과 비슷하게 매우 좋다고 생각한다. 특히 F와 G번 문제가 정말 재미있었다. 쉬운 포지션의 문제도 퀄리티가 좋은 편이다. 아쉬웠던 점들:D 퍼솔을 정말 간발의 차이로 놓쳤다. AC를 받은 직후 스코어보드에는 퍼솔로 표기되었으나, 한 1분쯤 지나니 나보다 먼저 제출한 다른 사람의 소스코드가 채점되었고..
2025 KSA Automata Winter Contest 후기 작년에는 좀 망쳤던거같은데, 올해는 잘 쳐서 좋다. G에서 좀 심하게 말렸는데, 나만 그런건 아닌 것 같아서 신경쓰지 않기로 했다. 풀이내가 푼 것만 있다. (A에서 H)I와 J는 업솔빙 이후 정리할 예정이다.A. 아름다운 수열상당히 비직관적인 관찰을 요구하며, 증명도 어렵다. 다음 관찰이 핵심이다.$i$번째 원소가 $i$인 수열은 문제에서 제시된 조건을 모두 만족한다.증명이 굉장히 재미있는데, 여백이 부족하여 여기에는 적지 않겠다.B. 저녁 태권도각 학생이 정확히 한 날짜를 제외하고 모든 태권도에 참여해야 한다는 것을 알 수 있다.결국 중요한 것은 $i$일에 참여해야 하는 학생의 최소 명수인 $A_i+B_i$이다. 아침, 저녁에 상관없이, 이 조건을 만족하도록 모든 학생을 각 날짜에 배정했다 하자. 그..
2025 1월 PS 일지 5월쯤에 이런 글을 쓴 적이 있다. 한 달에 푼 모든 다이아 문제를 다 쓰는게 생각보다 고된 작업이라는 것을 깨닫게 되었는데, 그래서 재미있었던 문제만 적기로 했다. 27599. Parmigiana With Seafoodhttps://www.acmicpc.net/problem/27599기범이와 셋을 돌때 푼 문제다.일단 이분탐색의 아이디어를 적용하면 다음과 같이 문제를 환원할 수 있다.트리에 $0$ 또는 $1$이라는 숫자가 적혀 있을 때, A와 B가 서로 리프를 제거하는 것을 반복할 때 A가 $1$을 하나라도 지울 수 있을까?이것저것 관찰할게 좀 많다. 우선 1이 써진 정점이 적어도 하나 있다고 가정하자. 1. 1이 리프면 A가 승리한다.2. $N$이 짝수면 A가 승리한다.1이 써진 정점이 리프면 1에 ..
2024 Rewind 사실 이런 글을 쓸 생각이 별로 없었는데, 친구가 써서 나도 쓰게 되었다.01.06. Hello 2024고등학교를 졸업하기 직전, 최고의 퍼포먼스를 갱신시키며 International Grandmaster라는 타이틀을 얻었다. 그 대회가 있기 전까지는, 한 해를 꽤나 잘 시작했다고 생각했었다.고등학교에 입학하기 직전 레이팅이 1784이었고, 저 라운드 직후 레이팅이 2610이었으니, 고등학교 3년 동안 826점이나 올렸다.02.20. 카이스트 입학카이스트에 입학했다. 당시의 사진을 찾아보려고 했는데 못 찾았다. 입학식날은 비가 왔다.3월~7월딱히 이렇다 할 일정이 없다. PS 동아리인 RUN에 가입해 ps하고 공부하고 과제하는 것만 반복했다. 다이아스트릭도 이때쯤 시작했다.1학기때 들은 과목을 소개하자면..
제 1회 피갤컵 후기 ps 갤러리에서 대회를 연다고 해서 참여해보았다.  나보다 잘하시는 분들이 꽤 많이 참가하셨는데, 운이 좋아서 이길 수 있었다. 아마 G를 빨리 푼게 크게 작용했던 것 같다. 또한 운 좋게 추첨에 당첨되어 버거를 하나 더 받을 수 있었다.   전반적인 문제 퀄리티는 정말 좋다. 전형적인 문제가 거의 없고, 쉬운 문제와 어려운 문제 모두 재미있다. 특히, 전반적으로 구현이 매우 짧고 깔끔하다.간단한 문제 풀이A: 제한이 작아서 무슨 방법을 써도 다 풀린다. 나의 경우, 앞에서부터 보면서 PS4나 PS5가 나올때마다 숫자를 제거하는 방법으로 $O(N)$에 풀었다.B: $i$라운드만에 $K$명을 뽑을 수 있는지 판정하려면 주어진 모든 문자열들의 크기 $i$의 prefix들만 고려할 때 $K$번 이하로 등장한 ..
2024년 6월 PS 일지 요약BOJ시험기간 등 위기가 많았지만, 매일 다이아 한 문제 이상 풀기에 성공했다. 스트릭이 매일 오전 6시에 초기화되는데, 오전 5시 30분이 넘어 겨우 맞은 날이 6월에만 적어도 3번은 되는 것 같다.개인적으로 재미있었던 문제는 다음과 같다.좋은 수열(31442)Bit Shift Registers (22048)Led-led Paths (16659)Gross LCS (24691)Library 3 (32002)코드포스7월을 하루 앞두고 코포 레이팅도 IGM을 회복하는데 성공했다. 이제 크게 망하지 않으면 2500~2700의 퍼포먼스가 안정적으로 나오는 것 같은데, 다이아스트릭의 영향이 있는 것 같다. 이대로만 간다면 연말에는 2700을 찍을 수 있지 않을까? 18913. Graph Coloringhttp..
2024년 5월 PS 일지 지금까지는 임의의 주기로 ps 일지를 작성했지만, 아마 이제부터는 꾸준히 ps일지가 올라올 예정이다. 언제까지 가능할지는 모르겠지만, 5월 셋째주부터 다이아 문제로만 스트릭을 잇는 것을 시도해 보고 있다. 푼 문제 중 풀이가 기억이 나는 문제만 작성했다. 15773. Touch The Skyhttps://www.acmicpc.net/problem/15773더보기고도 제약 조건을 다음과 같이 바꿀 수 있다.풍선을 사용했을 때 고도가 $L_i+D_i$ 이하이면 풍선을 사용할 수 있다.그런데 이 문제는 deadline이 있는 스케줄링 문제와 동치이다. 따라서 deadline 오름차순으로 보면서 해당 풍선을 사용하고, 만약 사용으로 인해 해당 풍선이 deadline을 침범한다면 사용한 풍선 리스트에서 가장 $D..
2024년 1월 PS 일지 수학이 더 많다. 문제 뒤의 (O)는 풀이 없이 풀었다는 뜻이고, (X)는 풀지 못하고 풀이만 확인했다는 뜻이다. ps문제의 경우 (△)는 풀이를 까고 업솔빙했다는 뜻이다. 1. IMO Shortlists 수올 공부를 안 한지 3년은 된 것 같은데, 정말 오랜만에 다시 시작했다. 대수, 기하, 정수는 기초만 알아서 손도 못 대겠고, 그나마 조합 분야가 풀리는 것 같다. (이마저도 어려운건 못 풀겠다) 1.1. 2001 IMO Shortlist C3 (O) Define a $k$-clique to be a set of $k$ people such that every pair of them are acquainted with each other. At a certain party, every pair of ..
2023 나는코더다 송년대회 이야기 나코더 송년대회는 2016년 경기과학고 32기에서 처음 개최하여 지난 7년간 매년 연말에 개최되어왔다. 올해는 내가 있는 나코더 39기가 대회를 열어야만 했다. 대회 문제들은 나, 문정후(mjhmjh1104), 채이환(chaeyihwan), 이동현(kizen)이 출제했다. 내가 5문제, 이동현이 3문제, 채이환과 문정후가 각각 2문제를 출제했다. 대회 결과 본대회 스코어보드 오픈 콘테스트 스코어보드 의도한 것 보다는 솔브 수가 많이 적었으나, 상위권 분포가 생각보다 잘 나왔다. 1, 2, 3등 팀이 각각 39, 41, 40기 팀이다. 대회 문제 출제 문제 아이디어를 모으는 것은 2년전 나코더 40기 선발고사 때부터 시작했다. 그때 생각한 문제 중 일부는 40기 선발고사에 냈다. 내가 출제한 문제 중 어떤..
728x90

티스토리툴바