본문 바로가기

PS

(9)
BOJ#18865 이제 다시 시작이다 자력 플1 기분 좋고 ~ 사실 처음에 풀면서 골드인 줄 알았고, 실제로 아이디어 자체는 그렇게 어렵지 않다.세그트리이니만큼 플5이상 보정받고 (응용이니 3~4 이상), 손으로 해야하는 계산이 좀 귀찮긴 했다. 쨋든 기분조아져서 풀이 써야지 [풀이]x = 스피커부터 (ex, ey) 까지의 맨해튼 거리라고 하자.세 개의 세그를 준비해서 x에 대응되는 인덱스에 각각 $1,\space x,\space, x^{2}$에 대한 SUM 연산을 수행하게 하자. ex, ey부터 시작해서 훈련소를 덮는 삼각형의 한 변의 길이는 v-x가 된다.이제 구간을 4개로 나누어서 생각하자. 훈련소의 가로, 세로 중 짧은 것을 m 긴 것을 M이라 하자. 1) v-x ∈ [0, m] x ∈ [v-m, v]2) v-x ∈ (m, M] x ..
ICPC 2017 인터넷 예선 업솔빙 후기 첫 팀연습이다 ~ ! 한 명은 작년에 함께 했던 친구이며 ICPC에 매년 나오는 쌩구현 문제를 담당하고, 한 분은 올해 새로 영입했으며 수학(!!)을 매우 잘하신다. 올해 팀 구성 꽤 좋당!! 나는 음료수 서빙해야지 오예 셋이 합쳐서 총 6문제를 풀었으며, 마지막에 각자 EFG를 잡고 있었는데, 다들 학기 중에 코딩을 쉬던 상태라 삽질을 많이 해서, 더 잘할 수도 있었을 것 같다. 인터넷 예선이라 그런지 전형적인 문제가 많았다. EFGL도 플래이니만큼 굉장히 풀만했던 문제인 것 같으며, 팀연습 후 개인 업솔빙을 통해 FGL을 풀어보았다. 플래 중에서는 #D Grashoppper Route, #E Jerry and Tom, #G Map Labeling이 굉장히 좋은 문제라고 생각한다. 내가 푼 문제에 대해..
Google Code Jam 2020 Round 1A 후기 잠수탄다는 네모 어디 많이 바쁘긴 한데 학기 중 대회 즐기는 걸 생각하면서 겨울방학에 그렇게 공부햇는데 안 치는 게 말이 안된다. 결과도 꽤 만족스럽게 나와서 후기 써야지! 코딩할 줄 알고 (Pattern Matching) / 파스칼 삼각형 들어봤고 비트연산 할 줄 알면 (Pascal Walk) 두 문제를 풀 수 있다. 마지막 문제를 잡을 때는 시간이 조금 남았는데 지문 읽으면 끝날 거 같아서 과제하러 튀었다. 킥스타트랑 다르게 구코잼은 더 큰(?) 대회인만큼 비전형적인 문제가 많다. 그래도 1라운드까지는 알고리즘을 쓰는 문제는 잘 안 나온다. # Pattern Matching [문제] a*b*c, a*b*, 이런식으로 여러 개의 문자열이 원본 문자열의 일부를 *으로 치환한 채로 주어진다. 원본 문자열을..
Kick Start Round A 2020 후기 얍! 후기 써야지 네 문제 다 전형적인 느낌이다. 코딩할 줄 알고 (Allocation) / DP (Plates) / 파라메트릭 서치 (Workout) / 트라이 (Bundling) 를 다루어봤다면 쉽게 풀이를 떠올릴 수 있다. 그렇지만 트라이를 살면서 한 번 짜봐서 4번이 나한테는 까다로웠을 것 같다. 3번까지 빠르게 풀어서 올솔할 수도 있었을 것 같은데, 중간에 잠들어서 결국 3솔했다 ㅠ # Allocation [문제] N개의 집이 있고, 각각의 가격은 다르다. B달러가 있으면, 집을 최대 몇 개 살 수 있을까? [풀이] 쉬운 그리디이다. 가격 순으로 정렬하고, 싼 것부터 사면 된다. # Plates [문제] N개의 묶음이 있고, 각 묶음에는 K개의 접시가 있다. ( 접시의 Beauty가 NxK 행렬..
BOJ#11993 Circular Barn (Gold) 조금 생각해야하는 그리디다. 문제에 있는 예제는 그리기 힘드니, input : 7 2 0 2 0 3 0 0 ans : 15 인 예제를 사용해서 동작을 이해해보자. [접근] 편의상 입력을 거꾸로 받아 반시계 방향으로 문제를 살펴보았다. 배열의 인덱스가 증가하는 순으로 관리할 수 있어 구현이 편해진다. 배열의 인덱스가 의미하는 것은 Room 이고, 배열에 들어있는 값이 의미하는 것은 소의 개체수이다. 소가 방을 찾아가는게 무언가 그리디하다는 점을 느낄 수 있어서 다음과 같은 동작을 생각해보하면 답을 구할 수 있을 것 같다는 느낌이 든다. 자신의 오른쪽에 있는 (자신을 포함하여) 가장 가까운 소를 찾아 자신의 방에 넣는다. 다만 이렇게 하면 답은 1 + 1 + 4 + 25 = 31로 오답이 된다. 자신의 인덱..
USACO 2016 February Gold 업솔빙 한동안 유사코 골드 라운드 후기가 안 올라온 것은, 세 문제 다 푼 라운드가 없어서(...)이다.solved.ac 기준으로 플5/플5/골1로 이루어진 실력에 적합한(?) 세트를 찾아서 오랜만에 다 풀어보았다.이번 라운드는 공식 솔루션을 거의 보지 않았다. 공식 테케는 좀 참고했지만 꽤나 뿌듯하다 >__ 공식 테스트케이스와 영어로 된 솔루션은 이 링크에 있다.http://www.usaco.org/index.php?page=feb16results#11993 Circular Barn (Gold)와 자력플5!! 간단한 풀이를 적으려고 하다가 어느 순간 길어져서 게시글을 분리했다.#11994 Circular Barn Revisiteddp~ 제한이 작으니 적당히 DP하면 된다.dp [N: i번 방에서 시작해서] [..
1일 1알고 하는 글 - 실패 LAST UPDATE 2020-03-16꾸준히 갱신되는 글이다!갱신이 끝났다.요즘 갑자기 많이 공부해서 지친 것 같다.중간에 많이 게을러져서 망한 글(...)이다.개강해서 바빠져서 그냥 망한 글로 둬야지.사람의 계획은 언제나 성공할 수 있는 게 아니다 ㅎ..ㅎ1월에는 solved.ac 플5 랭작(https://nemo-algorithm.tistory.com/3)을 진행했으며, 민트에서 블루 중반까지 오를 수 있었다.실력이 올랐는지 모르겠는데, 일단 레이팅은 올랐으니 한동안은 알고리즘 이론을 늘리고자 한다. 언제나 강조하지만, 알고리즘 설명해주는 블로그 아니고, 블루 중후반에 있는 누군가가 적는 공부 일지이다.알고리즘 설명할 레벨도 안된다 ㅎㅎ 구글링하면 다른 똑똑한 분들이 적은 좋은 글들이 많다.글의 업..
USACO 2020 January Gold 업솔빙 후기 아마 한동안은 끌리는 문제 풀지 않을까. 쉽게 질려하는 내 성격에 문제집 하나 계속 푸는 건 솔직히 힘들었다. 골1 / 플5 / 플2 이렇게 세 문제로 이루어져 있는 세트이다. 한 문제 쉽고, 한 문제 확률적으로 풀 수 있을 거 같고, 한 문제는 어렵게 느껴질, 상당히 내 실력에 적합한 세트라고 생각했다. 공식 테스트케이스와 영어로 된 솔루션은 이 링크에 있다. http://usaco.org/index.php?page=jan20results ---------------------------------------------------------------------------------------- #18316 Time is Mooney DP문제이다. T변화량이 (T+1)^2-T^2이라 선형적인데 m[i]