$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

본문 바로가기

알고리즘 문제풀이/PS_Weekly

 (10)
2020 10월 PS 일지 중간고사 기간이라 몇개 없다. :( 다음달부턴 학교 공부 내용도 뭐 했는지 조금씩 정리해서 따로 적어볼 생각이다. 나중에 기억나는데 도움이 될것 같아서... Rounds Codeforces Round 678 (Div.2) : 1077th, -42. Div2D 못풀어서 떡락했다. 그렇게 어렵지 않은 이분탐색 + 트리 DFS 정도로 생각했는데 놓친 부분이 있었던 듯. Codeforces Round Edu97 : 320th, +22 시간이 약간 모자라서 E번 코딩을 못 끝냈다. 대략적인 풀이는 이분탐색 + LIS 응용인데, 세그트리를 쓰는 구현이 오히려 조금 더 쉬웠다는 것 같다. 다음날 dhdroid랑 F번을 업솔빙했다. Problems 2020 중앙대학교 프로그래밍 대회 검수를 맡았다. www.acmicp..
9월 2-3주차 PS 정리 최적화 이론 과목의 과제와 소개원실 프로젝트에 시달리고 있다. 이번 학기는 소개원실에 내 생각과 무관하게 바쳐질 예정이었으므로 그러려니 하는 중. 하루에 한시간씩이라도 시간 내서 알고리즘 공부도 계속하려고 하는데 뭔가 잘 안 된다. Rounds SNUPC Division 2 : 7등 (3등상). gratus907.com/122 에 포스팅했다. 좀더 침착하게 구현하는 연습이 필요하지만 대체로 실력만큼 했다고 생각한다. Codeforces Round Edu95 : Unrated A번과 B번에서 오류가 발생해서 라운드가 언레당했다. C까지 풀고 언레된걸 알고나니까 뭔가 앞에 A에서 날려먹은 시간때문에 그러지않아도 별로 하고싶지 않았던 터라 던졌다. Codeforces Round 669 (Div2) : 665t..
9월 1주차 PS 정리 (8.31 - 9.6) Rounds - SCPC 2020 Round 2 : 별도 포스팅 (쓰고 있다). 크게 망했고 정말 힘들었다. ㅋㅋ;;; - Codeforces Round 666 (Division 1) : 별로 재밌는 문제는 없었다. AB는 쉽고, C번은 너무 케이스가 많아서... +51점 (2051) - AtCoder Beginner Contest 177 : F번을 어떻게 풀지 전혀 감을 못 잡았다. 흠... +37점 (1921) - ICPC 신촌 Summer Camp Open : SCPC 망하고 다음날이기도 하고, 각종 과제가 있어서 조금만 하고 나올 생각이었는데 아무튼 힐링하면서 8문제를 풀고 3시간 만에 도망쳤다. 문제/풀이 (8월 중에 푼것도 포함되어 있다) BOJ 19559, Baltic Olympiad of ..
7월 2 ~ 4주차 PS 정리 주로 UCPC 2020을 위해 팀원들이랑 공부한거랑, 일주일에 한번씩 도는 dlwocks31과의 1:1 세션에서 푼 문제들이다. BOJ 8903, ICPC Daejeon Regional 2011 D번 "Equipment" (장비) 난이도 : Solved AC Platinum 3 최대화해야 하는 지표가 5개뿐임을 관찰하자. 또한, $\binom{n}{k}$ 개의 조합을 모두 볼 필요가 없는데, $k >= 5$ 이면 지표 $a, b, c, d, e$에 대해 각각을 최대화하는 장비 5개를 모두 고를 수 있고 나머지 전부는 무의미하기 때문이다. 즉, $k = 2, 3, 4$ 에 대해서만 풀자. $k = 2$ 일 때를 예로 들어 생각해 보면, 5개의 stat 중, 몇개는 장비 1에서, 나머지는 장비 2에서 올 것..
6월 ~ 7월 1주차 PS 정리 결국 1학기가 종강하고 나서야 PS를 다시 조금씩 시작했다. :( 앞으로 이렇게 묶어서 포스팅할때는 코드를 Github을 이용해서 올리려고 한다. BOJ 16440, 경북대학교 Goricon 2018, "제이크와 케이크" 난이도 : Solved AC Platinum 5 s와 k가 나열된 문자열을 최소 개수의 연속된 조각으로 자르고, 이를 재배열하여, 양쪽이 같은 개수의 s와 k를 가질 수 있게 하는 문제이다. 답이 2 이하라는, 즉 2번의 커팅으로 문제를 반드시 해결할 수 있다는 놀라운 Claim을 증명하려고 한다. 이는 다시 말해, 하나의 $n/2$짜리 연속한 segment가 $s$와 $k$를 동수로 포함하도록 자를 수 있음을 의미한다. $n/2$ 개 짜리 연속된 구간을 먼저 잡고, 이를 오른쪽으로 살..
4월 3, 4주차 PS 정리 그나마 Red Army Study와 dlwocks31이랑 연습하면서 푸는 문제들이 있어서 조금 알고리즘 공부하는 시간이 늘었다. Google Code Jam Round 1B에 참가했고, 319등의 성적을 거뒀다. https://gratus907.com/103 9문제 + Codejam이 있으니 11문제라고 생각하기로 했다. ㅋㅋ 레드아미의 경우, 2주차 셋은 개인적으로 괜찮았지만 3주차 셋은 공부하는 의미가 없었다. 여기 기술된 문제 중 2주차에 해당했던 문제는 Palindrome, Sad Powers, Queue, Red-White Fence의 4문제이고, 3주차의 경우 한 문제도 적지 않았는데, 어쩌다보니 문제가 다 사전지식만 있으면 금방 뚝딱하는 문제거나 끔찍한 구현에 시달리는 문제가 뽑혀서... B..
4월 1, 2주차 PS 정리 왤케 요새 안하지.... 딱히 할 시간이 없냐면 그건 또 아니다. (주로 롤토체스에 빠져 살고 있다) 5문제. 난이도 순 (아마도) 그나마 SNUPS Red Army를 시작해서 문제풀 동기가 조금 더 생겼다. Red Army는 작년에 TAMREF님이 개설한 스터디를 올해 내가 이어서 하고 있는데, Codeforces 기준 블루~오렌지 정도 실력을 가진 사람들이 조금 어려운 문제 (2000+) 를 일주일동안 몇개 풀고 디스커션을 하는, 스터디 그룹 같은 느낌이다. 다음주에는 Red Army 2주차를 최대한 풀고 풀이를 작성하는걸 목표로 하고 있다 (2주차부터는 이상한 사람들의 영향으로 2600, 2800 문제가 들어가 있기 때문에 다 풀긴 조금 무리가 있다) Codeforces Round 635 (Div1..
3월 3, 4주차 PS 정리 7문제, 난이도 순. 온라인 개강이라 시간이 널널할줄 알았는데 생각보다 과제가 많아서 PS를 못 돌고 있다. BOJ 11405 책 구매하기 난이도 : Platinum 4 MCMF가 무엇이고 어떻게 구하는지 공부할 때 푸는 기본 구현 문제. 플로우 같은 고급 알고리즘을 너무 모르는 것 같아서 MCMF를 공부하고 구현을 (적당히 팀노트를 베껴 가며) 해봤다. 아직 응용해서 MCMF 문제를 모델링해서 풀기에는 갈길이 먼것 같다. 팀노트에 넣어놓은 MCMF가 잘 도는지 확인하는 문제라고 할 수 있겠다. Atcoder Beginner Contest 160F, Distributing Integers Atcoder 난이도 1962 대략적으로 문제를 설명하자면, 정점 1부터 $N$까지로 구성된 트리에서, $x$ 번을 ..

티스토리툴바