CP_contest_Review (27) 썸네일형 리스트형 codeforces R703 D2 0솔.... A. Shifting Stacks 구현 할 수 있을 것 같아서 그쪽으로 방향 잡았다가 전을 다 태웠습니다.😨(h가 무려 10억입니다...) 애초에 가장 작은 증가 수열을 크기라는 관찰은 문제 열리자마자 알아챘는데 여기서 prefix sum은 상상도 못했습니다. 그냥 i번 인덱스에서 그때의 누적합이 증가 수열의 최소 크기보다 작으면 false 이렇게 풀면 됩니다.😡 codeforces R702 D3 solved: 2 out of 7 A,B 삽질해서 2문제 푸는데 30분 걸렸습니다. C번은 전처리해서 배열로 만들기는 했는데 이후 접근법에 있어 투포인터를 사용하는 트롤링, 그대로 2솔하고 끝나버렸습니다.😭 투포인터가 N개 배열에서 가능한 두개를 모두 탐색하는게 아니라는 점을 계속 잊고 있는 것 같습니다. A. Dense Array 문제에서 친절하게 식을 줘서 그대로 구현하면 됩니다. $\frac{max\left ( a_{i}, a_{i+1} \right )}{min\left ( a_{i}, a_{i+1} \right )} > 2$ 인 경우 원소를 몇개 넣어야 하는지 카운팅해주면 해결 할 수 있습니다. 저는 이 부분을 구현하는데 시간을 소모했는데 어렵지는 않습니다 아래와 같이 쉽게 구현 할 수 있습니다... codeforces R701 D2 solved: 0 out of 6 바로 어제 밤을 새서 스킵하려다 그냥 쳤는데 무려 0솔입니다 😅 따라서 업솔한 문제는 그때 그때 추가하겠습니다🙃 A. Add and Divide 그냥 수학문제입니다. 저는 대회중에 식은 다 뽑았는데 구현을 못하고 끝났습니다. 각각의 연산에 대해 k번 n번 했다고 했을 때, WLOG, $b = k$ 그리고 $a = \left \lfloor \frac{a}{b^n} \right \rfloor$ 따라서 이때 $min\left ( n+k \right ), a a) { ans=min(ans, i+j); break; } } } AtCoder ABC 191 solved: 2 out of 6 2문제를 10분안에 해결해서 기대 했었는데 역시나 C번에서 전을 구워버렸습니다. 주어진 다각형이 convex할때는 고려했지만 concave할 수도 있다는 사실을 고려못했는데 많은 사람들이 비슷한 실수를 한 것 같습니다. A - Vanishing Pitch 주어진 위치에서 공이 보이지 않는지 확인해주면 됩니다. B - Remove It 처음부터 입력을 받을 때, X와 다르면 입력을 받고 같으면 입력을 받지 않는 식으로 문제를 해결 할 수 있고 이는 $O\left ( N \right )$입니다. C - Digital Graffiti 에디토리얼이 올라오는대로 풀이를 추가하겠습니다 Codeforces R699 D2 solved: 1 out of 6 A번을 빠르게 해결하고 B번에서 전 굽다가 라운드가 끝났습니다. B번에서 중요한 관찰 2가지는 발견 했지만 문제를 해결 못했습니다. 개인적으로 너무 아쉬운 부분입니다. A. Space Navigation 단순한 구현문제로 문제에서 제시한 그대로를 구현하면 됩니다. B. New Colony 결국 돌이 최대 $\left (n-1 \right )\times \left ( max-1 \right )$개이며 이보다 크면 무조건 -1이라는 사실을 알 수 있습니다. 이때 max는 최대 100이고 n도 최대 100임으로, -1이 아닌 돌은 총 1만개까지라 구현으로 문제를 해결 할 수 있습니다. 왼쪽 산부터 돌을 굴려주면서 마지막 위치를 갱신해주고 만약 돌이 끝까지 굴러간다면 -1을 출.. AtCoder ABC 190 solved: 3 out of 6 C번까지 푸는데 30분이 안걸렸는데, D번 수학에서 막혔습니다. A - Very Very Primitive Game 둘이 같은 수의 캔디를 들고 있는 상황을 고려하면 쉽게 해결 할 수 있습니다. if (c==0) { if (a>b) cout codeforces R698 D2 solved: 2 out of 6 A,B 두 문제를 40분이 안되는 시간안에 삽질 없이 해결하여(WA없이) 오늘 드디어 색을 바꾸는구나 했는데 C,D가 수학이라 좌절한 라운드입니다. C번은 오늘 자고 일어나서 다시 에디토리얼을 읽는데도 도통 이해가 가지 않아 우선 풀이를 보류합니다. A. Nezzar and Colorful Balls N이 정말 너무너무 작아서 $O\left ( N^2 \right )$풀이로 AC를 받았습니다. 길이 N짜리 배열을 돌면서 색을 그냥 칠해주면 됩니다. int n;read(n); int A[n]; rep(i, n) { int tmp;read(tmp); A[i]=tmp; } int painted[n]; fill(painted, painted+n, -1); int color = .. Codeforces R697 D3 solved 1 out of 7 서버 문제로인해 대회가 미뤄지기도하고 채점이 진행되지않아 B번까지 보다가 그냥 잤습니다. 너무 아쉽지만 A번을 특이하게 풀어서 기록을 남깁니다. A. Odd Divisor 주어진 정수 N이 홀수로 나눠지는지 확인하는 문제입니다. 다만 이때 N의 크기가 $10^{14}$임으로 $O\left ( N \right )$으로 찾아주면 안됩니다. N이 홀수면, N은 무조건 Odd Divisor를 갖는다는 점을 활용하여 문제를 해결할 수 있습니다. func(N) { if N=odd return true else if N=even func(n/2) } 이렇게 N을 절반씩 나눠주면 $O\left ( logN \right )$안에 문제를 풀 수 있습니다. bool chk(ll k) { if.. CF R696 D2 solved 2 out of 6 A. Puzzle From the Future 문제 태그에는 그리디라고 되어있는데 문제를 풀면서 증명은 생각 못했고 그냥 구현문제처럼 풀었습니다. 문자열 a의 첫 글자는 무조건 1로 시작하고, 그 이후로는 현재 보고있는 인덱스를 i라고 할때 d[i-1]과 a[i]+b[i]의 값을 계속 다르게 해줘서 해결해주면 됩니다. rep(i, b.length()) { int k = b[i]-'0'; if (i==0) a+='1'; else { int tmp = (a[i-1]-'0')+(b[i-1]-'0'); // d[i-1] if (tmp!=k+1) a+='1'; else a+='0'; } } B. Different Divisors 대회중에 계속 공지가 떠서 특이한 문제였다고 기억이 .. ABC 188 대회중에는 A,B번까지 풀었다 A,B 두 문제를 10분안에 해결해서 C번은 풀 줄 알았는데 도무지 풀이가 생각나질 않아서 못풀었다 A - Three-Point Shot 삼점 슛을 넣고 역전이 가능한지 묻는 문제이다 문제에 나온 그대로 구현하면 풀 수 있다 주어지는 두 팀 중 무조건 점수가 낮은팀을 A, 높은 팀을 B로 보는게 구현의 팁 B - Orthogonality 벡터의 곱을 하여 0이 되는지 묻는 문제이다 N이 10만이라 $O\left ( N^2 \right )$보다 빠르게 풀어야 하는데, 그냥 1부터 N까지 더해주면서 그 합이 0인지 아닌지 확인하면 풀린다 C - ABC Tournament 비트연산을 이용한 구현인줄 알았는데 전혀 아니었습니다 키 포인트는 어찌됐든 매치의 결과로 파이널리스트는 왼쪽.. 이전 1 2 3 다음