pseong

Problem - E - Codeforces codeforces.com 보자마자 트리디피 인 것은 알았지만 한 가지 착각한 것 때문에 시간이 너무 오래 걸렸다. dp[i] : i를 루트로 하는 서브트리 내에서 정답 이라고 했을 때 dp[i] 는 max(모든 자식 dp[j] 를 더한 값, max(dp[j]) + 1)이라고 생각했다. 여기서 간과한 사실은 이렇게 구현하면 max(dp[j]) + 1)에 포함된 노드들 중에 모든 자식 dp[k]를 더한 값이 존재할 수 있다는 것이다. max(dp[j]) + 1로 구한 값은 항상 그 자식들도 max(dp[k]) + 1로 구해져야 한다. 생각해 보면 max(dp[j]) + 1이라는 값은 트리의 깊이이다. 따라서 트리의 깊이와 모든 자식 dp[j] 를 더한 값은 분리..

Problem - D - Codeforces codeforces.com 세로 x 가로 y 인 사각형으로부터 잘려 나온 n개의 조각들이 있다고 가정하자. (1) n개의 조각들로 세로 x 가로 y 인 사각형을 만들 수 있는지 판단할 수 있다. (2) 첫 번째 조각은 세로가 x이거나 가로가 y인 사각형 이어야 한다. 세로가 x인 조각과 가로가 y인 조각은 동시에 존재할 수 없다. 세로가 x인 조각을 먼저 잘랐다고 가정하면 가로는 y보다 작아지므로 가로가 y인 조각을 영원히 사용할 수 없다. 가로가 y인 조각을 먼저 잘랐다고 가정하면 세로는 x보다 작아지므로 세로가 x인 조각을 영원히 사용할 수 없다. 따라서 동시에 존재할 수 없으므로 항상 다음에 사용할 조각의 가로 또는 세로의 길이는 유일하다. 만약 가로가 ..

Problem - E - Codeforces codeforces.com Solution. 간선의 가중치가 k인 간선의 개수를 dp[k] 라 하자. 간선의 가중치는 연결된 두 노드의 최대 공약수 이므로 최대 공약수가 k가 되려면 두 수는 k의 배수가 되어야 한다. 따라서 k의 배수 중에서 2개를 선택하는 경우의 수 n/kC2를 구해주면 dp[k]의 초기값을 설정할 수 있다. 하지만 k의 배수 중에서 2k의 배수중에서 2개를 선택한 경우의 수는 최대공약수가 2k이므로 제외해 주어야 하고 마찬가지로 3k, 4k... 쭉 제외해 주어야 한다. 따라서 n부터 1까지 반대로 dp[i]를 채워 주면 답을 구할 수 있다. k를 선택했을 때 최대 공약수가 k + 1 인 추가할 수 있는 간선의 개수는 dp[k + 1] 이..

Problem - E - Codeforces codeforces.com 먼저 x가 y를 이긴다라는 것을 x에서 y로 가는 간선이 존재한다고 하자. 그리고 어떤 그래프에서 다른 모든 노드로 갈 수 있는 노드를 후보라고 하자. Lemma 1. 토너먼트의 승자는 최소 한 명은 존재한다. (후보는 무조건 한 명 존재한다.) Proof. 먼저 n이 1 또는 2일 때를 생각해 보자. 1 또는 2일 때는 무조건 어떤 한 노드는 다른 모든 노드를 방문할 수 있다. 여기서 노드를 하나씩 추가해 보자. 지문에 나온 대로 완전 그래프여야 하기 때문에 노드 하나를 추가할 때마다 기존에 있던 모든 노드와 연결되어야 한다. 여기서 기존에 있던 노드 중에서 모든 노드를 방문할 수 있는 노드를 x라 하자. 새로 추가하는 노드를 y라..

A번은 문제를 처음에 잘못 읽어서 조금 헤멨다. L과 R이 자기 자신도 포함해서 불빛을 밝혀 주는 줄 알았는데 아니었다. 아무튼 문자열에 R 다음에 L이 나오면 0이고 RL 문자가 있으면 R의 위치고 그게 아니라면 -1이다. B번은 구성적 문제고 배열을 만드는 문제다. 짝수일 땐 -1 0 -1 0 반복해서 출력해 주면 되고 홀수일 땐 식 잘 세우면 답이 나온다. C번은 또 배열 문제인데 관찰이 생각보다 간단해서 순조롭게 풀었다. m번째 원소 포함 왼쪽 구간에서 어떻게 두 개로 자르던 m번이 포함된 조각이 음수가 되게 해야 한다. m번째 원소 다음부터 끝까지 구간에서는 구간을 어떻게 두 개로 자르던 m번째 다음 원소가 포함된 구간이 양수여야 한다. 이 사실을 알았으면 우선순위 큐를 써서 잘 구현하면 된다...

번은 코포에 자주 등장하는 배열 조작 문제였다. 그냥 가장 작은 것을 바꿔주면 된다는 생각에 우선순위 큐 풀이가 생각났고 그렇게 풀었더니 맞았다. 추 후 답지를 보니 좀 더 깔끔하게 푼 풀이가 있었지만 어차피 시간 복잡도는 똑같으니까 그냥 넘어가는 게 나을 것 같다. B번은 구성적 문제인데 주어진 수식을 만족하는 순열을 하나 찾아서 출력하는 문제였다. 정말 문제 그대로 주어진 수식대로 구성만 하면 되었다. C번은 5틀 하고 맞아서 250점이나 깎였다. 처음에는 굉장히 단순하게 생각해서 차이가 짝수인지 홀수인지만 판별해서 제출했는데 알고 보니 아니었다. 그래서 좀 더 생각해 보다가 공약수라는 것의 특징에 대해서 생각해 봤다. 공약수는 생각해 보면 두 수의 차이가 존재하고 두 수의 공약수는 항상 그 차이보다..

F - One Fourth AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 신발끈 공식을 사용하면 한 포인터가 움직일 때마다 계산이 가능하기 때문에 투 포인터로 둘 다 왼쪽부터 탐색하면 될꺼라고 생각했지만 구현에서 조금 문제가 있어서 틀리게 됐다. 중요 포인트는 2가지를 기억하면 된다. 1. 신발끈 공식을 사용하면 맨 마지막 곱셈은 다음 첫번째와의 곱로 넘어가게 되는데 무식하게 그대로 구현했다. 첫번째 점을 원점으로 맞춰주면 더해줄때 마지막 곱셈은 안해도 된다. 이렇게 되면 포인터가 움직일 때마다 크로스곱 한번만 하면 돼..

1582A - Luntik and Concerts a, b, c가 전부 1개 이상 존재하므로 최대 차이는 1이다. 따라서 차이는 0 또는 1이 될 수 있다. a + b*2 + c*3 이 짝수면 차이는 0이고 홀수면 차이는 1이다. 더보기 #include using namespace std; using ll=long long; using pii=pair; using pll=pair; #define F first #define S second int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; cin >> T; while(T--) { int a, b, c; cin >> a >> b >> c; int s=a+b*2+c*3; if(s&1)..