PS 일지

너무 오래 쉰 것 같다.종강을 하고도 PS는 종종 했지만, 글 쓰는게 귀찮아서 방치하다가 4개월치나 밀려버렸다. 한 번에 쓰기에는 문제 수가 너무 많아서 4월부터 다시 시작하려 한다... 4/2BOJ 4384 - 공평하게 팀 나누기Gold 1더보기#knapsack #dp 모든 사람들의 몸무게 합은 $45\,000$ 이하이고, 사람의 수가 $100$명 이하이다.따라서, 사람이 한 명씩 추가될 때마다 (몸무게 합, 사람 수)로 가능한 경우를 knapsack dp로 갱신해주면 된다. BOJ 1043 - 거짓말Gold 4더보기#bfs 주어진 $M$개의 파티 정보로 양방향 그래프를 만들고, 진실을 아는 사람들을 시작점으로 한 뒤 bfs를 돌려주자.bfs 수행 중에 만나는 모든 사람들에게는 거짓말을 할 수 없다..

Round 917에서 내 실력에 허무함을 느끼고 한동안 PS를 하지 않았었다.그러다 블루 복귀를 위해 간절함을 가지고 다시 시작하게 되었다. A - Square (00:02)네 개의 점이 사각형을 이루는 것이 보장되므로 네 점에 대한 $x$, $y$좌표의 최소, 최댓값을 구해 놓으면 넓이를 구할 수 있다. B - Arranging Cats (00:08)두 수열에 대해 같은 인덱스끼리 xor을 해주고 다시 저장하면, 변화를 줘야 하는 박스들만 남는다.두 수열에서 남은 $1$의 수 중 최댓값 만큼의 작업으로 두 수열을 같게 만들 수 있다. C - Sending Messages (00:16)$m_i$에서 $m_{i+1}$로 갈 때, 폰을 껐다가 다시 키는 경우와 쭉 켜두는 경우 중 더 작은 값에..

이번 라운드가 역대 최저점 퍼포먼스를 찍은 라운드였다...A번을 풀고 B를 보는데 풀이가 바로 생각나는 게 없어서 나머지 문제들을 둘러봤다.E를 풀 수 있을 것 같아서 여기에 시간을 다 쏟아부었는데, 왜 틀리지 하다가 반례가 생각났고 고칠 수 없어서 그냥 포기해버렸다. A - Least Product (00:04)배열에 $0$이 있거나 음의 원소 개수가 홀수이면, 아무런 작업을 하지 않았을 때 전체 곱이 최소가 된다.그렇지 않으면, $0$이 아닌 원소들 중 아무 원소에 작업을 1회만 하면 전체 곱이 최소가 된다. B - Erase First or Second Letter??? C - Watering an Array??? D - Yet Another Inversions Problem??? E - Co..

Codeforces Round 915 (Div. 2) 에 참가했다.이번 라운드는 내 안일한 판단때문에 아쉬웠던 라운드였다.무지성 제출을 하면 안 된다는 걸 배워가는 좋은 기회라고 생각해야겠다. A - Constructive Problems (00:04)문제가 $n\times n$ 정사각형일 때를 생각해보면, 답은 $n$임을 쉽게 알 수 있다. $n\times m$ 격자에서, 우선 $\min(n, m)$ 크기의 정사각형을 모두 build할 수 있다.남은 직사각형의 크기가 $x \times y$ 라면, $\min(x, y)$ 크기의 정사각형을 또 모두 build할 수 있다.$\vdots$ 이 과정을 반복해서 정답을 구하면 $\max(n, m)$이 된다. B - Beginner's Zelda (00:..

https://www.acmicpc.net/problem/1176 1176번: 섞기첫 줄에는 학생의 수 N(1 ≤ N ≤ 16)과 최소 넘어야할 키의 차이 값 K(1 ≤ K ≤ 3,400)가 주어진다. 다음 N개의 줄에는 학생들의 키가 순서대로 들어온다. 키는 25,000 이하인 자연수만 들어온다.www.acmicpc.net 문제 요약학생 $N$명이 줄을 서야 한다. 각 학생은 자신과 이웃한 모든 학생과 키의 차이가 $K$보다 크도록 줄을 서야 할 때, 줄을 서는 경우의 수를 구하는 문제이다. 문제 해결$N$의 제한 $1 \le N \le 16$에 주목하자. bitmask dp가 딱 떠오르는 제한이다.다음과 같이 식을 세워보자.$dp[i][j] = $지금까지 줄을 선 학생들의 집합이 이진수 $j$로 표현..

https://www.acmicpc.net/problem/24502 24502번: blobsad채완이와 주환이가 이 일을 마칠 수 있는 최소 시간을 초 단위로 출력한다. 만약, 마칠 수 없다면 blobsad를 출력한다.www.acmicpc.net문제 요약길이 $N$인 수열 $A$와 양의 정수 $K$가 주어진다.이 수열에 작업을 할 수 있다.어떤 $i$에 대해, $A_i$를 1 줄이고 $A_{i-1}$ 혹은 $A_{i+1}$을 1 올린다.모든 $i$에 대해 $A_i$가 $K$의 배수가 되도록 만들 때, 작업 횟수의 최솟값을 구하는 문제이다. 문제 해결문제 $A_i$가 $K$의 배수인가를 결정짓는 요소는 $A_i \bmod{K}$이다. 따라서, 주어진 모든 $A_i$를 $A_i \bmod{K}$로 바꿔서 생..

https://www.acmicpc.net/problem/9015 9015번: 정사각형각 테스트 케이스마다 가장 큰 정사각형의 넓이를 한 줄에 하나씩 출력한다. 단, 정사각형이 없는 경우 0을 출력한다.www.acmicpc.net문제 요약평면 위에 $N$개의 점이 주어졌을 때, 가장 큰 정사각형의 넓이를 구하는 문제이다. 문제 해결어떠한 두 점 $P, Q$를 골랐을 때, 그 두 점을 이은 선분을 변으로 갖는 정사각형이 있는지 알 수 있을까? 그 두 점의 $x$좌표 변화량과 $y$좌표 변화량을 각각 $dx, dy$라고 하자.$P, Q$를 $(dx, -dy)$만큼 대칭이동한 점이 둘 다 존재한다면 정사각형이 된다.이렇게 만들어진 사각형은 모두 변의 길이가 같고, 네 각이 항상 직각이 되기 때문에 정사각형이다..

https://www.acmicpc.net/problem/14461 14461번: 소가 길을 건너간 이유 730에서 출발해서 가능한 한 빨리 도착하려면 10으로 간 뒤 풀을 먹고, 5로 간 뒤 풀을 먹고, 존의 집인 80으로 가야 한다. 길을 건너는 데 총 16초, 풀을 먹는데 총 15초가 걸린다.www.acmicpc.net문제 요약2차원 격자판이 주어지고, 각 칸에는 정수가 주어진다.칸에서 상하좌우로 이동할 수 있으며 한 번의 이동에는 $T$의 시간이 소모된다.이동을 3번 하고 나면, 풀을 먹어야 해서(?) 현재 칸에 쓰여있는 정수만큼의 시간이 더 걸린다.$(1,1)$에서 $(N,N)$으로 이동하는데 걸리는 최소 시간을 구하는 문제이다. 문제 해결state를 구성하는 요소는 크게 세 가지이다.1. 풀을..

https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼?프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐www.acmicpc.net문제 요약건물을 정점으로 본 방향그래프가 주어진다. 각 건물은 건설하거나 파괴될 수 있다. (중복 건설도 가능하다.)건물들 사이의 관계를 나타내는 방향 간선이 주어진다. 간선 $X \rightarrow Y$는 건물 $X$가 건설된 상태여야 건물 $Y$가 건설될 수 있다는 의미이다.$K$개의 작업이 주어지며, 각 작업은 건물 $a$를 건설하거나 파괴하는 것이다.이 $K$개..

https://www.acmicpc.net/problem/25685 25685번: 좋은 노드 집합 찾기Alice와 Bob은 트리를 이용한 놀이를 즐겨한다. n개의 노드를 가진 트리 가 있고 노드는 편의상 번호가 1부터 n까지 붙어있다고 하자. i번 노드의 부모 노드는 p[i] 라 하고, 루트 노드의 경우 p[i] = 0www.acmicpc.net문제 요약정점에 $1$부터 $N$까지 번호가 부여된 루트 있는 트리에서, "좋은 노드 집합"은 이 트리의 노드의 부분집합 $S$이면서 아래 조건을 모두 만족하는 집합으로 정의한다.어떤 노드 $x$가 $S$에 속해있다면 $x$와 연결된 노드들은 $S$에 속하지 않는다.어떤 노드 $x$가 $S$에 속하지 않았다면 $x$의 자식 노드들 중 최소 하나의 노드는 $S$에 ..