생각날때마다 올리는 블로그

문제 링크https://oj.uz/problem/view/JOI14_secret 문제 요약 어떤 연산자 ★이 있다.얘가 결합법칙은 성립한다. 즉, (x★y)★z = x★(y★z)가 성립한다.이 때, 주어진 배열 A에서, 우리는 구간 L,R이 주어질 때,A[L] ★ A[L+1] ★ A[L+2].... ★ A[R]의 값을 알아내라. 함수형우리는 Secret란 함수를 통해서 x와 y의 ★의 값을 알 수 있다,우리가 구현해야하는 함수는 2개이다.두 함수는 다음과 같다. 1) Init(int N,int A[])N은 배열에 들어가있는 숫자의 개수이고, A는 배열을 나타낸다.초기화 단계로, 100점을 맞기 위해서는 Secret 함수를 최대 8000번 불러내야한다. (N

https://oj.uz/problem/view/JOI14_pinball 문제i번째에 사이에 있는 모든 좌표들을 로 보내버리는 핀볼 막대기가 위치하고, 각 막대기를 한 번 탈때마다 D_i의 비용이 듭니다.이 때, 어떤 좌표에서 떨어트려도 똑같은 좌표로 놓게 하는 핀볼의 배치 중에서, 최소의 비용이 드는 핀볼의 위치의 배치를 찾아서 그 비용이 얼마인지를 구하여라. 관찰이 문제를 그냥 아무 생각 없이 보면 상당히 복잡한 시뮬레이션 게임처럼 보인다. 하지만, 일종의 가정을 하고 나면 그 순간부터는 생각보다 간단한 문제로 바뀐다.공의 최종 위치를 항상 단조 증가하게 막대기를 놓는다고 하자. 이렇게 하면, 결론적으로 모든 공이 다 한쪽으로 모이기 위해선, 1번 공과 N번 공이 똑같은 곳으로 모이면 된다.나오는 출..

문제http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2492&sca=50 풀이일단, 1번 항목에 대한 것은 풀이하지 않겠다. 그 이유는, 단순한 유니온-파인드 자료구조이기 때문이다.유니온-파인드에 대해 궁금하다면 다음과 같은 사이트를 참조하자. http://bowbowbow.tistory.com/26 http://koosaga.com/6 다음은 문제가 되는 2번 과정이다.2번의 c=0일 때는 현재 존재하는 모든 팀들의 쌍의 개수이기 때문에, c=0일때는 무시하고 생각한다.2번 과정의 간단한 O(nq) 풀이는 다음과 같다.크기가 1~N인 배열을 만들어놓고, 1번을 수행할 때 동시에 size를 빼고 더해준다.예를 들어 크기가 4인것들과 크기가 6인것들이 동맹..