알고리즘/codeforces
Educational Codeforces Round 112-C. Coin Rows
문제 설명 앨리스와 밥은 $2 \times m$ 크기의 격자판에서 게임을 하고 있다. $i$번째 행과 $j$번째 열에 위치한 격자는 $a_{i, j}$개 코인이 위치해 있다. 처음에 앨리스와 밥은 격자 $(1, 1)$ 에 위치해 있다. 이들은 격자 $(2, m)$ 을 향해서 다음 동작을 수행한다. 가능한 움직임은 다음과 같다. 오른쪽으로 이동 $(x, y) -> (x, y + 1)$ 아래쪽으로 이동 $(x, y) -> (x + 1, y)$ 첫번째로 앨리스가 $(2, m)$ 을 향해서 움직인다. 앨리스는 방문한 모든 격자의 코인을 다 쓸어담는다. 단 처음과 끝도 포함. 두번째로 밥이 $(2, m)$ 을 향해서 움직인다. 이때 밥은 앨리스가 방문하지 않은 모든 격자의 코인을 다 쓸어 담는다. 즉 앨리스가 이..
알고리즘/codeforces
Educational Codeforces Round 112-B. Two Tables
문제 설명 축과 평행하고 너비가 $W$이고, 높이가 $H$인 직사각형 방이 있다. 따라서 왼쪽 아래에 꼭짓점은 $(0, 0$ 이고, 오른쪽 위에 꼭짓점은 $(W, H)$ 이다. 이 방안에는 직사각형 탁자가 놓여있다. 탁자의 옆면은 벽과 평행하며, 왼쪽 아래 꼭짓점은 $(x_1, y_1)$, 오른쪽 위에 꼭짓점은 $(x_2, y_2)$ 이다. 우리는 이 방안에 너비가 $w$이고, 높이가 $h$인 또 다른 탁자를 기존의 탁자와 평행하고, 벽과 평행하게 놓고 싶다. 여기서 주의해야할 점은 두 테이블이 겹치게 놓으면 안된다는 것이다. 어떤 탁자라도 움직일 수는 없지만 첫번째 탁자를 이동시킬 수는 있다. 두번째 탁자가 주어진 방에 놓일 수 있게 하기 위해서 첫번째 탁자가 움직여야할 최소 거리는 무엇인가? Inpu..
알고리즘/codeforces
Educational Codeforces Round 112-A. PizzaForces
문제 설명 Pizzaforces는 페니가 가장 좋아하는 피자가게이다. 이 가게에는 3종류의 피자를 만들고 판매한다. S 사이즈는 6조각, M사이즈는 8조각, L사이즈는 10조각으로 이루어져 있다. 각각 피자를 만드는데 15분, 20분, 25분이 걸린다. 페니의 생일은 바로 오늘이고 친구 $n$명이 오기로 되어있다. 그래서 페나가 가장 좋아하는 피자집인 Pizzaforces에서 피자를 주문하려 한다. 페니는 모든 친구들이 최소 피자 1조각을 먹게 주문하고 싶다. 총 주문 시간은 모든 피자를 요리하는데 필요한 총 시간이다. 우리는 최소 $n$조각의 피자를 만들기 위해서 필요한 최소 시간을 구해야 한다. Input 첫번째 줄에는 테스트 케이스를 의미하는 정수 $t (1 \le t \le 10^4)$ 이 주어진..
알고리즘/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$번째 행에 자신의 폰이 최대 몇개나 위치할 수 있는지 알고싶다. 오직 조지의 턴만 가지고 있으며, ..
