블로그 옮겼습니다

http://codeforces.com/contest/803/problem/D 너무 간단한 파라메트릭서치문제이다. 보자마자 파라메트릭서치임을 알았는데 구현이 막혀서 1시간동안 풀이못했기에반성하는 마음으로 기록용으로 글을 올린다..(정확히는 파라메트릭서치가 아니라 바이너리 서치라는데 나는 파라메트릭서치가 편하다..) 공백, 하이픈(-), 알파벳 대소문자로 이루어진 문자열 한줄과 만들 수 있는 최대 줄 수 K를 입력받는다.공백과 하이픈에서 줄을 바꿀 수가 있을 때 K줄을 넘지 않도록 하는 최대 가로폭(width) 를 구하는 문제이다.가로폭은 각 줄의 길이중 최대인 길이를 말한다. 그럼 그냥 단순히 가로폭의 상한을 정해놓고 그 가로폭을 최대로 갖도록 최대한 한줄에 꾸겨넣을 때 줄의 수를K개 이하로 만들 수 있..

큰 수 N의 모든 약수를 구하는 방법.큰 수라는 것은 int 의 범위를 넘으면서 long long 의 범위는 넘지않는 정도의 크기를 가진 수라고 생각하면 된다.약수를 구하는 가장 쉬운 방법은 1부터 N 까지 모두 돌며 N 을 나눈 나머지가 0인 것을 모두 찾으면 된다.하지만 N이 매우 크기 때문에 O(N) 으로는 구할 수가 없다. 그렇다면 어떻게 할까약수들의 특성중의 하나는 서로 짝을 이룬다는 것이다. 다시말해서N의 약수 i 가 있으면 N/i 도 약수라는 것이다. 그렇기 때문에 i가 N^0.5 를 넘어가면, 만약 약수가 존재하더라도 어차피 앞에서 봐준 것이기 때문에 또 봐줄 필요가 없다. 즉, N^0.5 까지만 반복하면서 N 을 나눈 나머지가 0인 수 i를 찾고i 를 찾았다면 N/i 도 같이 찾아주면 된..

http://codeforces.com/contest/803/problem/C N,K = K*(K+1)/2 냐 라는 말이 같고먼저 GCD를 정해주고 이 GCD로 strictly increasing 하는 K개로 분리가 가능한지즉, 고정된 GCD로 K개의 수를 각각 나눠서 모두 더한 값이 K*(K+1) 보다 크거나 같은지를 판단하기만하면되기 때문에GCD를 최대로 하기위해 가능한 가장 큰 GCD부터 가장 작은 GCD까지 반복하며 가장 큰 GCD를 찾은 뒤N을 그 GCD로 나눠서 strictly increasing 한 K개의 수를 만들고(1,2,3,... 처럼 1씩 증가시키다가 마지막 K번째 수에 다 때려박으면됨)K개의 수에 모두 GCD를 곱해주면 답이 될 것이다.만약 N/GCD >= K*(K+1)/2 가 되는..

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3148 K

BOJ 9359번 : 서로소 1

(해싱에 대한 개념은 제 개인적인 생각이 많이 섞여있어서 틀린 내용이 있을 수도 있다는 것을 미리 밝힙니다.) 해싱은 어떤 큰 데이터(스트링, 트리 등)가 있을 때 이 것을 하나의 수로 나타내어 비교를 하기 쉽도록(그리고 빠르도록)할 때 유용하다. 기본적으로 컴퓨터에서 저장할 수 있는 수의 크기의 한계가 존재하기 때문에보통 해시값은 아무리 커도 long long 범위 내에 들어 와야 한다. 그래서 modular 연산을 사용하게 되는데그러면 문제가 생길 수 있는게 서로 다른 데이터 인데 해시값이 같은 경우가 생길 수가 있는 것이다. 그래서 원래의 해쉬테이블은해시값이 단순히 해쉬테이블의 인덱스를 나타내고 그 인덱스에 실제 데이터가 링크드 리스트와 같은 형태로 연결되어서결국 실제 데이터를 찾는 과정이 필요하기..

이 문제는 흔히 가로외 세로의 길이가 같은 격자판에서 각 칸이 검은색 또는 흰색으로 이루어져 있을때 자식이 4개이거나 0개인 트리로 격자를 표현하는 '쿼드 트리' 라는 개념의 변형 문제이다. 격자가 주어졌을때 이 격자를 가장작은 정사각형모양으로 키우고 새로생긴 격자를 흰색으로 채운 뒤 쿼드트리의 노드의 개수를 구하는 것이 첫번째 요구되어지는 것이고 그다음엔 압축된 쿼드트리의 노드 수를 구해야 하는데 압축을 하는 방법은 공통된 서브 트리들을 딱 하나만남겨서 공유하는 것이다. 이렇게 할때 최소한의 노드 수를 사용하도록 압축했을 때의 노드의 수를 구하는 것이 두번째 요구되어지는 답이다. 우선 복잡도 계산을 위해 총 노드 수의 상한을 계산해보자. 격자의 가로 세로 길이는 128이 최대이기 때문에 쿼드트리의 높이..

http://codeforces.com/contest/681/problem/E 바퀴벌레의 좌표와 속도, 시간이 주어지고 N개의 접시에 대한 정보(좌표와 반지름)가 주어질 때 바퀴벌레가 접시 안에 들어가면 살 수 있는데 처음에 정한 방향으로만 갈 수가 있을 때, 바퀴벌레가 살 수 있는 확률을 구하는 문제 우선 바퀴벌레의 속도와 시간을 곱하면 바퀴벌레가 갈 수 있는 최대 거리가 되며, 바퀴벌레의 위치를 중심으로하고 반지름이 최대 거리인 원을 그렸을 때 접시들과 겹치는 방향들의 seq 들의 합집합의 각도들의 합에 대해 2π 로 나눠 주면 답이 된다. 일단 하나의 접시에 대해서만 생각해 보자. 우선 바퀴벌레의 이동가능 범위 원과 접시가 겹치지 않는다면 이 접시는 살 수 있는 확률을 전혀 증가시켜 주지 않는다. ..

https://community.topcoder.com/stat?c=problem_statement&pm=11476 N

https://community.topcoder.com/stat?c=problem_statement&pm=11500 우선 문제는 흔히 알고있는 '사천성' 이라는 게임을 최소한의 턴 수로 클리어 하기 위해 필요한 턴 수의 기대값이다.그냥 그때 그때 최적의 선택을 할 때 클리어 하는 데 필요한 턴 수의 기대값이라고 생각하면 될 것 같다. 처음에 실수할 수 있는 것이 뭐냐면.. 실제로 게임을 할 때 뒤집혀 있는 두개의 칸을 선택하면 이 두개가 동시에 뒤집히는것이 아니라 하나씩 선택을 하는데, 하나를 선택하면 이것이 뒤집하고 이 정보를 바탕으로 더 최적의 선택을 할 수가 있기 때문에 답이 다르게 나온다는 사실이다. 문제에서 플레이어는 한번 뒤집었던 칸의 모양은 평생 기억한다고 되어있기 때문에 클리어 까지 필요한..