Lifeignite

H. Polynomial BOJ 11500

 문제 설명 :

  어떤 함수 f(k)를 아래와 같이 정의한다. 

 이 때 우리는 f에 관한 새로운 식 S(n)을 정의할 건데 그건 또 아래와 같다.

이럴 때 S(n)을 n에 관하여 정리해보자면 아래와 같이 정리된다.

이 때 다음을 구해서 출력하시오.

주어지는 것은 다음이다. 

문제 풀이 :

 사실 이런 종류의 수식을 처음 접하는 사람은 이게 대체 뭔 개소린가 싶은 느낌이 들 것이다. 정수론과 굉장히 밀접한 식인데 처음 읽었을 때 도무지 분석을 할 수가 없었다.

 S(n)을 f(k)로 풀어보자면 다음과 같다.

일단, 

이식을 보면 이걸 n에 관하여 정리해야 하는데, 정수론에 대해 기초 지식이 있는 사람들은 (사실 고딩때도 배운다) 거듭제곱의 합이 n에 관한 식으로 나온다는 사실을 알 수 있다. 

예를들면,

요런 것들? 

따라서 거듭제곱이 같은 것끼리 모아보자.

위 식을 정리하면 아래와 같이 깔끔하게 나오게 된다.

이제 필요한게 0<=t<=25 사이에 있는 모든 거듭제곱의 합의 계수들만 찾으면 답이다.

근데이게 쉽지가 않다. 이 걸 찾기 위해서는 가장 마지막에 주어진 식이 필요하다.

1부터 n까지 k제곱의 합을 앞으로 T(n,k)라 했을 때 다음과같다.

^증명보시려면 클릭하세요.

위 식을 정리하고나면 0~k-1의 거듭제곱합을 통해서 k거듭제곱합을 구할 수 있다.

따라서 0,1,2,3,4...25까지 미리 거듭제곱의 합을 구해놓고 처리하면 끝

소스코드 보기 <- 클릭

문제집 : https://www.acmicpc.net/category/detail/1413

풀이는 하나하나 업데이트 될 예정입니다.

간략한 문제 분류와 솔루션만 제시 해놓고 풀이가 따로 필요하다고 생각되는 문제들은 추후 링크 하도록 하겠습니다. (요청하시면 그 부분에 관한 풀이도 올려드리겠습니다. ) 

A. Coin Swap  BOJ 11493

 flow문제 중에서도 MCMF문제다.  "동전의 교환 = 코스트" 로 두고 흰색을 모두 흰색으로 옮길때의 최소 코스트로 그래프 설계를 하면 된다.(검은색을 검은색으로 옮기는 코스트로 생각해도 무방) 흰색 정점이 있는 곳을 src와 연결하고 흰색 동전이 있는 곳을 sink로 돌렸을 때 나오는 MCMF결과를 출력하면 된다.

C. Grid BOJ 11495

 flow 문제 중에서도 이분 그래프로 만든 후 최대매칭하는 문제다. 익히 알려진 사실로 최대 매칭은 flow와 동치다.
 각각의 그리드를 순서대로 1, 2, 3,4... 번호를 매긴 후 인접한 것 끼리 연결한다. 이때 짝수는 src에 홀수는 sink에 연결하며 각각의 캐퍼시티는 그 그리드의 값으로 하고 매칭을 찾으면 된다.
 이 때 결과를 찾는 방법은 두가지 있는데 src와 sink에 남아 있는 캐퍼시티를 추적하는 방법과 전체에서 매칭의 수를 빼는 방법이 있다.(1매칭은 1코스트를 감소시켜주므로) 

D. Kernel  BOJ 11496

 기하 문제다.(segment tree로도 풀린다고 한다.) kernel이 존재할 수 있는 구간을 결정하고 그 위치가 주어진 polygon사이에 존재하는 지 결정하는 문제다. 열심히 그려보다보면 어떤 방식으로 kernel이 존재할 수 있는 구간을 결정하는 지 알 수 있다.(솔직히 이런걸 대회중에 발견하기는 어려워 보인다..)

E. Log Jumping BOJ 11497

 그리디 문제다. 통나무들을 길이 순으로 정렬하고 원의 왼쪽 오른쪽 차례대로 배치해 나가면 최적이 된다. 

F. Odd Cycle BOJ 11498

 그래프 문제 중에서도 SCC를 사용하여 시간을 줄이는 문제다. 사실 진짜 별거 없고 coloring하는데 그 coloring을 SCC내에서 하면 되는 문제다. 근데 한가지 조심해야할게 그냥 돌리면 WA가 날 수 있는데 사이클이 여러개 존재할 수 있다. 따라서 coloring을 back edge만 체크하게 해야한다. 이때 잘 처리 해줘야 TLE가 안난다. 

G. Path BOJ 11499

 기하 문제 중에서도 Convex_hull을 사용하는 문제다. 사실 그냥 컨백스 홀 만드는 방식으로 그냥 쭉 훑으면서 만들면서 최대 값을 갱신만 시켜주면된다.

H. Polynomial BOJ 11500 솔루션

 그냥 수식을 정리하는 문제다. 수학적 센스가 필요한 것 같다. (이미 알고 있다면 개꿀이었을 듯...) 수식을 정리해서 그대로 대입하면 된다. (하루종일 정리하면 된다.) 거듭 제곱의 합에 관하여 정리해야 한다.

I. Stock BOJ 11501

 파라매트릭 서치 문제다. 특정 상한을 결정하고 만들 수 있는지 검사한다. 이 때 검사는 선형으로 할 수 있어서 O(n) 그리고 파라매트릭에 logn이 들어 총 O(nlogn)이 든다. 

J. 3-Primes Problem BOJ 11502

 추측이라는데 그런가 보다 하면 된다. 그냥 하라는데로 하면 되는데 1000밖에 안된다. 따라서 소수 a,b를 결정하면 자동으로c가 결정된다. 여러가지 방법이 있는데, 전수 검사를 해서 (a,b,결정하고 c가 소수인지 확인) 푸는 방법, 넵섹하는 법, 등등 있다.

K. Tree Edit BOJ 11503

트리 dp문제다. 아직 안풀었다.

 L. Wheel of Numbers BOJ 11504

시뮬레이션 문제다. 직접 다해보면 된다.