$$\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' 카테고리의 글 목록::::Gratus' Blog

"알고리즘 문제풀이/PS_Weekly" 관련 글 10

2020 10월 PS 일지
알고리즘 문제풀이/PS_Weekly 2020. 11. 2. 22:42
중간고사 기간이라 몇개 없다. :( 다음달부턴 학교 공부 내용도 뭐 했는지 조금씩 정리해서 따로 적어볼 생각이다. 나중에 기억나는데 도움이 될것 같아서... 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 정리
알고리즘 문제풀이/PS_Weekly 2020. 9. 20. 18:26
최적화 이론 과목의 과제와 소개원실 프로젝트에 시달리고 있다. 이번 학기는 소개원실에 내 생각과 무관하게 바쳐질 예정이었으므로 그러려니 하는 중. 하루에 한시간씩이라도 시간 내서 알고리즘 공부도 계속하려고 하는데 뭔가 잘 안 된다. 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)
알고리즘 문제풀이/PS_Weekly 2020. 9. 13. 14:17
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 정리
알고리즘 문제풀이/PS_Weekly 2020. 7. 26. 18:33
주로 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 정리
알고리즘 문제풀이/PS_Weekly 2020. 7. 4. 02:44
결국 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$ 개 짜리 연속된 구간을 먼저 잡고, 이를 오른쪽으로 살..
admin

티스토리툴바