알고리즘/atcoder
AtCoder Beginner Contest 208 A부터 D까지 업솔빙
AtCoder Beginner Contest 208 A부터 D까지 업솔빙 계속 이렇게 대회가 나왔으면 좋겠다. D번문제가 생각보다 내가 알고있는 알고리즘을 그대로 사용해서 풀 수 있었다. 이제는 "어딘가 들어본 알고리즘"이 아닌 "언제든지 꺼내 쓸 수 있는 알고리즘"으로 만들어야 할 시기이다. 이번 대회를 참여하면서 배운 것은 Floyd-Warshall(플로이드-와샬) 알고리즘의 구현과 쓰임새 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - Rolling Dice (*28) 접기/펼치기 문제 설명 $1, 2, ..., 6$ 이 적혀있는 주사위를 $A$번 던질때 주사위 눈금수의 합이 $B$가 나올 수 있을까? 제약 $1 \le A \le ..
알고리즘/codeforces
Codeforces Round #736 (Div. 2)-C. Web of Lies
문제 설명 $n$명의 귀족이 있다. $1$부터 $n$까지 번호가 붙여져 있는 귀족 $i$는 $i$만큼 힘을 가지고 있다. 또한 $m$개의 친구관계를 가지고 있다. 귀족 $a$와 $b$사이에 있는 친밀도는 항상 서로 작용한다. 만약 한 귀족이 다음 두 조건을 모두 만족하면 그 귀족을 우리는 "취약하다" 고 한다. 귀족은 최소 1명 이상의 친구를 가져야한다. 모든 귀족의 친구는 그 귀족보다 높은 힘을 가져야한다. 우리는 다음 세종류의 질의에 따라 진행한다. 귀족 $u$와 $v$사이에 친구관계를 맺는다. 귀족 $u$와 $v$사이에 있는 친구관계를 지운다. 다음과정에 따라 답을 도출한다. The Process: 모든 취약한 귀족을 동시에 죽여버린다. 그리고 그 귀족과 관계되어 있는 친구관계 또한 끝난다. 그후 ..
알고리즘/codeforces
Codeforces Round #736 (Div. 2)-B. Gregor and the Pawn Game
문제 설명 $n \times n$ 크기의 체스판이 주어진다. 왼쪽부터 $i$번째 행과 $j$번째 열을 $(i, j)$ 라고 표기한다. 현재 조지는 $n$번째 행에 폰을 몇개 놓는다. 적 폰은 $1$번째 행에 위치해 있다. 각 턴마다 조지는 조지의 폰중 하나를 움직인다. 만약 맞은편에 폰이 존재하지 않는다면 폰은 위로 한칸 움직일 수 있다. $(i, j)$ 에서 $(i - 1, j)$ 추가적으로 위쪽 대각선에 상대 폰이 존재한다면 폰은 대각선으로 한칸 위로 움직일 수 있다. $(i, j)$ 에서 $(i - 1, j - 1) or (i - 1, j + 1)$ 그리고 그 위치에 있는 폰은 제거된다. 조지는 $1$번째 행에 자신의 폰이 최대 몇개나 위치할 수 있는지 알고싶다. 오직 조지의 턴만 가지고 있으며, ..
알고리즘/codeforces
Codeforces Round #736 (Div. 2)-A. Gregor and Cryptography
문제 설명 조지는 RSA 암호화 방식을 공부하고 있다. 비록 조지는 RSA가 어떻게 작동되는지 모르지만 소수에 관심을 가지고 있고 그에 대한 인수에 매료되었다. 조지가 가장 좋아하는 소수는 $P$ 이다. 조지는 다음 속성을 모두 만족하는 두 정수를 찾고 있다. $P\;mod\;a = P\;mod\;b$ $2 \le a < b \le P$ 조지가 좋아하는 소수와 관련된 두 수를 찾아주자. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 소수 $P(5 \le P \le 10^9)$ 이 주어진다. Output 각 줄마다 두 정수 $a, b (2 \le a < b \le P)$ 를 출력한다. 만약 답이 여러개 ..
알고리즘/codeforces
Codeforces Round #734 (Div. 3)-C. Interesting Story
문제 설명 커리는 소설을 쓰고 싶다. 커리는 진짜 이상한 작가인데 오직 문자 'a', 'b', 'c', 'd', 'e'만 사용한다. 이야기를 구성하기 위해서 커리는 주어진 소문자만으로 이루어진 단어 $n$개를 작성했다. 커리는 재밌는 이야기를 만들기 위해서 선택해야 하는 최대 단어수를 구해야 한다. 단어를 선택하는 순서는 중요하지 않다. 이야기를 구성하는 모든 단어에 있는 5개의 문자중 한 문자의 개수가 다른 4개의 모든 문자의 개수 총합보다 큰 경우가 있으면 이 이야기는 흥미로운 이야기라고 한다. 예를 들어 이야기가 3단어 "bac", "aaada", "e"로 이루어져 있다면 이 이야기는 흥미로운 이야기이다. 왜냐하면 단어 '..
알고리즘/codeforces
Codeforces Round #734 (Div. 3)-B2. Wonderful Coloring - 2
문제 설명 폴은 정수 $a_1, a_2, ..., a_n$ 으로 이루어진 수열을 생각했다. 폴은 이 정수들을 $k$개 색깔의 분필로 칠하고 싶다. 다음의 조건을 만족하면서 색칠을 하면 환상적인 수열이라고 말한다. 수열의 각 원소는 $k$개의 색깔중 하나만 색칠하거나 색칠하지 않아야 한다. 같은 색깔로 색칠한 모든 두 원소는 서로 다른 값을 가져야한다. 각 $k$번째 색깔로 칠한 원소의 개수는 모두 같아야 한다. 위에서 언급한 3개의 조건을 만족하면서 색칠한 원소의 개수가 최대가 되어야 한다. 예를 들어 수열 $a = [3, 1, 1, 1, 10, 3, 10, 10, 2]$ 이고 $k = 3$ 인 경우 수열의 환상적인 색칠의 한가지 경우는 다음과 같다. 폴이 주어진 수열 $a$를 환상적인 색칠을 할 수 있..
