Codeforces Round 700(Div.2) A~D1 A. Yet Another String Game Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityCodeforces 영어 소문자로 이루어진 한 문자열을 가지고 둘이 번갈아가면서 문자열의 한 글자씩을 바꾼다. 한 명은 문자열이 사전순으로 최대한 앞쪽으로 오게 만들려고 하고 한 명은 문자열이 사전순으로 최대한 뒤쪽으로 가게 만들려고 한다. 그러면 한 명은 자기가
코드포스 Codeforces Round #554(Div.2) A~D 정말 오랜만에 풀이를 올린다. 성실하게 써야 하는데.. A. Neko Finds Grapes Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityCodeforces n개의 숫자들로 이루어진 배열 a와 m개의 숫자들로 이루어진 배열 b가 주어진다. 이때 배열 a의 숫자와 b의 숫자를 하나씩 매칭해서 더한 것이 홀수가 되는 쌍이 최대한 많도록 매칭하는 문제다.
Codeforces Round #694 (Div.2) A~D A. Strange Partition Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityCodeforces 문제의 조건을 잘 읽어 보면, 모든 원소를 합친 후에 beauty를 계산하는 것이 최소한의 beauty이고 각각 원소에 대해 beauty를 계산한 후 모두 합해주는 것이 최대한의 beauty임을 쉽게 알 수 있다. #include #include #include #include #include #include #include
Codeforces Round #693 (Div. 3) A~E 또 떡락했다. 아직 실력이 너무나도 부족하다. 뭔가 마음만 급해지는 듯한 느낌이...꾸준하게 하다 보면 언젠가는 실력이 오를 거라고 생각하지만 이제 나이가 너무 들어 버려서 시간이... A. Cards for Friends Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityCodeforces 종이를 반으로 자를 수 있을 때(즉 w나 h중 하나가
Codeforces Round #687 (Div.2) A~E 어제 돌았던 버추얼을 이제 풀이를 쓴다. 이때 현장에서 치렀어야 했다는 생각이 강하게 든다. 아무튼 원래 내가 잘 풀었으면 좋은 셋이고 내가 말리면 구데기셋이라는 알고리즘 판의 합리화 법칙에 따라 이건 좋은 셋이었다. A. Prison Break Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityCodeforces n행 m열 사이즈의 격자로 된
Codeforces Round #551 (Div.2) A~D 매주 코드포스 버추얼을 도는 스터디를 하는데, 최근 라운드들은 다른 스터디원들이 이미 풀어본 라운드가 많아서 오래전 라운드부터 진행하고 있다. 재작년 라운드까지 거슬러올라가서 진행했고 그 풀이를 여기 적는다. A. Serval and Bus Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityCodeforces 비가 오는데 Serval은 버스를 타야 한다고 한다. 그래서 Serval이
Educational Codeforces Round #101(Div.2) A~D 버추얼을 돌았는데, 점점 머리가 안 좋아지는 것 같은 묘한 느낌을 받는다. 실력이란 게 쉽게 늘어나는 것은 아니라지만 늘어나기는 커녕 줄어드는 것 같은 느낌은 착각이라고 믿고 싶다. 버추얼을 까고 나서 업솔빙하면서 라운드에 대한 평가를 보니까 쉬운 라운드였다고 해서 자괴감이 들었다. 단 A번에서 헤맨 사람이 나뿐은 아니라는 사실이 좀 위안이 되었다. A.
Educational Codeforces Round 100(Div. 2) A~D A. Dungeon Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityCodeforces 3마리의 몬스터가 나타났다. 우리는 3마리 중 1마리의 몬스터에게 한 번 공격하여 1의 데미지를 가할 수 있고 이 공격을 이용해 모든 몬스터를 물리쳐야 한다. 다만 7의 배수 번째 공격을 할 때는 3마리 모두에게 공격이 들어간다. (이를 enhanced shot이라
Codeforces Round #692 (Div. 2) A~D 오늘도 코드포스 버추얼을 치고 풀이를 쓴다. D번 하나 하루종일 업솔빙하다가 결국 Lawali님의 코드 그리고 Gravekper님의 풀이 영상을 보고 이해할 수 있었다. A. In-Game Chat 그냥 문자열 끝에 있는 닫는 괄호의 개수를 세주고, 나머지 문자의 수와 비교해 주면 되는 문제다. #include #include #include #include #include #include #include #include #include typedef long
Codeforces Round #691 Div.2 A~C A. Red-Blue Shuffle Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityCodeforces 카드의 위에 있는 숫자들의 배열, 아래 있는 숫자들의 배열이 각각 주어진다. 이때 각 인덱스마다 위에 있는 숫자와 아래 있는 숫자들을 비교한다. 그리고 어느 쪽이 더 큰지에 따라 위/아래에 점수 같은 걸 매긴다. 그 점수를 비교해서
Codeforces Round #688 A~D 간만에 생각이 들어서 앞으로는 주기적으로 코드포스 셋 하나씩을 풀고 풀이를 쓰려고 한다. 이번에 푼 셋은 우리나라 ps계의 초대형 네임드 중 하나인 djm03178님의 셋이다. 나는 실제 대회에서 한문제밖에 못풀었기에 그다지 좋지는 않았다..ㅋㅋ A. Cancel the Trains Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityCodeforces 100x100 격자로 된
백준 BOJ 18189 참 어려운 문제 https://www.acmicpc.net/problem/18189 문제 설명 i번 정점의 색이 A[i]인 크기가 N인 트리가 주어질 때, 색깔이 같은 두 정점을 고르면, 이 둘은 항상 조상-자식 관계가 아니다 의 조건을 만족하는 루트가 될 수 있는 정점을 모두 찾아라. 풀이 r을 루트로 하는 트리에서 모든 정점 v에 대해 색이
bird function의 해 구하기 오랜만에 스터디를 하다가 스터디 과제 하나를 들고 왔다. 다른 과제나 진도 따라갈 수업도 산더미인데 언제하지 ㅅㅂ. 하여튼 과제는 일단 간단하다. bird function f(x,y) 에 대해 f(x,y)=0을 만족하는 해의 쌍(-2pi<=x<=2pi, -2pi<=y<=2pi)을 구하는 것. bird function은 무슨 최적화에 쓰이는 듣보잡 함수라고
함수형 하스켈, 왜 이렇게 어려운거야? 솔직하게 인정합시다. 하스켈은 어렵습니다. 어떤 사람들은 배우면서 포기하고, 어떤 사람들은 걸음마를 떼고 나서도 몇 걸음 걸어보기도 전에 그만둡니다. 하스켈에 대해 들어보기라도 한 사람들은 아주 많습니다. 그러나 하스켈을 배우기 시작해서 뭔가 쓸모 있는 프로그램을 만들어 보는데까지 도달하는 사람들은 아주 적습니다. 무엇이 하스켈을 그렇게 어렵게 만드는지 궁금해서 직접 배워봤습니다. 저는 아직 막
백준 BOJ 16074 Mountaineers 출처 : https://www.acmicpc.net/problem/16074 각 cell에 1, 2, 3, 4, ,,, (h * w)번호를 매긴 후 이 새로 인덱싱한 번호는 노드 번호로 취급 이후 각 인접한 노드(상, 하, 좌, 우)와 연결(엣지)을 하는게 두 노드 간의 cost는 누 도느 중 max값이 두 노드 사이의 cost가
Persistent LiChao Tree와 Offline LiChao Tree (부제: Dynamic LiChao Tree) 오랜만에 글을 쓴다. ploffer11이다. 탈알고 한다면서 씹덕 알고 하고 있으니 얘가 다시 알창이 됬나 오해할 수 있는데, 오히려 취미로 게임하듯 하니까 난이도 있는 알고리즘만 하게 되서 그렇다. 아무튼 퍼시스턴트 리차오 트리와 오프라인 리차오 트리가 뭐냐? 일단 리차오 트리 모르는 사람은 그것부터 배우고 읽길 Offline LiChao Tree 오프라인 리차오 트리는 다음과
백준 BOJ 13208 승현이와 승현이 출처 : https://www.acmicpc.net/problem/13208 문제에서 그래프가 주어진다. 이걸 또 다른 그래프로 바꿔야 한다. 주어진 그래프에서는 노드가 1, 2, 3, ,,, N까지 있다. 여기서 새로 만들어야 될 그래프는 N^2개의 노드를 가진다. (1, 1), (1, 2), (1, 3) ,,, (1, N), (2, 1), (2, 2),,,(2, N),,,(N, N) 이것을
코드포스 Codeforces Round #620 (Div. 2) E. 1-Trees and Queries 출처 : https://codeforces.com/contest/1304/problem/E LCA를 이용하면 댄다... 풀이는 int query(int nu, int nv, int u, int v, int len) 함수에 주석으로 적어놓았다.... 아래는 전체 코드 #include #define endl "\n" using namespace std; using ll = long long; struct TREE { int vn; vector>elist; vectors, p,
코드포스 Codeforces Round #294 (Div. 2) E. A and B and Lecture Rooms 풀이는 아래 그림으로 **대.체.한.다** 출처 : https://codeforces.com/contest/519/problem/E 아래는 소스코드 #include #define endl "\n" using namespace std; using ll = long long; struct TREE { int vn, sidx; vector>elist, p; vectorsize, depth; TREE(int a) : vn(a), sidx(1) { size.resize(vn + 1,
백준 BOJ 16213 dgeu-learning 출처 : https://www.acmicpc.net/problem/16213 요즘 HLD풀고 있는데 구현량이 꽤 있는 문제를 봐서 여기다가 올린다. (C한정) 참고로 난 구현량이 많으면 좋...다.... 힣... 오랜만에 정렬을 구현해 보고 싶다면 이 문제를 추천한다. 풀이 : MAXIMUM spanning tree를 만든다. 만들어진 트리를 가지고 heavy-light decomposition을 돌린다. min segment tree를 만든다. 엣지사이의 값을가지고
백준 BOJ 13016 내 왼손에는 흑염룡이 잠들어 있다 출처 : https://www.acmicpc.net/problem/13016 반갑읍니다. 누가봐도 tree dp인데 나는 아직도 tree dp를 풀어본적이 없어서 LCA로 비벼봄. 설명은 PPT로 대.체.한.다 는 여기 파일 업로드가 안대서 각 슬라이드 사진으로 첨.부.한.다 아래는 코드 #include #include struct e { int num, cost; }; struct node { int num;
백준 BOJ 10775 공항 출처 : https://www.acmicpc.net/problem/10775 한 6개월전 union-find 분류 훑다가 문제 이해가 안대서 넘겼는데 오늘 다시 보니깐 union-find풀이방법은 생각 안나고 이상하게 segment tree풀이가 생각났다. 간단한 설명 : i번째 비행기가 k번쨰 게이트에 도킹하고 싶다. 지금 k번째 게이트가 비어 있다면 도킹하면 된다. 그러나 k번쨰 게이트가 이미 도킹된 상태라면 1 ~ k -
백준 BOJ 1517 버블 소트 출처 : https://www.acmicpc.net/problem/1517 inversion counting 나는 merge sort tree 모른다. 아래 풀이는 segment tree 사용 #include #include struct info { int idx; long long val; }; long long answer, * tree; struct info *list, *sorted; void msort(struct info *, int, int); void merge(struct info *, int, int, int); int
BOJ 2671 잠수함 식별 ㅎㅇ! 오랜만에 돌아왔다. 오늘의 문제는 KOI 1996의 중등 2번이자 고등 1번인, 잠수함 식별이다. 풀이법은 양심에 찔리지만 간단한 풀이와 정직하지만 귀찮은 풀이로 총 두 가지 풀이를 소개하고자 한다. 두 풀이의 차이점은 단순히 구현 방식의 차이일 뿐, 기본적 원리의 차이는 없다. 우선, 문자열의 길이가 길지 않아서 백트래킹으로 AC를 받아낼 수 있을지는 모르겠다.
