노력하는 공대생의 공부일지

점수를 올리기 위해서 많은 팁과 방법들이 있을 것이다. 근본적인 해결책은 실력을 올리는 것. 플레티넘을 마구마구 밀어버리는 실력을 우선적 목표로 해야겠다.. 어려운 문제를 요즘 너무 안푸는데 많이 풀어야 겠다.

13536을 풀며 머리를 탁 치고 짠 후 24915를 풀었다. 문제 풀이에 비하인드가 있는데, 24915는 한 이틀정도 고민한 문제였다. 고민했는데 모르겠어서 풀이를 찾아보려 해도 최근 문제라서 풀이가 없다;;; 그래서 포기했었다. 오늘 학회 채점현황에서 20052 가 풀렸는데, 나는 아직 안 풀려 있길래 풀었다. 그래서 세트로 13536을 풀어보려 갔는데, 이것도 안풀림;; 한 1시간 정도 고민하다가 설마 금광 세그? 라는 생각으로 들어갔는데 바로바로 풀려버린다. 13536은 struct로 3개를 관리해주면 된다. 이건 설명이 어려워서 생략하고 24915 중심으로 설명을 해보자면, 어떤 구간 [l , r]을 나타내는 노드에 대해서 1. l> b >> c; if (a == 1)update(b - 1, c..

자기 pr의 시대라고 한다. 여기서 pr은 public relation의 약자이다. 즉 대중과 나의 관계 맺기. 요즘 세상에서 '나'라는 존재를 스스로 홍보해야 한다는 것이다. 나는 이러한 경향성이 마음에 들지 않는다. 아직 알바의외에는 (그것도 학원 알바) 사회 경험을 해본적이 없는 나로써는, 그다지 많은 인간상을 만나봤다고는 할 수 없을 것이다. 그래도 살아오면서 느낀 점 중에 하나는, 나는 허세를 정말 싫어 한다는 것이다. 고등학교 때부터 그랬다. 그래서 의도적으로 그런 친구들을 멀리하고는 했다. 어쨌든 본론으로 돌아가보면, 자기 pr의 시대는 허세와 비슷한 맥락에 놓여있다고 생각한다. 물론 진짜 실력이 있는 사람들은 당연히 존재한다. 그런데 가짜들이 너~~~무 많아서 찾기가 어렵다. 그리고 보여주..

2022년 3월 26일 즈음 팀연습으로 풀어보았던 셋이다. 일주일이 지난 지금 시점 한 문제 빼고 모든 문제를 업솔빙해서, 풀이를 올려보고자 한다. 개인적으로 에듀케이셔널 한 느낌이 강한 측면이 있었다. 구현/지문이 더럽지 않아서 너무 좋았다. dp가 많이 나오는 듯한 경향은 우리나라랑 잘 맞는듯 하기도 하다. 연습셋 하기 전에 처음이니까 쉬운셋 하자고 해서 골랐고, 연습 때는 C D E I 4문제를 못 풀고 9솔로 마무리 했었다. 연습셋 후기는 귀찮아서 다음에 잘 봤을때 쓰겠다 ㅋㅋ. A. Circle Bounce 이 문제는 마음에 쏙 드는 문제였는데, 풀면서 얻어간 것이 좀 있었다. 우선 확률을 기약분수로 나타내는 문제에 대해서, modulo를 취하면 곱하기를 해도 일정하게 유지된다는 성질이 있는데,..

버츄얼을 했는데, educational 한 셋이어서 풀이를 올려본다. 뭣 같은 에듀코포보다 훨씬 좋다. https://atcoder.jp/contests/abc244 D. 문제 요약 ! RGB로 이루어진 순열 S와 T가 주어진다. S를 T로 만들건데, S의 임의의 원소 2개를 골라서 swap하는 작업을 정확히 1e18번 해서 바꿀 수 있는지 구해라. 잘 알려진 문제이다. S와 T의 inversion의 기우성에 따라 변하는데, segment tree등의 자료구조를 사용하면 O(nlogn)에 구할 수 있다. 근데 n이 3이다. 오버킬이다. 어떻게 할까? 이럴때는, 3C2가지 경우에 대해서 각각의 경우를 모두 따져주면 된다. 즉 S에서 R>G 였는데, T에서 RT로 가는 path 중에서 경로의 길이(사이의 간..

https://www.acmicpc.net/workbook/view/8646 많이 풀어주세요.

https://codeforces.com/contest/1516/problem/C 문제요약: 수열에서 합이 정확히 전체 합의 절반인 부분 집합이 존재하지 않도록 만들자. 원소를 하나씩 집합에서 제외하는 연산을 할 수 있다. 풀이: 일단 정확히 합이 절반인 것이 존재하는지를 dp로 판단하자. O(100*2000*100)정도에 알 수 있다. 그렇다면 정확히 절반인 것이 존재한다고 하자. (없으면 0출력후 종료) 전체합이 홀수라면 그런 partition이 불가능함은 자명하다. 따라서 홀수인 원소가 하나라도 있다면 그 원소를 하나 제거하기만 하면된다. 그게 아니라면, 즉 홀수인 원소가 없다면, 이제 중요한 것은, 모든 원소는 짝수가 되고 즉 모든 원소를 동시에 2로 나눈다. 2로 나눈 새로운 수열에서 parti..

문제 요약: 수열의 인접한 원소의 차이가 k이하이면 swap할 수 있다. 위 연산을 마음껏 사용했을 때 얻을 수 있는 lexicoographically smallest 수열은? 뇌절해서 풀긴했는데, 풀어서 기부니가 좋았다. 일단 기본 아이디어는 빨리 나왔는데, 이걸 어렵게 구현해버린거 같다. 나중에 정해도 공부할 생각. 우선 사전순으로 빨른 걸 구하라고 했을 때 아이디어는, 가장 빠른걸 고른다는 그리디를 생각해 볼 수 있다. 즉 우리는 현재 상태에서 맨 왼쪽으로 옮길 수 있는 가장 작은 value를 뽑아와야 된다는 생각을 할 수 있다. 그런데 어떤 ai가 있을때 jk라면, ai는 가장 왼쪽 원소가 될 수 없다.(자명하게도) 그리고 모든 j

공식 해설을 봤는데, 나처럼 푼 사람이 없는거 같아서 올려본다. 보통 아름다운 풀이는 간선을 뒤집는다는 아이디어 이다. 이제 무지성 풀이는 scc/위상정렬을 잘 쓰는 풀이가 있다. 나는 쉬운 무지성 풀이로 풀었는데, 그냥 실제로 그래프에서 사이클 찾아주면 된다. #include //#define double long double //T.erase(unique(T.begin(),T.end()),T.end()); //written by djs100201 #define all(v) v.begin(),v.end() using namespace std; using ll = long long; using P = pair; using PP = pair; const ll n_ = 1e6 + 100, inf = 1e18..

문제요약. 300*300 grid에서 거리의 정의를 manhatan distance로 했을때 정삼각형의 개수를 구하여라. 우선 유클리드 좌표게에서 정수 좌표 3개의 꼭짓점을 가지는 정삼각형은 존재하지 않는다. tan 60이 무리수이기 때문. 따라서 이 문제에서는 맨해튼 거리로 변형되었는데, 접근 방식은 다음과 같다. 일단 점 2개가 일직선인 경우는 예외처리 했다. 이는 간단한 sweeping으로 예외 처리 할 수 있다. 이제 3점의 x와 y좌표는 전부 distinct하다고 가정하자. 우리는 이제 이런걸 생각해보자. 어떤 점 3개를 뽑았을때 이 3개의 점이 정삼각형이 되는지를 어떻게 판정할 지를 생각해보면 되자. 우선 이 3점을 x좌표로 정렬하자. 그렇다면, x좌표로 정렬하고 봤을때, y좌표의 대소관계에 ..