ABC216G - 01Sequence 의 에디토리얼 을 보는데, 문제를 소 게임(牛ゲー) 형태로 변형해서 풀면 된다고 나와있다. 처음 보는 유형이라서 검색해보니까 특이한 유형이라서 정리해본다. BOJ 7040 - 밥 먹기 BOJ 링크 소 게임은 위 문제에서 나온 풀이를 일본에서 부르는 말인 것 같다. 개미책(蟻本) 으로 알려진 풀이같다. (번역본이 있는데, 속칭 노란책 이라 부른다.) 어떤 주어진...
최근에 재미있는 풀이를 발견해서 정리해본다. 이 풀이는 결과값(정답)을 구해야 하는데, 결과값을 구하기 위해 계산하는 과정에서 결과값이 필요한 경우를 말한다. 말이 이해가 안 갈수가 있는데, 밑에 문제를 보면 어떠한 유형인지 알 수 있을 것이다. 푸는 방법을 간단히 요약하자면, 결과값을 parametric search를 이용해 임의로 정하고, 계산해서 나온 결과값...
최근에 경로에서 최소/최대 간선을 최대/최소화 하는 알고리즘을 배웠는데, 개념이 재미있어서 정리해본다. 최소 간선을 최대화 BOJ 1939 - 중량제한 위 문제를 요약하면 경로에서 최소 간선을 최대화하는 문제이다. 기본적인 개념은 MST를 크루스칼 알고리즘 을 이용해서 구할 때 만들어지는 유니온 파인드 트리를 이용하는 것이다. 최소 간선을 최대화 할때는 Maximum...
Educational Codeforces Round 106 (Rated for Div. 2) 에 참가했다. 2일 연속으로 하는거라서 할까말까 고민하다가 했는데 결과가 좋지 않다. 걍 쉴껄… 전체 Code A. Domino on Windowsill 그림으로 표현하면 이런 모양이 된다. 이러면 주황색 영역 왼쪽에는 하얀 도미노를 min(k1, k2)개 놓을 수 있고, 오른쪽에는 검은 도미노를 n - max(k1, k2)를 놓을 수 있다. 그리고 주황색 영역에서는 하얀/검은 도미...
Codeforces Round #708 (Div. 2) 에 참가했다. 도중에 사이트가 마비되는 이슈가 있었다. m1버전으로 풀고있었는데 결국 unrated되었다. 중간에 조금 헤매서 잘 못봤는데 다행이다. (망할 정수론) 전체 Code A. Meximization 일단 정렬을 해서 바로 순서대로 출력하면 틀리게 된다. 왜냐하면 중복되는 숫자가 있는 경우 해당 부분에 mex값이 변하지 않기 때문이다. ex) 0 1 2 2 3 보다...
