PS/Problem Solving(124)
-
2021년 1월 22일 PS일지
1. 이분매칭 연습문제 1017 소수 쌍✔ - 모델링 모르겠어서 풀이보고 짬. 홀수 / 짝수 모델링 처음에 동일한 집합 간 이분 매칭을 시도하려 그랬는데 어림도 없다 이분 매칭은 항상 '이분' 되어야 함을 명심하자. 2. PST 연습문제 11932 트리와 k번째 수✔ PST 사용한다는 말만 듣고 혼자 풀었는데, 기분 정말 좋다!! 당분간 사용할 PST 구현 13538 XOR 쿼리 16977 히가큰직쿼
2021.01.22 -
If you are a Newbie in Competitive Programming
There was a question in Codeforces recently. Talking about "I'm such a Newbie in Codeforces.. What should I do?" This is a quite boring question since there are tons of same questions. So it got many downvotes, obviously. However, I wanted to reply him because I was once a Newbie too. My Reply If you are thinking Codeforces as a 'tutorial' site, you are in the wrong place. That's why you are get..
2021.01.21 -
2021년 1월 21일 PS 일지
1. Persistence Segment Tree 연습문제 풀이 www.acmicpc.net/problem/11932 11932번: 트리와 K번째 수 첫째 줄에는 두 개의 양의 정수 N과 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 각 정점의 가중치를 나타내는 N개의 정수가 주어진다. i번째 정수는 i번 정점의 가중치이다. 이 가중치는 모두 www.acmicpc.net 트리와 K번째 수 문제는 푸는 중이다 풀이 보기 전에 어제 풀었던 Component Tree 내용을 이용해 O(N log^3 N) 풀이를 짰으나 장렬히 시간초과가 난다. 덕분에 LCA 복습했다 ^^ HLD로 비슷하게 할 수 있을 것 같으나 역시 시간초과가 예상된다. 잠깐 다른 과목 밸런스 맞추러 갑니다. 한동안 PS에..
2021.01.21 -
2021년 1월 20일 PS 일지
1. Segment Tree 연습문제 마무리 2014-2015 ACM-ICPC, NEERC, Southern Subregional Contest C. Component Tree codeforces.com/gym/100513/problem/C Problem - C - Codeforces codeforces.com 분명 간단한 세그트리 연습문제라 들었건만 정말 어렵다 2시간 이상 고민했는데 풀이가 안 나와서 풀이를 찾아봤다. 정말 다양한 풀이를 봤지만 이해가 안됨. 오히려 HLD 쓰는 풀이를 이해해버려서 세그 쓰는 풀이를 탐색 중임. 그냥 혼자 생각하기로 함. 일단 property 별로 생각하는 것은 명백하다. 어떤 노드가 property를 가지고 있다. -> 자신의 subtree에 영향을 미친다. 결국 구..
2021.01.20 -
2021년 1월 19일 PS 일지
코포 참여합니다~ codeforces.com/blog/entry/86882 Codeforces Round #696 (Div. 2) - Codeforces codeforces.com A: 관찰이 조금 늦어서 큰일났다는 생각을 했다. a와 b를 bit sum 한 다음 d를 만드는데 비트 1과 1을 더하면 10이 되는게 아니라 2가 된다. ex) 110 + 110 -> 220 그런데 연속된 값이 있으면 20 이렇게 자릿수가 줄어든다. b가 주어질 때 a+b의 최댓값을 찾기. (a와 b의 자릿수는 정해져 있음) 앞자릿수가 가장 크고, 자릿수가 안 줄어든게 이득. 그런 경우는 딱 한가지 밖에 없다. 맨 앞자릿수를 1로 고정시키고 다음 자릿수로 넘어갈 때 인접한 비트의 합이 안 같은 경우로 고른다. 두가지 선택지가..
2021.01.19 -
PS일지 중간 점검
날짜 한 일 배운 점 1/7 PS일지 작성 결심, Kquery, 레이지세그 기본에 충실하자. 세그에서도 모르는게 많다 1/8 코포 Div2 #695 + C,E upsolve ad-hoc을 더 충실히 할 필요가 있다. C는 쉬웠는데 많이 말린듯 1/9 게임이론 과도한 계획은 실천하기 어려움 1/10 게임이론 계획을 줄였으나 역시 과도했음 1/11 세그 연습문제 가가두점(가장 가까운 두 점) 공부 set,map은 std::lower_bound에서 O(N)에 동작함. 꼭 내장함수를 이용하자 1/12 버추얼 과도한 계획은 실천하기 어려움. 생각을 멈추고 먼저 해버리자. 1/13 염소 줄서기(다이아4) 거의 처음으로 스스로의 힘으로 다이아 문제를 풀었다. 최소 외접원 및 Convex Hull 복습 하면 된다. 1..
2021.01.18 -
2021년 1월 18일 PS 일지
1. PBS 마무리 Calculating Average라는 문제를 오늘 끝내버린다. 그동안 미뤄 왔는데 오늘 날 잡고 끝내버리기로 결심했다. Calculating Average 맞 았 다! pbs를 엄청 효율적으로 적용하는 방법도 있던데 그것은 300iq님의 코드를 참고하자. CHT를 Persistent하게 관리한다. 2. Segment Tree 연습문제 풀기 codeforces.com/gym/100513/problem/C Problem - C - Codeforces codeforces.com 3. Persistent Segment Tree 드디어 대망의 Persistent Segment Tree를 공부한다. 2021/01/18 - [Problem Solving/알고리즘 이론 정리] - Persisten..
2021.01.18 -
2021년 1월 17일 PS 일지 - K보다 작은 수의 개수 쿼리
클래스 7에 들어갔는데 재미있는 문제들이 보인다. -> "수열과 쿼리 1" 그중 예전에 풀었던 KQUERY와 연관된 문제가 여럿 있어 모두 AC를 띄우고 왔다. 달달하다~ K Query2 같은 경우 구간에서 k 이상인 수 개수 쿼리 + point update를 처리하는 문제인데 대부분 sqrt decomposition으로 풀었지만 내 풀이는 좌표압축 + BIT in Seg로 O( log^2 N)에 각 쿼리를 처리 가능하다. 하지만 시간은 웬지 모르게 평방분할보다 느리다. 세그가 복잡한 연산이여서 그렇다고 생각한다. Geeks for Geeks 평방분할 풀이 - www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray-set-..
2021.01.17 -
2021년 1월 16일 PS 일지
1일 3BOJ www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 해싱 연습문제 내가 즐겨쓰는 소수들: 5e5+9, 5e5+29, 1e9+7, 1e9+9, 1e9+21 1e9+21은 잘 알려져 있지 않은 소수이기 때문에 저격을 피할 수 있어 좋다. 머,,, 대부분 저격해놨다면 랜덤을 쓰자. 정렬하면 쉽게 풀 수 있겠지만 일부러 해싱을 써 봤다. 생각나는 또 다른 풀이로는 정렬한 다음 투포인터를 써서 비교 과정을 O(n)으로 구현할 수 있겠다. ..
2021.01.16 -
How to win Gold Medal in IOI
usaco.guide/dashboard/ Dashboard A free collection of curated, high-quality competitive programming resources to take you from USACO Bronze to USACO Platinum and beyond. Written by top USACO Finalists, these tutorials will guide you through your competitive programming journey. usaco.guide https://codeforces.com/blog/entry/69100 My winning theory in IOI 2018 & 2019 — Why I won 2 golds in IOI - C..
2021.01.15 -
2021년 1월 15일 PS 일지
Educational Codeforces Round 102 (Rated for Div. 2) Dashboard - Educational Codeforces Round 102 (Rated for Div. 2) - Codeforces codeforces.com 나름 잘했다고 생각한다. 다만 에듀코포여서 모든 문제의 점수가 같다 따라서 빨리 풀고 적게 틀리는게 관건 C를 못 푼게 살짝 심각.. 코포에서 자주 쓰이는 알고리즘을 저장한 템플릿을 어서 빨리 만들어야 겠다. B,D,E 구현이 느렸다 E는 재밌는 문제다. 고급 알고리즘 시간에 다룬 그래프 변환을 여기서 써먹게 됐다. 주어진 그래프를 문제의 정답을 그대로 유지하되, 정점과 간선을 추가/삭제하는게 그래프 변환이다. 여기서는 정점을 상태에 따라 여러 정점으..
2021.01.14 -
2021년 1월 14일 PS 일지
맞왜틀; 오늘 PST 하는 날인데 ㅜㅜㅜㅜㅜ 맞왜틀에 빠졌다 ㅡ.ㅡ www.acmicpc.net/problem/17236 17236번: Heights 각 줄에 실존하는 삼각형의 높이 값 ha, hb, hc가 각각 주어진다. ha, hb, hc는 실수이며, 0.01 ≤ ha, hb, hc ≤ 100.00이다. www.acmicpc.net 기하 + 부동소수점 오차 빡친다.... 오늘 PST 하고 BOJ 3솔은 내일 해야겠다. 1/13에 적은게 1/14에 3솔했다고 생각하면 됨.
2021.01.14 -
2O21년 1월 13일 PS 일지
오늘은 블로그에 글을 쓰는 날! 이 PS일지로 대신하자. 이론 글 쓰는건 정말 귀찮다r. 1.롯데 자이언츠와 가희 1. www.acmicpc.net/problem/20653 20653번: 롯데 자이언츠와 가희 첫 번째 테스트 케이스의 경우, 문제의 조건을 만족하는 수열은 [6, 12], [12, 6] 의 2가지입니다. 두 번째 테스트 케이스의 경우, 조건을 만족하는 수열은 존재하지 않습니다. www.acmicpc.net 조가희님이 오픈톡방에 올린 문제! 어떤 수 X가 주어졌을 때 n개의 수가 각각 d1^e_i_1 * d2^e_i_2 * d3^e_i_3 ... 의 꼴로 표현될 때 (d_i는 소수, e_i는 음이 아닌 정수)로 표현된다면 d1^max(e_1) * d2^max(e_2) .... = X가 되는 ..
2021.01.14 -
2021년 1월 12일 PS 일지
이제 일기처럼 쓰고 있다. 오늘은 코포 버추얼을 도는 날이다. 목요일에서 금요일로 넘어갈 때 에듀코포가 있다. 목요일날 건 오전에 하고, 새벽 2시까지 코포를 친 다음 (만약 할게 있다면) 업솔빙을 일어나서 하자. 이를 대비하기 위해 에듀 코포 버추얼을 돌겠다. codeforces.com/contest/1469 Dashboard - Educational Codeforces Round 101 (Rated for Div. 2) - Codeforces codeforces.com 문제는 안 읽어 봤다. 6시 쯤 돌 듯? 구글링 하다가 u.icpc.global/lectures/ Lectures Lower Bounds for Multiplication and Integer Sorting via Network Cod..
2021.01.12 -
2021년 1월 11일 PS 일지
7 - 성공 8 - 성공 9 - 실패 10 - 실패 아무래도 거창한 계획을 세우면 실패하나 보다. 지나간건 잊어버리고 오늘 PS한 걸 적는다. 다시 무계획의 삶으로~ www.spoj.com/problems/POSTERS/ SPOJ.com - Problem POSTERS ... www.spoj.com 오늘은 이걸 푸는 것으로 시작했다. ㅇㄴ ㅋㅋㅋㅋ 처음에 엄청 어려운 문젠 줄 알았으나 예전에 이미 풀어본 문제다. code.sasa.hs.kr/problem.php?id=1317 SASA OJ discuss3 첫 번째 줄에 벽의 조각 수 n과 벽에 색칠하기의 반복 횟수 m이 입력된다. 두 번째 줄에 1부터 m까지의 벽의 폐구간 [a, b]와 페인트의 색 번호 c가 공백으로 구분되어 입력된다. [입력값의 정의..
2021.01.11 -
2021년 1월 10일 PS 일지
어제 욕심이 과도했다 계획한거 하나도 안 끝내고 자버림! 이쯤되면 일상과 PS의 공존이 주내용 우선순위를 살짝 틀어서 1. 게임 이론 2. 수학 숙제 3. 학교 일 어제 교훈을 얻었으니, 2,3번은 하기 싫으면 안해도 된다는 결론을 내렸다. ㅋㅋㅋㅋㅋㅋ 이렇게 가자. Atcoder은 정 하고 싶으면 화요일날 버추얼 가야지! UPD1 게임 이론을 공부하기 위해 실제로 국제 게임 토너먼트에 참가했다 5명 중 2등했고, Stage 2로 간다. 당분간 디코 계속 켜야겠네 🤣
2021.01.10 -
2021년 1월 9일 PS 일지
어제 필요한 업솔빙을 다 하고 자서 기분이 좋다. 오늘은 원칙 상 블로그 글 쓰는 날이다. ARC가 오늘, ABC가 내일 있던데 해도 될까? 결론을 내렸다: 최근 공부한 게임 이론을 포스팅하고, 수학 숙제를 끝내고, 오답 노트를 완성한 다음, 학교 일을 마무리한 다음 라운드를 돌리기로 ㅎㅎ UPD: 과도한 계획은 할 수 있던 것도 못 끝내게 합니다. 다음 날로 넘어가주세요
2021.01.09 -
2021년 1월 8일 PS 일지
다른 분들처럼 막 거창하게 쓸거 아니다. 나만의 방식으로, 매일 쓰는게 목표다. 레이지 연습문제 하나 풀려 그랬는데, 그러지 말고, 수업 시작 전에 (월,목) 풀 테스트 문제로 남겨두었다. 그날은 테스트 문제, PST, CosmoCraft를 푸는게 학습 목표. 오늘은 Codeforces Round #695 (Div. 2)에 참가할거다. 7분 뒤 시작! 끝나고 간단한 후기 남겨보겠다. Codeforces Round #695 (Div. 2) 끝나고 Div2 치고는 어렵다는 평이 많았다. Worst contest 이런 댓글도 있었는데 반응이 좀 과하다는 생각이 든다. C를 잡다가 D로 넘어갔는데 이건 굉장히 좋은 선택이었다. A는 그리디 B는 Brute Force C는 Case Work D는 dp + pref..
2021.01.08 -
2021년 1월 7일 PS 일지
자기 전까지는 오늘이 맞지~ www.commonlounge.com/discussion/f6052177ea3543439251079f57f480e0 요기 옛날에 하다가 접었었는데, 초반 문제들이 너무 쉬운게 원인이다. 어려운거부터 해야지 보니까 어려운게 없다 ㅋㅋㅋ 엄청 대단한건줄 알았는데 별거 없네. 이래서 사람은 어떤거든 시작하고 봐야 한다. 일단 하기로 이미 글을 적어 놨으니, 모르는걸 찾아서 공부한다. 1. Augmented Segment Tree 코포 링크로 연결된다. PST 등 모르는 개념이 있어서 함께 공부하기로 한다 첨에 세그먼트 트리를 개념을 한 번 읽어봤다. 이미 알고 있는거여서 개쉽네~ 하고 넘기려다가 예제 문제 들어가봤더니.. 어렵네? 이때 이상함을 느끼고 기초부터 다잡고 가기로 했다...
2021.01.08 -
겨울방학
매일 1개 이상 하기~ 정해 놓은 로드맵은 다음과 같음 월 목 -> IOI Program 화 금 -> 코포 버추얼 / 라운드 수 토 -> 블로그 글 - 공부한 알고리즘 or 코포 - 하고 싶은거 일 -> 알고리즘 책 독서실에서 풀기 (전자기기 X) 하면 된다 여기에 동기부여용 시스템을 하나 만든다. 매일 실천한 내용을 정말 조금이라도 적는다. 그래야 계속하기가 훨씬 재밌따. 난 각 잡고 글 쓰는 것보다 이렇게 의식의 흐름대로 글을 쓰는 것을 정말 좋아한다.
2021.01.08 -
신기한 Contest
atcoder.jp/contests/hokudai-hitachi2020 Hitachi Hokudai Lab. & Hokkaido University Contest 2020 - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp Marathon 형식의 Contest를 몇 번 봐 왔는데 이렇게 한달 동안 하는 건 처음 본다. 나중에 심심할 때 해보기~
2021.01.03 -
프로그래밍으로 수학하기
이버 확률과 통게 보고서를 생각했던 주제를 누가 이미 했다 ㄷㄷ 적분을 울프람 알파가 못해서 끙끙대고 있었는데 이 분은 중적분을 파이썬으로 수치적분해버렸다. (내가 몰라서 그렇지 매트랩으로도 가능할 것이다.) ok97465.github.io/2018/09/180911_DistanceBetweenTwoPointsOfQuadrate 수학 신호/영상처리 Python/C++ 코딩 수학, 레이다, 신호처리, 영상처리, Python, Programming 에 대해 공부한 부분을 정리해 두는 개인 블로그 입니다. ok97465.github.io 이거 보고 수학에 입문하고 싶다.
2020.12.29 -
제 1회 세종정보올림피아드
제 1회 세종정보올림피아드 후기 제 1회 즐겁게 고등부 1등 먹고 왔습니다. 친구들과 택시 타고 세종 SW 교육센터에 도착. 12시~12시 30분 사이 입실이라 근처에 있는 칼국수 집에서 든든하게 한 그릇 뚝딱. 오후 1시부터 5시까지 4시간 동안 진행했습니다. 풀이 스케치 A: 스위핑 문제. 일단 기지국이 원점이 되도록 좌표들을 평행이동한다. 레이저가 일직선 형태로 나아가므로 점들을 x>0 인 것과 x
2020.12.20 -
The J-th Number
The J-th Number 10641번: The J-th Number You are given N empty arrays, t1,…,tn. At first, you execute M queries as follows. add a value v to array ti (a ≤ i ≤ b) Next, you process Q following output queries. output the j-th number of the sequence sorted all values in ti (x ≤ i ≤ y) www.acmicpc.net 진짜 너무 화났지만 재밌는 문제다. PBS가 무엇인지는 이 글 참고. Range Update, Range Sum Query가 필요하므로 당연히 처음에 Lazy Propagation..
2020.12.17 -
병렬이분탐색 & 최소신장트리
www.acmicpc.net/workbook/view/5749 문제집: 병렬 이분 탐색 (pentagon03) www.acmicpc.net 최근 병렬이분탐색 문제를 많이 풀었는데, 모든 해결 소스의 실행 시간이 매우 긴 것을 확인했다. 실행 시간이 짧은 사람들의 코드를 확인해봤는데 대부분 최소 신장 트리라는 개념을 사용하더라. 대표적으로 승현이와 승현이, JOI 국가의 행사, Ski Course Rating 등이그렇다. -관련 설명 tamref.com/65 공부해보자.
2020.12.16 -
Codeforces Round #690 (Div. 3)
실력이 느는게 실감이 간다. System Test, Hacking을 조금 더 지켜봐야겠지만 웬만해서는 핵 당할 일은 없을 것이다 UPD: E2 TLE E2에서 심각하게 절었는데 페널티 덕분에 실시간으로 순위가 밀리는 걸 관찰했다 '-' 하지만! 그 덕분에 핵 당할뻔한 E1 코드를 고칠 수 있어서 만족한다. 생각 없이 눈에 보이는 것만 수정하고 코드를 다시 제출하는 습관을 버려야된다. 페널티를 쌓는 주 원인이다. A: Favorite Sequence 0:04 AC 투 포인터처럼 배열을 양 끝에서 번갈아 출력하면 된다. B: Last Year's Substring 0:15 AC 이렇게 오래 끌 문제가 아니다.. 주어진 문자열에서 합쳐서 "2020"이 되는 prefix, suffix가 존재하는지 묻는 문제. ..
2020.12.16 -
알고리즘 프로그램
www.commonlounge.com/discussion/5d2822257dfa49328d85fd27cf114441 Competitive Programming: From Beginner to Expert | CommonLounge This is a very comprehensive 94-part course on competitive programming. It gets you from knowing basic programming to being a yellow-red rated coder on Codeforces / CodeChef / TopCoder / etc. The primary objectives of this course are to learn about 30 diff www.commonlo..
2020.12.15 -
Slope Trick
이론 정리 게시물로 이동해주세요 howtoliveworldnice.tistory.com/477 Slope Trick - 함수 개형을 이용한 최적화 Special Thanks to Cgiosy Slope Trick: 함수 개형을 이용한 최적화 백준 13323 BOJ 수열 1 풀이 백준 13324 BOJ 수열 2 풀이 WhiteBoard Tutorial BOJ수열1 BOJ수열2 howtoliveworldnice.tistory.com 공부한 기록 12/14 : 21:40 ~ 23:20까지 블로그 글과 코드포스 글을 열심히 읽었으나 이해 실패 cgiosy 말로는 스스로 종이에 그래프 그려가면서 하는게 훨씬 이해가 잘된다고 한다. 다음 Try 때는 그렇게 한다 Slope Trick 공부하는 문제 jwvg0425-..
2020.12.14 -
ABC 184
AtCoder Beginner Contest 184 AtCoder Beginner Contest 184 - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp A : 하면 된다. B : string, cin 쓰면 공백 처리 편해서 좋다. D : C번보다 관찰이 쉬웠다. 기댓값 DP C : 사람에 따라 헷갈릴 수 있는 문제. 두 점이 주어지는데, 한 점을 원점으로 하도록 평행이동하는게 구현상 편하다. 대부분 2번만에 게임을 끝낼 수 있음을 관찰하면 문제가 쉽게 풀린다. F : Meet in the Middle. ..
2020.11.26 -
2020년 세종과학예술영재학교 정보올림피아드 풀이
※2020/11/23 - [Problem Solving] - 2020년 세종과학예술영재학교 정보올림피아드 후기에서 문제 풀이를 분리한 글입니다. 문제 소개 및 풀이 문제 체감 난이도와 사용 알고리즘은 다음과 같습니다. 문제 난이도 : A < B < D < C 핵심 알고리즘 : A 누적합 배열, B 투포인터, C 다이내믹 프로그래밍, D 세그먼트 트리 문제 A: 할로윈과 별사탕(L) 크기 N 배열에서 주어진 위치 k를 제외한 모든 위치에 x를 더하는 쿼리를 M번 처리하는 문제입니다. 모든 쿼리를 처리한 후 최종 배열을 출력해야 합니다. $ 1
2020.11.23