ACRush가 말도 안되는 빠른 스피드로 Level 3을 풀어서 1등을 차지한 가운데, 한국인에서는 유일하게 Level 3를 패스해서 에디토리얼을 쓰게 된 Astein입니다 -_-;

Easy (250 pts.)

• 문제 설명
  길이가 L이며, 0이상 L-p+1이하의 모든 i에서 'i번째 글자'와 'i+p번째 글자'가 같은 문자열이 있을 때, 이 문자열을 '주기가 p이다' 라고 말한다. 예를 들어 'CATCATC', 'CATCAT', 'ACTAC', 'ACT'는 모두 주기가 3인 문자열이다.
  어떤 염색체 문자열이 입력으로 주어진다. maxPeriod보다 주기가 짧은 문자열을 만들고 싶은데, '치환'작업을 최소화하려고 한다. '치환'작업이란 어떤 글자를 다른 글자로 바꾸는 것을 의미한다. 최소 몇 번의 치환 작업을 수행했을 때 maxPeriod보다 주기가 짧은 문자열을 완성할 수 있을지 구하시오.
  [spoiler="더 보기..."] * 문제 해법
  만약 주기가 1이라고 가정해 봅시다. 그러면 모든 글자가 같아야 가능하지요. 따라서 이 때 치환작업을 최소화 하려면 문자열에서 제일 많이 나타나는 글자로 만드는 것이 낫다는 것을 발견할 수 있습니다.
  주기가 2라고 하면, 짝수번째에 위치한 글자들이 서로 모두 같아야 하고, 홀수번째에 위치한 글자들끼리 모두 같아야 하지요. 그러면 홀수번째에 가장 많이 나온 글자로 홀수번째 위치를 채우고, 짝수번째에 가장 많이 나온 글자로 짝수번째 위치를 채우는 것이 최소한의 치환작업을 거쳐 주기-2인 문자열을 만들 수 있게 됩니다.
  이를 주기가 k인 문자열에 대해서 확장할 수가 있지요. 편의를 위해 xjtuhyh의 code 를 링크합니다. (에디토리얼에 소개된 소스코드 입니다.)
  [/spoiler]

  Medium (500 pts.)

• 문제 설명
  흰색('.')과 검은색('#')으로 구성된 이미지가 있다. 검은색 점이 서로 인접해 있는 경우 같은 그룹에 있다고 말할 수 있다. 또한 같은 그룹에 속한 임의의 두 검은색 점을 잡았을 때, 두 점 간의 최단거리가 manhattan distance만큼이 되는 경우 smooth하다고 말한다. manhattan distance란 (xA, yA), (xB, yB)의 두 점이 있을때 |xA - xB| + |yA - yB|값을 의미한다.
  친구가 smooth image를 전송했는데, 일부 에러들 때문에 몇몇 검은색 점이 흰색으로 바뀌어 버렸다 (원래 흰색점은 모두 그대로 흰색점인 상태이다.) 에러가 섞인 image를 원래의 smooth image로 만들고 싶어한다. 가능한 적은 수의 흰색 점을 검은색으로 바꾸어 smooth하게 만들려고 한다. 답은 언제나 유일하다.
  [spoiler="더 보기..."] * 문제 해법
  저는 대회때 접근도 못했는데 다른 소스들을 보니 쉽게 풀었더군요 ㅠㅠ
  같은 그룹에 있는 점들을 하나의 집합으로 생각합니다. 이 집합에 대하여 같은 x좌표를 가진 점들이 있으면, 이들은 모두 일직선으로 연결되어 있어야 하겠지요. (y좌표에 대해서도 마찬가지입니다) 즉 ㄷ 자 모양이 있을때 세로선이 존재해야 한다는 뜻이지요.
  위의 과정을 더이상 검은색으로 변환하는 과정이 없을때까지 반복하면 됩니다. 이러한 변환과정 횟수가 거의 없기 때문에 생각보다 빠른 시간안에 프로그램이 종료되는 것을 확인 할 수 있습니다 :)
  [/spoiler]

  Hard (1000 pts.)

• 문제 설명
  Nim Game은 여러개의 바구니에서 성냥을 꺼내는 게임이다. 한 턴에 플레이어는 하나 이상의 성냥을 꺼내야 하는데 반드시 하나의 바구니에서만 꺼내야 한다. 마지막 성냥을 가져가는 사람이 이긴다.
  당신은 친구와 기존의 Nim game을 하다가 매우 지겹다고 생각하고 있다. 그래서 게임의 규칙을 바꾸게 되었다. 바꾼 규칙은 두 페이즈로 구성되어 있다. 첫번째 페이즈에서는 당신이 전체 바구니에서 몇 개의 바구니를 (당신이 원하는 만큼) 제거한다. 그 다음은 상대방이 자기가 원하는 만큼의 바구니를 제거한다. 하나도 제거하지 않는 것은 가능하지만, 모든 바구니를 제거하는 것은 불가능하다. 두번째 페이즈는 기존의 Nim game과 같은 규칙을 따른다.
  각각의 바구니에 몇 개의 성냥이 있는지가 입력으로 주어진다. 당신은 첫번째 페이즈에서 성냥을 가능한한 조금 제거하여 이기고 싶다. 둘 다 최선을 다한다고 할 때, 몇 개의 성냥을 제거했을 때 당신의 승리를 보장할 수 있겠는가?
  [spoiler="더 보기..."] * 문제 해법
  무엇보다도, 이 문제를 풀기 위해서는 사전지식이 좀 필요합니다. 일반적인 Nim Game에서 항상 이기는 경우를 알고 있어야 하기 때문이지요.
  [/spoiler]

  [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]