leo020630의 블로그

앳코더는 레이팅이 잘 오르는 것 같다. 아직 낮아서 그런가? A. Four Prints (0:01, +) *28 직사각형의 세 꼭짓점이 주어졌을 때 남은 하나의 점을 구하면 된다. 적당히 if문을 써주면 구현할 수 있다. A번치고 오래 걸렸다. B. Get Closer (0:03, +) *79 구하라는 것을 계산하면 된다. 문제에서 제한을 상당히 편하게 주어 대충 짜도 된다. C. Coupon (0:07, +) *336 \(A_{i}/X\)의 합과 \(K\)를 잘 비교해 처리해주면 된다. D. 2-variable Function (0:30, +3) *1148 \(A\)를 고정한 후 \(B\)는 이분 탐색으로 찾아주면 된다. 최대 \(10^6\)까지 돌리면 되니 오버플로우는 고려할 필요가 없으며, 예외처리..

대회중 과정과는 상관 없이, 에듀만 치면 결과가 귀신같이 좋다. A. Integer Moves (00:01, +) 주어진 점이 원점이면 0, 원점과의 거리가 정수면 1, 아니면 2이다. B. XY Sequence (00:03, +) 그리디하게 해주면 된다. C. Bracket Sequence Deletion (00:18, +) 괄호 문자열에서 팰린드롬을 생각해본건 처음이라 뇌절이 와 지문을 좀 느리게 읽었다. 만약 앞 두 글자가 ((이나 ))인 경우 팰린드롬이라 지울 수 있고, ()인 경우 올바른 괄호 문자열이라 지울 수 있다. 남은 경우는 )(인데, 이 경우 )(((..(()가 팰린드롬이므로 )가 다시 나올때까지 확인해주면 된다. D. For Gamers. By Gamers. (01:11, +7) 핵심..

코포랑 앳코더가 같이 있었는데, 코포가 테크노컵+앳코더 블루까지 레이팅이 얼마 남지 않았었기 때문에 앳코더를 쳤다. 결과적으로는 괜찮은 선택이었던 것 같다. A. Last Letter (0:00, +) *6 B. Go Straight and Turn Right (0:02, +) *30 생략 C. Yamanote Line Game (0:04, +) *165 앳코더에서는 처음 보는 인터랙티브였다. 하지만 인터랙티브인게 별 의미가 있는 수준은 아니었고, set등을 이용해 구현하면 쉽게 맞을 수 있다. D. Swap Hats (0:08, +) *165 D번 정도면 꽤 귀찮다는 인식이 있었는데, 너무 쉬워서 놀랐다. 두 배열의 inversion parity가 일정해야 하는데, n이 3이니 대충 if문으로 구현해주..

전날 있던 Div. 2에서 2095->1943이라는 기염을 (또) 토한 터라 멘탈이 좋지는 않았다. Div. 1에서 오른 적이 거의 없던 터라 좀 무섭기도 했고.. 그래도 레이팅이 엄청 낮아져 있었기 때문인지 어떻게 오르긴 한 것 같다. A. Weird Sum (00:38, +) Div. 1에서의 흥망을 가르는 요인은 A라고 생각한다. 그리고 나는 대부분의 Div. 1에서 A만 보면 뇌가 굳는다. 이번 역시 그랬다. 스코어보드는 10분만에 초록색이 쫘르륵 깔리는데 나는 감이 하나도 안 왔다. 30분을 넘게 생각한 후에야 정해도 아닌 \(O(NsqrtN)\) 시간복잡도의 풀이를 찾아서 해결할 수 있었다. 이때만 해도 엄청 망할줄 알았다. B. Integral Array (01:01, +1) 문제를 처음 봤..

오렌지를 처음 찍은 후부터 이 라운드 전까지 총 3개의 rated 라운드를 쳤다. 결과는 -81, -9, -115로 많이 좋지 않았다. 첫 라운드에서는 A에서 크게 말렸고, Div.2 C에 세그를 두개 박는 오버오버킬을 하고 나서야 해결할 수 있었지만 그 때는 이미 대회 시작 후 1시간이 지난 시간이었기 때문에 좋지 못한 결과로 대회를 마무리해야 했다.두번째 라운드는 비교적 평이하게 진행되었으나, C를 4번 틀리고도 해결하지 못한 점이 아쉬웠다. 화룡점정은 본 글에서 다루는 라운드 바로 하루 전에 진행된 컨테스트였다. Div.2 였음에도 불구하고 2솔로 대회를 마무리했다. 퍼포먼스는 무려 민트였으며, 그런 경험은 굉장히 오랜만일 뿐더러 C가 그렇게 어려운 문제도 아니었기 때문에 멘탈이 나간 주 원인이 되..

A. The Miracle and the Sleeper (00:02, +) \(r%max(l,r/2+1)\)이 답이다. B. Scenes From a Memory (00:12, +) 관찰을 통해 자리수를 무조건 2이하로 만들 수 있다는 것을 알 수 있다. 이를 토대로 나이브하게 구현하면 된다. C. Rings (00:43, +1) 다음과 같은 관찰이 필요하다 : 어떤 이진수의 앞이나 뒤에 0을 붙여도 주어진 조건을 만족한다. 따라서, 주어진 문자열에 0이 하나라도 포함되어 있으면 더 긴 쪽으로 연결시켜 주면 된다. 전부 1인 경우엔 \([1,n-1]\)과 \([2,n]\)을 호출하는 방법과, \(n\)이 짝수인 경우에 길이가 \(n/2\)인 수가 약수가 된다는 점을 이용하는 방법 등 다양한 풀이가 존재한..

A. There Are Two Types Of Burgers (00:04, +) 더 비싼 버거를 최대한 많이 만들어준 후 남은 빵으로 다른 버거를 만들어주는 것이 최적이다. B. Square Filling (00:08, +) 그리디하게 칠해준 후 두 배열이 같은지 확인하면 된다. C. Gas Pipeline (00:31, +) 길이가 2이상인 0을 만날때 마다 비용이 더 적은 경로로 이어주면 된다. D. Number Of Permutations (00:50, +) 전체 경우의 수인 \(N!\)에서 첫 배열로 정렬할 수 있는 경우와 둘째 배열로 정렬할 수 있는 경우를 빼준 후, 둘 모두로 정렬 가능한 경우를 더해주면 된다. 각 경우는 연속된 같은 수의 갯수만큼 팩토리얼을 해주면 구할 수 있다. E. XOR..

A. Simply Strange Sort (00:07, +) Div2 A답지 않은 구현 문제이다. 구현이 어렵진 않기 때문에 문제에서 하라는 것을 해주면 된다. B. Charmed by the Game (00:20, +) \(|a-b|/2\)의 값을 이용해 잘 탐색해주면 된다. 나는 머리가 안돌아가서 무지성으로 구현했다.. C. Deep Down Below (00:32,+) 각 동굴마다 \(A_i-i\)의 최대값을 저장해 준 후, 이를 기준으로 정렬한 후 파라메트릭 서치를 진행하면 된다. 이분탐색을 하지 않고도 답을 구할 수 있다 한다. D1. Up the Strip (01:06, +2) \(floor(N/i)\)의 값이 \(O(sqrt(N)\)개라는 것을 이용하면 \(O(Nsqrt(n))\)에 문제를 ..

A. Creating a Character (00:06, +1) \(max(0,min(exp+1,(str-int+exp+1)/2)\)가 답이다. B. Zmei Gorynich (00:14, +) 가장 효율이 좋은 무기를 사용하다 가장 공격력이 높은 무기로 마무리하면 된다. C. The Number Of Good Substrings (00:39, +) 관찰을 해보면, leading zero의 개수에 따라 해당되는 수가 최대 2개임을 알 수 있다. 따라서, 연속되는 0의 개수를 체크하다 1을 만났을때 가능한 수를 모두 체크하면 \(O(N)\)에 문제를 해결할 수 있다.

A. Dial Up (00:18, +1) *442 제자리에서 계속 더하다 처음 다른 값이 나오면 가장 가까운 곳으로 이동하고, 이후에는 나오는 값에 따라 1이나 2를 더해주면 된다. 불가능한 경우 처리는 쉬우니 생략하도록 하겠다. B. Squares (00:54, +) *1273 \(1\)부터 \(sqrt(N)\)까지는 모든 경우가 되므로 다 더해준다. 그러면 각 \(x\)당 가능한 \(y\)의 개수가 \(O(sqrt(N))\)개가 된다. 따라서 각 경우에 대해 구간의 길이를 곱해 더해주면 된다. C. LIS to Original Sequence (01:42, +4) *1896 다음과 같은 과정을 따른다. LIS의 원소를 \(A_1..A_k\)라 했을때 (1) \(i