본문 바로가기

반응형

div2

[Codeforces] Round #709 (div. 2) A ~ D 풀이 2021.03.21 22:20 ~ 00:35 본 라운드 참여 (performance = 1844) 테크노컵은 뭔가 항상 어려운 느낌이다... 생각보다 퍼포먼스가 나쁘지 않게는 나왔는데, 개인적으로 요즘 코포 폼이 조금 올라왔다고 생각해서 더 아쉬운 기분이 든다. A. Prison Break (*800) 모든 칸들에서 밖으로 나갈 수 있기 위해서 제거해야 하는 벽의 수의 최소를 구하는 문제이다. 답은 가로 * 세로, 즉 칸의 개수이고 대회중에는 직관적으로 빠르게 해결했다. 정확한지는 모르겠으나 증명을 하자면, 각 칸마다 해당 칸에서 시작해서 밖으로 나갈 수 있는지 없는지를 상태로 표현하고, 벽이 제거된 이웃한 칸은 하나의 칸으로 합쳐진다고 생각하자. 벽을 하나 제거했을 때 밖으로 나갈 수 없었던 2개 이상..
[Codeforces] Round #694 (Div. 2) 풀이 2021. 01. 05 23:35 본 라운드 참가 실력이 정체되어있다. 예전엔 더 올라갈 수 있는데 운이 안 따라주는 느낌이었다면 지금은 느낌이 좀 다르다.... 재활이 꽤 오래 걸릴 것 같다. 1471A. Strange Partition 주어진 배열에서 인접한 두 원소를 대신해서 두 원소의 합으로 대체할 수 있다. 배열의 원소는 1개만큼 줄어든다. 이 연산을 원하는 만큼 한 후에, 배열의 각 원소를 x으로 나눈 값을 올림 하여 모두 더한 합의 최솟값과 최댓값을 구해야 한다. 최대인 경우는 연산을 한번도 하지 않은 원래의 배열에서 합을 구해주는 경우이고, 최소인 경우는 연산을 n-1번 적용한, 즉 배열의 원소가 1개만 남았을 때이다. [소스 코드] #include using namespace std; u..