제가 Editorial을 쓰는 날도 오는군요..;
어머니가 보시면 좋아하시겠네요. (어머니도 algospot을 자주 들어오십니다ㅋㅋ)
순위표를 보시지요.

언제봐도 흐뭇하군요. SRM에서 22등은 난생 처음 해봅니다.
첼린지에서 300점이나 땄으니 운이 많이 따랐다고 봐야 되겠죠.
한국인 코더들은 평균정도 했으나 레드 두분이 부진했다는 것이 아쉽군요.
그래도 국가순위로 10위 네덜란드를 바짝 추격하게 되었습니다.
...
이제부터 문제 설명과 풀이.
실력은 없지만 열심히 써보겠습니다.

250 EASY.
세로 크기 height, 가로 크기 width인 체스판이 주어집니다. 나이트(기사)가 왼쪽 제일 아래 칸에 있습니다. 이 기사는 상태가 안 좋아서 오른쪽으로밖에 못 움직입니다. 그래서 4종류의 이동 방법이 있습니다.
1. 위로 두칸 간 다음에 오른쪽으로 한칸 이동.
2. 위로 한칸 간 다음에 오른쪽으로 두칸 이동.
3. 아래로 한칸 간 다음에 오른쪽으로 두칸 이동.
4. 아래로 두칸 간 다음에 오른쪽으로 한칸 이동.
기사는 체스판의 여러 지점을 최대한 많이 방문하고 싶은데, 네 종류의 이동 방법을 적어도 한번씩은 써야 합니다. 네 종류의 이동 방법을 한번씩 쓰지 않는다면, 최대 3번까지만 이동이 가능합니다. 이 기사의 최대 이동 횟수를 구하세요.
1 <= height, width <= 200,000,000
[spoiler="해법을 보시겠어요?"]먼저 제가 푼 방식을 소개하겠습니다.
일단 최대 3번까지 이동할 수 있다고하면, 몇 번 이동할 수 있는지를 세어봅니다. BFS를 이용했습니다.
오른쪽으로 한칸 이상은 반드시 가게 되어있고, 2번 이동과 3번 이동을 최소 한번씩은 써야되기 때문에 나올 수 있는 최적의 답은 width-2 입니다.
height가 3 이상인 경우에는 이동 방법을 1~4의 번호로 표시했을 때, 아래와 같은 방법으로 이동이 가능합니다.
2->3->1->4->1->4->1->4->1->4->... (1과 4의 반복)
이렇게 이동하면 width-2의 답을 얻어낼 수 있습니다.
그래서 height가 3 이상이면 처음에 BFS로 얻은 답과 width-2 중에 큰 값을 답으로 출력했습니다.
[code]
struct ele {
int t,x,y;
};
queue q;
int hy[4]={-2,-1,1,2};
int hx[4]={1,2,2,1};
int LameKnight::maxCells(int height, int width) {
ele tmp;
int pos=0;
tmp.t=1;
tmp.x=tmp.y=0;
q.push(tmp);
while (!q.empty()) {
tmp=q.front();
q.pop();
pos=max(pos,tmp.t);
if (tmp.t==4) continue;
for (int i=0;i<4;i++) {
int py,px,x,y;
x=tmp.x;
y=tmp.y;
py=y+hy[i];
px=x+hx[i];
if (py<0 || px<0 || py>=height || px>=width) continue;
ele tmp2;
tmp2.t=tmp.t+1;
tmp2.x=px;
tmp2.y=py;
q.push(tmp2);
}
}
if (height>=3)
pos=max(width-2,pos);
return pos;
}
[/code]
사실 제 방법은 너무 쓸데없이 긴 것 같고요, 같은 방에서 하던 nya라는 분의 솔루션을 소개하겠습니다.
[code]
int maxCells(int height, int width) {
if (height == 1)
return 1;
if (height == 2)
return min((width+1)/2, 4);
return max(min(width, 4), width-2);
}
[/code]
깔끔하게 잘 짠 것 같습니다.
[/spoiler]

500 MEDIUM.
n종류의 카드가 각각 cards[i]개가 있습니다. ( 0 <= i < n ) 그리고 조커가 jokers개 있습니다.
이 카드로 한 묶음을 만들 수 있는데, 두가지 방법이 있습니다.
1. n종류의 카드를 모두 하나씩 고른다.
2. n-1종류의 카드를 하나씩 고르고, 조커를 하나 고른다.
지금 가지고 있는 카드로 최대한 많은 묶음을 만들면 총 몇 묶음을 만들 수 있을까요?
1 <= n <= 50
0 <= cards[i], jokers <= 500,000,000
[spoiler="해법을 보시겠어요?"]"m개의 묶음을 만들 수 있는가?"에 대한 답("예 or 아니오")을 O(n)만에 구할 수 있습니다. 또한 m개의 묶음을 만들 수 있다면 m-1개의 묶음도 만들 수 있고, m개의 묶음을 만들 수 없다면, m+1개의 묶음도 만들 수 없기 때문에 답을 이분검색으로 찾을 수 있습니다.
cards[i]와 jokers가 500,000,000인 것으로 봐서 출제자의 의도가 이분검색이었던 것으로 추측해봅니다.
m개의 묶음을 만들 수 있는 경우에는 아래 두 조건이 성립해야 합니다.
1. cards[i] < m 인 경우, i번 카드에 대해 조커를 m-cards[i]개 만큼 채워야 한다. 그럼 필요한 조커의 개수가 나오는데, 그 수가 jokers이하여야 한다.
2. 필요한 조커의 개수가 m이하여야 한다. 조커는 한 묶음에 하나씩만 사용할 수 있기 때문이다.
이 조건을 고려해서 프로그램을 짜면
[code]
#define ll long long
#define MAX 500000000
int n;
int CompilingDecksWithJokers::maxCompleteDecks(vector cards, int jokers) {
n=cards.size();
int l=0,r=MAX*2,m;
int dp=0;
while (l<=r) {
m=(l+r)/2;
ll sum=0; //숫자가 커서 overflow의 위험이 있습니다. 그래서 long long을 썼습니다.
for (int i=0;i if (cards[i] sum+=m-cards[i];
if (sum<=jokers && m>=sum) {
dp=m;
l=m+1;
}
else
r=m-1;
}
return dp;
}
[/code]
이렇게 됩니다.
제가 이 문제에서 첼린지로 300점을 획득했는데 제 전략을 소개하자면 매우 간단합니다.
우선 랜덤으로 적절히 데이터를 만들고, 이분검색으로 풀지 않은 사람만 공략했습니다.=_=
[/spoiler]

1000 HARD.
문제를 모릅니다.
[spoiler="해법을 보시겠어요?"]문제를 모릅니다. =_= [/spoiler]

12월 4일 어머니 생신이었는데 깜빡하고 지나갈 뻔 했습니다.
어머니, 생신 축하드립니다. (--)(__)