알고리즘/codeforces
Codeforces Round #737 (Div. 2) A부터 C까지 업솔빙
Codeforces Round #737 (Div. 2) A부터 C까지 업솔빙 사실 코드포스에서 A번 문제가 5분 넘을때 까지 안풀리면 그 대회는 참가하지 않는 것이 RATING에 이로울 정도로 A번 문제를 쉽게 풀 수 있는지 없는지가 중요하다. 이번 대회는 A번 문제를 생각보다 빠르게 풀어서 기분이 좋았다. 하지만 바로 B번부터 막혀서 기분이 안좋았지만 나머지 B, C번 문제가 좋아서 업솔빙을 한다. 이번 대회에서 배운 것은 경로 압축 방법과 value-index pair 배열의 활용 이항계수의 성질 복습 및 dp 제발 정렬하는 것도 생각해보자. A. Ezzat and Two Subsequences (*800) 접기/펼치기 문제 설명 배열 1개가 주어지고 이 배열을 두 subsequences $a$, $..
알고리즘/atcoder
AtCoder Beginner Contest 207-A부터 C까지 업솔빙
AtCoder Beginner Contest 207 A부터 C까지 업솔빙 C번 문제 이거는 모르면 그냥 당하는 문제라고 생각했다. 문제 제목도 많은 조건 분기라서 이렇게 많은 조건을 분기해야 하나? 라는 생각을 하면서 문제를 풀었는데 결국은 못풀고 보니까 애초에 이런 문제를 푸는 방법이 있었다. 진짜 PS는 고인물 판인거 같다. 두 구간이 교차하는 조건 쉽게 구하기 닫힌구간과 열린구간에 대한 처리 방법 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - Repression (*6) 접기/펼치기 문제 설명 책상에 카드 3개가 있고 각 카드에는 양수가 적혀져 있다. 각 카드에 적혀있는 정수는 $A, B, C$이다. 두 카드를 선택하고 두 카드를..
알고리즘/atcoder
AtCoder Beginner Contest 209 - A부터 D까지 업솔빙
AtCoder Beginner Contest 209 A부터 D까지 업솔빙 충격적이라고 느낀 문제 set, C번하고 D번을 모두 못풀어서 짜증이 났던 문제다 도대체 나는 천장을 얼마나 두들겨야 그 고지를 넘어갈 수 있을까? 심지어 C번문제는 거의 다 접근했는데 한가지 생각을 못해서 못풀었고, D번 문제는 접근방법 조차 생각을 못해서 배울 점이 개인적으로 많았다고 느끼는 문제다. bipartite graph(이분 그래프)의 정의 및 활용 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - Counting (*5) 접기/펼치기 문제 설명 $A$보다 작지않고 $B$보다 크지 않은 정수는 몇개일까? 문제 해설 일단 $A$부터 $B$까지 정수의 개수를..
알고리즘/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)$ 이 주어진..
