안녕하세요. 에디토리얼 쓰고 싶다고 노래를 불렀던 Being입니다...

전반적으로 한국인 성적이 참 안 좋았던 대회네요. 특히 Level 2 문제에서 overflow 등등으로 득점을 하지 못한 것이 치명적인 것 같습니다.

Easy (250 pts.)

• 문제 설명 n명의 소비자에게 물건을 판매해야 하는데, 각각의 소비자마다 판매하는 데 드는 추가 비용과 그 값을 초과하면 판매하지 않는 가격 한계가 주어졌을 때, 최대의 이익을 내는 가장 작은 물건의 가격은 얼마인가? # 1 <= n <= 50 # 0 <= 가격 <= 10^6 [spoiler="풀이 보기"]naive하게, 가능한 가격의 범위인 10^6 안에서 모든 소비자에 대해 판매했을 때의 이익을 계산해 볼 수 있을 것입니다. 그러나 조금만 생각해 보면, 각각의 소비자들의 가격 상한이 critical한 지점임을 알 수 있습니다. 즉, 이 지점들만 고려하여도 충분합니다. 이를테면 각각의 소비자에 대해 이익-물건 가격 그래프를 그린다면 톱니 모양의 그래프가 나오게 되겠죠. 이 값들을 모두 더한 그래프를 따져보면 톱니의 꼭지점, 즉 가격 상한 지점만 고려하여도 된다는 것을 알 수 있습니다.[/spoiler]

Medium (500 pts.)

• 문제 설명 l x w x h 크기의 커다란 박스가 있다. 이 박스에 1x1x1, 2x2x2, 4x4x4, 2^k x 2^k x 2^k ... 꼴의 큐브들을 채워넣으려고 한다. 이 때 보유하고 있는 각 큐브의 개수가 있어서, 항상 채우지 못할 수도 있다. l x w x h 박스를 완전히 채워 넣으려면 보유한 큐브 중에 최소 몇 개를 사용해야 하는가? # 1 <= l, w, h <= 10^6 # 2^0 <= 큐브의 각 변의 크기 <= 2^19 # 1 <= 보유하고 있는 각 큐브의 개수 <= 10^6 [spoiler="풀이 보기"]풀이가 다양한데, 제 접근을 소개하겠습니다. 1차원의 경우 너무 단순하니, 2차원 문제를 먼저 떠올려 봅시다. 예를 들어 5x5를 채우려고 한다면, 아무리 어떻게 채우더라도 5x5에서 4x4 만큼의 영역을 제외한 짜투리 조각들은 1x1로 채울 수밖에 없을 것입니다. 5x4를 채우려고 한다면, 역시 4x4 만큼의 영역은 어떻게 채울 지 몰라도 나머지 영역은 1x1로 채워야만 합니다. 3차원에서도 같은 방법으로 접근할 수 있습니다. 즉, 지금 현재 l x w x h 크기의 박스를 채우려고 한다고 합시다. l을 가장 가까운 짝수로 내림한 것 ( (l >> 1) << 1 ) 을 l', w를 내림한 것을 w', h를 h' 로 정의한다면 l' x w' x h' 크기의 박스를 제외한 나머지 조각들은 1x1x1 큐브들 이외에 다른 방법은 생각할 수 없습니다. 그러면 이러한 큐브들을 재고를 탈탈 털어 일단 채워넣고 봅니다. 이제 l' x w' x h' 크기의 박스를 채워야 합니다. 이 박스의 각 변의 크기는 짝수니까, 큐브의 수가 충분히 많다고 치면 큐브와 박스의 크기를 전부 절반으로 나눔으로써, (l' / 2) x (w' / 2) x (h' / 2) 크기의 박스를 2^(i - 1) 꼴의 큐브들로 채우는 재귀적인 문제가 됩니다. 이런 식으로 채워나가다가 만일 큐브가 부족하다면, 각 큐브는 자기 자신보다 한 단계 작은 큐브 8개로 대체될 수 있으므로 최대한 사용해나가면 됩니다. 이러다가 큐브가 부족하다면 GG를 치시면 됩니다. 오버플로의 경우 위에서 자투리 영역을 채워넣을 큐브의 수를 계산할 때, 예를 들면 999999x999999x999999 - 999998x999998x999998 과 같은 상황이 발생할 수 있습니다. 이걸 아무리 (k+1)^3 - k^3 = 3k^2 + 3k + 1 등등의 공식을 통해 경우를 나누고 별 방법을 다 하더라도 오버플로 문제는 피할 수가 없습니다. 다행인 점은, 큐브의 크기가 최대 10^6이기 때문에 (10^6)^3 = 10^18 이 64비트 정수 안에 들어간다는 점이죠. 물론 64비트 정수로 계산하더라도 더 작은 큐브를 찾기 위해서 8배 8배 8배 하다 보면 끝도 없이 오버플로가 날 수 있습니다. 이럴 때 64비트 정수를 사용해 계산하다 필요한 큐브의 수가 지나치게 많아지는 경우, 즉 모든 큐브를 총동원해도 이런 사이즈는 맞출 수 없는 상황까지 가는 경우 무조건 불가능하다고 선언하면 됩니다. 뭐 strict하게 계산하지 않아도 대략 0x7FFFFFFF 정도만 잡아도 충분하죠. [/spoiler]

Hard (1000 pts.)

• 문제 설명 -9~+9 까지의 정수가 나열된 nxn square matrix가 있다. 여기서 n개의 element를 선택하는데, 각 행에 하나씩, 각 열에 하나씩만 선택할 수 있다. 선택된 element들의 행렬에서의 위치를 주욱 늘어놓았을 때, 어떤 element의 열 번호와 어떤 element의 행 번호가 같다면 두 element는 같은 그룹에 속하게 된다. 이로써 형성되는 환형 그룹의 개수가 짝수인 경우, 각 element의 값의 곱에 -1을 곱한 값이 점수가 되고, 홀수인 경우 각 element의 값의 곱이 점수가 된다. n개의 element를 선택하는 모든 방법에 대한 점수의 합을 121547로 나눈 나머지를 출력한다. [spoiler="풀이 보기"]matrix에서 모든 element를 각 열에 한 번씩, 각 행에 한 번씩 선택하여 그 곱을 모두 저장한다... 저는 매치 중간에 떠오르지 않았는데 챌린지 페이즈 때 코드를 보고 탄식했죠. 행렬의 determinant가 되겠습니다. WP: determinant의 정의 항목을 보시면 Here the sum is computed over all permutations σ of the numbers {1,2,...,n} and sgn(σ) denotes the signature of the permutation σ: +1 if σ is an even permutation and −1 if it is odd. 뭐 이런 말이 있습니다. 즉 우리가 일상적으로 determinant를 구하는 알고리즘 말고, 모든 permutation의 곱의 합을 구할 때 부호를 붙이는 규칙이 even permutation이냐 odd permutation이냐에 따라서 결정되는 것이거든요. 즉 문제의 조건과 완~전히 똑같습니다. 아흑. 밀접한 관련이 있죠 ㅠㅠ 어떤 permutation이 odd냐 even이냐 하는 것은 두 element의 위치를 바꾸는 transposition이 몇 개냐에 따라서 결정됩니다. odd permutation은 무슨 짓을 해도 홀수 번, even은 짝수 번 필요합니다. 위에서 말한 환형 그룹들을 생각해 봅시다. 선택한 permutation은 결국 i를 permutation[i]로 보내는 permutation이죠. 이걸 transposition으로 분해하려면 결국 환형 그룹들로 쪼개면 됩니다. 그리고 환형 그룹의 크기 - 1 회의 transposition이 필요하죠. 이걸 쭉 더해서 transposition이 홀수 개 필요한지 짝수 개 필요한지 생각해 보면 결국 n - #_of_group 개 만큼의 transposition이 필요하게 됩니다. 그러면 n이 홀수일 때는 determinant가 우리가 원하는 부호와 똑같이 나오게 되겠죠. n이 짝수일 때는 부호가 반대가 되니까 -1을 곱해 출력하면 됩니다. determinant 구하는 건 linear algebra에 자주 나오는 내용이겠지만, gaussian elimination으로 쭉 날리고 대각성분의 곱이 determinant가 됩니다. (elementary operation은 determinant의 절대값을 안 바꾼다고 하지요ㅠㅠ) 대신 이 과정에 필요한 것이 행렬 구현, 가우스 소거법 구현, 분수 구현.................등등이 있습니다. 라이브러리가 없는 사람들은 코딩하기 괴롭지 않았을까 싶습니다. [/spoiler] 다음 SRM에서는 한국이 좀 더 좋은 성적을 거둬야겠어요..일본을 공격해야 ㅋㅋㅋ
  [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]