mojo's Blog

문제 링크 => Problem - B - Codeforces Problem - B - Codeforces codeforces.com 이 문제에서 뇌절을 한 이유를 적어보려고 한다. 1. cell 을 채우는 과정에서 r, c가 달라지는 경우를 고려하지 못함 => 먼저 r을 채우고 c를 채우는 과정에서 cell을 채울 경우와 채우지 못할 영역을 표시해야 한다. cell을 채울 경우 r에서 cell을 채우지 못할 영역을 표시한 곳을 채운다면 이경우는 r, c가 달라지는 경우이다. 따라서 바로 0을 출력하면 끝이다. cell을 채우지 못할 영역을 표시할 경우 r에서 cell을 채운 곳이라면 이 또한 r, c가 달라지는 경우이다. 따라서 바로 0을 출력하면 끝이다. 2. 모든 cell 을 채웠을 때 r, c에 영..

문제 링크 => Problem - C - Codeforces Problem - C - Codeforces codeforces.com sorting 을 이용한 binary search 문제이다. 문제에 대해 간략하게 설명하자면 다음과 같다. 영웅들 n명과 드래곤 1명이 주어지며 힘, 수비력은 다음과 같이 주어진다. 영웅 => 드래곤에 맞서 싸울 영웅 1명과 드래곤의 공격을 받아쳐낼 (n - 1)명의 영웅들이 존재한다. 이때, 영웅의 각각 가지고 있는 힘을 ai 라고 한다. (1 해당 영웅을 한명 보내고 나머지 영웅들을 드래곤의 공격을 받아쳐내야 한다. 드래곤의 공격(y)이 나머지 영웅들의 힘(total)보다 클 경우 (y - total)만큼 힘을 키우면 된다. 반면에 같거나 작을경우 힘을 키우지 않아도 된..

문제 링크 => Dashboard - Educational Codeforces Round 72 (Rated for Div. 2) - Codeforces Dashboard - Educational Codeforces Round 72 (Rated for Div. 2) - Codeforces codeforces.com 어제 밤에 ICPC 학회분들과 virtual 을 돌려서 푼 문제인데 뇌절을 계속해서 풀지 못한 문제이다. 이러한 용의 머리의 길이 x 가 주어질 때 n 개의 Query가 주어진다. Query 는 머리의 길이를 d 만큼 잘라낼 수 있는 d 값과 자른 후에 h 만큼 다시 생겨나는 h 값이 주어진다. 이 때 용의 머리를 완전하게 잘라낼 수 있는 경우 최소로 자른 횟수를 출력하고 그렇지 못한 경우 -1..

문제 링크 => Problem - B - Codeforces Problem - B - Codeforces codeforces.com 이 문제를 해결하려면 먼저 MEX의 성질을 알아야 한다. MEX([0, 1, 2, ..., x]) = x + 1 MEX([0, 2, 4, 6, 8]) = 1 MEX([1, 2, 3, ... , x]) = 0 이런식으로 리스트 안에 0부터 시작해서 1씩 증가하다가 비어있는 숫자에 대해서 해당 값이 MEX 값임을 알 수 있다. 문제는 MEX 값 a와 XOR 값 b가 주어졌을 때과 리스트 안의 모든 XOR값이 b를 만족하면서 리스트의 MEX 값이 a를 만족하도록 하는 리스트의 최소 길이를 구해야 한다. 이때 리스트 안에 숫자는 겹쳐도 상관없다. (이부분 때문에 많은 뻘짓을 했다)..

문제 링크 => https://codeforces.com/contest/1561/problem/C Problem - C - Codeforces codeforces.com Problem tags => binary search, greedy, sortings 임의의 동굴에 들어갈 때 맨 앞의 몬스터부터 차례대로 무찔러가면서 1씩 레벨을 업할 수 있다. 이때, 몬스터를 무찌르는 과정에서 Hero는 몬스터보다 적어도 레벨이 1 높아야 한다. (이부분이 핵심) 즉, 임의의 동굴에 몬스터가 다음과 같이 배치 되었다고 가정하자. Hero (?) ) 5 , 10 , 8 , 12 , 15 , 11 , 16 이때 Hero가 해당 동굴에서 최소 어느 레벨이 되어야 모든 몬스터를 무찌를 수 있는지를 차례대로 확인하도록 한다...

문제 링크 => Problem - C - Codeforces Problem - C - Codeforces codeforces.com problem tags => Constructive algorithms, math 길이가 n 인 문자열 s 가 주어질 때, l1, r1, l2, r2 에 대하여 [ l1, r1 ] 에 해당하는 부분 문자열을 t 이라 하고 [ l2, r2 ] 에 해당하는 부분 문자열을 w 라 할 때, f(t) = f(w) * k 를 만족하도록 하는 l1, r1, l2, r2 를 찾는 문제이다. 아이디어가 신박한데 문자열 s의 index = 0 부터 접근하여 0인 지점을 발견할 때, 해당 index 값이 n/2 이상인 경우와 미만인 경우를 나눠서 범위를 바로 구할 수 있다. 위 방법을 고려하여..