돌이 코딩하는 방

문제 링크 : www.acmicpc.net/problem/19935 문제 소개 k 판의 게임을 진행한다. 각각의 게임은 m개의 숫자카드중 일부가 있는 n개의 카드 세트에서 1개씩을 뽑는다. 주최측이 원하는대로 수를 선정하고, 그 수와 뽑은 n개의 수의 차이의 절댓값 만큼 점수를 얻는다. 이때 주최측은 얻는 점수가 최소화 되도록 수를 선정한다. 이때 k 판을 진행하면서 얻는 점수가 최대가 되도록 각 판에서 뽑을 숫자카드를 설정하고, 이때 얻을 점수를 구하여라. 문제 풀이(+의식의 흐름) part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리 이 문제를 시작한 이유. 1분 보고 나서 DP 느낌이 확 왔다. 뭔가 난이도의 대부분은 관찰이고, 구현은 그렇게 어렵지 않을 것 같다는 생각이 크..

문제 링크 : www.acmicpc.net/problem/19934 문제 소개 인접행렬이 주어진다. 이때 모든 값은 3이하이다. 이때 주어진 인접행렬을 만족하는 트리가 있는지 판단하고, 있다면 그 트리를 보여라. 문제 풀이(+의식의 흐름) part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리 경로의 가짓수로 가능한 것은 0,1,2,3 인데, 각각의 경우에 대해서 두 노드가 어떤 식으로 배치 되어 있을지에 대해서 생각을 해보았다. 0가지일때: 둘은 같은 컴포넌트에 존재하지 않는다. 또한 0 이 아닌 두 노드는 항상 같은 컴포넌트에 존재해야 한다. 따라서 우리는 경우의 수가 0이 아닌 모든 쌍에 대해서 union &find 를 이용하여 같은 컴포넌트로 묶을 수 있다. 이때 같은 컴포넌..

문제 링크 : www.acmicpc.net/problem/1167 문제 태그 더보기 DFS 문제 풀이 트리의 한 정점에서 가장 먼 정점을 잡는다. 그러면 그 정점을 트리의 지름의 한쪽 끝이 된다. 따라서 찾은 정점에서 시작하여 가장 먼 정점까지의 거리를 구하면 그 거리가 트리의 지름이 된다. - 임의의 한 점에서 가장 먼 점을 잡으면 그 점은 항상 트리의 지름의 한 쪽 끝이 되는가? 아니라고 해보자. 아래의 그림에서 초록이 주황, 노랑보다 길어야 하는데, 그럼 주황-노랑으로 이어진 길이 지름인 것에 모순이다. 따라서 위의 가설은 참이다. 따라서 풀이는 정당하고, 어떤 한 점에서 나머지 모든 점까지의 거리를 구하면 되는데, 이는 다익으로도 할 수 있지만, 트리에서는 dfs로 간단하게 해결할 수 있다. 코드..

Codeforces 다시 떡락한뒤에... div1에서는 올리지 못했다. #668 div1이 굉장히 아쉬웠다. /2 만 안했어도 D를 푸는 것이었기 때문에 진짜 쭉 떡상할 수 있었다. 하지만 실패했다. 2000 초반이었지만 한동안 div1을 볼 수가 없었다. only div2만 한가득. 최대한 존버를 하다가 비장의 한 번을 터트려서 쭉 올라가기로 마음먹었다. #669에서 그 컨트롤을 실패해서 그냥 망해버릴뻔 했다. 2110 박제가 될 뻔 했으나 환상적인 D 시스페일로 인해서 2050 쯤에 세워놓을 수 있었다. 그 후 #670에서 38등 떡상에 성공! 후기글은 여기서 볼 수 있다. 현재 레이팅은 2181. 한국 60등, 세계 1700등대, 교내 5등을 기록했다. BOJ 1000문제 달성!!!! 요즘 정말 꾸..

문제 링크 : www.acmicpc.net/problem/5916 문제 태그 더보기 HLD ,segment tree lazy propagation 문제 풀이 문제를 보자... 1번 트리다. 2번 쿼리가 주어진다. 3번 그 쿼리가 경로 쿼리이다.... 아무리 봐도 이 문제는 HLD를 사용하는 문제라고 밖에는 생각이 들지 않는다. 경로에 모두 하나씩 심기 때문에 segment tree part에서 lazy propagation을 같이 섞어주면 문제를 해결할 수 있을 것 처럼 보인다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 4..

이번에는 38등을 했다. 한동안 only div2 밖에 없어서 2099에 최대한 근접시키고 한번에 쭉 올라가려고 했는데, 뭔가 이번이 기회인것 같아서 그냥 쭉 올려버렸다. 사실 좀 더 잘했을 수 있었을 것 같은데 비장의 한 방 치고는 조금 아쉬웠던 것 같기도 하다. 사실 한번 2등을 했어서 이제는 성에 안차는 것 같기도... A . Subset Mex 두 개의 그룹으로 나누고 두 그룹에 대한 각각의 Mex 값의 합을 최대화 시켜야 한다. 0부터 보면서 2번 이상 나왔으면 양쪽 모두에 넣을 수 있으며, 1번만 나왔으면, 한쪽 그룹에는 넣을 수 없고, 한 번도 나오지 않으면 양쪽 모두 넣을 수 없다. 따라서 우리가 구하고자 하는 값은 1번 이하로 등장한 가장 작은 수 + 0번 이하로 등장한 가장 작은 수 이..

이번에 소개할 Segment Tree 심화는 HLD이다. 원래는 Euler Tour 이후에 바로 글을 작성했어야 하는데, 대회 준비등의 이유로 다른 내용 관련 글을 계속 쓰다 보니까 계속 미뤄져서 이제서야 글을 쓰게 되었다. 사전 지식 (먼저 읽고 와야하는 글) stonejjun.tistory.com/103 세그 먼트 트리 - euler tour tree 설명글 What is HLD? 그러면 본격적으로 HLD는 무엇일까? HLD는 일단 Heavy - Light Decomposition의 약자이다. 무거운거 - 가벼운거 분해. 즉 Decomposition인데 Heavy Groupr과 Light Group으로 분리한다는 것이다. 그러면 여기서 좀 세부적으로 알아야 할 사항이 생긴다. 1. 뭐를 분리하는 것인..

이 글을 쓰게 된 동기는 굉장히 재미있다. 증명을 원하시는 분이 있었고 누군가가 내 글을 링크해주신 것을 알게 되었지만 그 글에서는 증명이 없었고, 그래서 관심을 가지게 되었다. 어느 정도 생각해본 결과 대충 증명이 된 것 같아서 일단은 빠르게 글을 써보려고 한다. 따라서 증명이 완벽하지 않을 수도 있으며 뇌피셜일 수도, 많이 생략했을 수도 있다. 하지만 오히려 직관적으로 받아들여질 수도 있다. 댓글로 비판과 지적은 언제나 환영한다.이 글을 읽기 전에...로테이팅 캘리퍼스 설명글 stonejjun.tistory.com/42본인은 설명을 굉장히 못하기 때문에 어쩔 수 없이 설명하려면 코드와 함께 설명하는 수밖에 없을 것 같다. 위 글의 맨 마지막에 코드가 있고, 증명과정에서 그 코드를 언급을 하게 될 것 ..

solved 기준 문자열을 너무 안풀었고, 문자열 관련 기초 코딩능력이 딸리는 것 같아서 아래와 같이 검색한 랜덤 문제를 푸려고 한다. 계속 푸는 대로 업데이트 할 예정이다. BOJ 17413 단어 뒤집기 제발 문제 좀 읽자. 1. 전체 뒤집은면 되는 줄 알고 reverse가 끝인줄 알았다. 2. 단어별로 뒤집는 것 인줄 몰랐다. 3. 자잘한 코딩 실수들. 정신좀 차리자. 대회면 망했다. 그래도 줄 입력이 getline(cin,s); 인것은 기억해냈다. 풀이는 입력 종류별로 케이스를 나눠서 뒤집어야 하는 것들은 스택에 담아두면 끝. 닥히 어렵지 않다. 더보기 #include using namespace std; typedef long long int ll; string s; string s2; stack..

문제 링크 : https://www.acmicpc.net/problem/13310 문제 태그 더보기 삼분 탐색, 로테이팅 켈리퍼스, 볼록 껍질 문제 풀이 가장 멀리 떨어진 두 별의 거리가 최소인 날을 구해야 한다. 다시 생각하면 임의의 두 별에 대해서 거리를 구한 후, 그 중 최댓값이 그 날에 대한 수치가 되는 것이다. 문제에서는 각 날별로 두 별의 거리를 구하는 것이지만 일단 관점을 바꿔서 두 별의 거리를 각 날별로 관찰해보자. V자. 이런식으로 나올것이다. 즉, 일정 시점까지는 두 별이 계속 가까워 졌다가, 일정 시점 이후부터는 계속 멀어질 것이다. 혹은 시간 구간 내에서는 계속 감소하거나 계속 증가할 수도 있다. 두 별에 대한 모든 거리 그래프를 겹친 후에 그 중 최댓값을 뽑아낸 그래프 G'를 생각..