안녕하세요. 에디토리얼이 끊긴지 오래된 것 같네요.
그동안 SRM을 풀어보면서 알고스팟 에디토리얼의 도움을 많이 받았는데요.
저도 조금이나마 도움이 되면 좋겠다는 생각에 이렇게 써봅니다.

하드는 푼 사람이 없어서, 이지 미듐만 빨리 풀고, 첼린지를 잘한 사람이 1등하는 셋이었습니다.
안타깝게도 페선생님은 Top10에 들어도 레이팅이 떨어지시네요.

Easy (250 pts.)

• 문제 설명
  소문자로 이루어진 단어들이 주어지면, 그것들을 이어붙여서 최소의 cost로 sentence를 만드는 게 문제입니다.
  각 단어는 그 알파벳들을 재배치할 수 있는데, 재배치하면 cost가 생기게 됩니다.
  cost는 원래 단어와 위치가 다른 알파벳 수로 정의됩니다. 예를 들어 "abc" -> "abc" 는 cost가 0이고,
  "abc" -> "acb", "bac", "cba" 는 cost가 2이고, "abc" -> "bca", "cab"는 cost가 3입니다.
  [spoiler="더 보기..."] * 해법
  기본적인 DP 문제입니다.
  dy[i] = sentence의 index i-1까지 만들 때, 최소의 cost
  substr(i,j) = sentence의 index i부터 알파벳 개수 j개를 가지는 substring
  words[] = 단어들
  dy[i] = min(dy[i-len] + cost(substr(i-len,len), words[j])) // len = length of words[j]
  이런 식으로 하시면 됩니다.
  cost함수는 입력으로 들어온 두 단어가 서로 재배치해서 같아질 수 있는지 검사해서
  불가능하다면 무한대를 리턴하고, 가능하다면 그 cost를 계산하면 되는데요.
  재배치해서 같아질 수 있는지는 각각을 정렬하고 같은지 비교해보면 됩니다.
  아래는 제가 실제 대회 때 작성했던 코드인데.. 점화식을 조금 달리 이용했습니다.
  i대신 i+len로 했네요.
  [code]
  #define REP(i,n) for(int i=0; i<(n); ++i)
  #define ALL(X) (X).begin(),(X).end()
  #define SZ(X) (int)(X).size()
  class SentenceDecomposition {
  public:
  int decompose(string, vector );
  };
  int anag(string a,string b)
  {
  sort(ALL(a));
  sort(ALL(b));
  return a==b;
  }
  int cost(string a,string b)
  {
  int c=0;
  REP(i,min(SZ(b),SZ(a)))
  if (a[i]!=b[i]) c++;
  return c;
  }
  int dy[2500];
  int SentenceDecomposition::decompose(string sent, vector val) {
  memset(dy,63,sizeof(dy));
  dy[0]=0;
  REP(i,SZ(sent))
  REP(j,SZ(val)) {
  int len=SZ(val[j]);
  if (anag(sent.substr(i,len),val[j])) {
  int cst=cost(sent.substr(i,len),val[j]);
  dy[i+len]=min(dy[i+len],dy[i]+cst);
  }
  }
  if (dy[SZ(sent)]>100) return -1;
  return dy[SZ(sent)];
  }
  [/code]
  [/spoiler]

  Medium (500 pts.)

• 문제 설명
  
  정사각형 모양의 케잌이 중심좌표 (0,0)에 놓여 있습니다. 가운데에는 정사각형 구멍이 하나 뚤려 있습니다.
  케잌의 크기와 구멍의 크기가 cakeLength, holeLength로 주어집니다.
  그리고나서 이 케잌을 수직이나 수평하게 자르는데 위 그림은 y=1, y=-4, x=1 이렇게 3번 자른 경우입니다.
  케잌을 다 자른 후에 케잌이 몇 조각으로 나뉘는지 구하는 게 문제입니다.
  [spoiler="더 보기..."] * 해법
  저는 cakeLength가 그리 크지 않길래 정수 좌표를 모두 격자로 나누고,
  BFS로 채우는 방법을 택했습니다.
  수직선 수평선에 붙어있는 격자점에서는 선을 넘어가지 못하게 해야 하죠.
  제 코드에서는 go배열이 그 역할을 합니다.
  [code]
  #define MP make_pair
  #define X first
  #define Y second
  #define PB push_back
  #define FOR(i,a,b) for( int i=(a); i<(b); ++i)
  #define REP(i,n) for(int i=0; i<(n); ++i)
  #define ALL(X) (X).begin(),(X).end()
  #define SZ(X) (int)(X).size()
  #define FORE(it,X) for(__typeof((X).begin()) it=(X).begin(); it!=(X).end(); ++it)
  class HoleCakeCuts {
  public:
  int cutTheCake(int, int, vector , vector );
  };
  int hy[4]={0,0,-1,1};
  int hx[4]={-1,1,0,0};
  int chk[205][205];
  int go[205][205];
  int cakl;
  void bfs(int x,int y)
  {
  queue q;
  chk[x][y]=1;
  q.push(MP(x,y));
  while (!q.empty()) {
  PII ka=q.front(); q.pop();
  x=ka.X,y=ka.Y;
  REP(i,4) {
  int py,px;
  px=x+hx[i];
  py=y+hy[i];
  if (go[x][y]&(1< if (px<0 || px>=cakl*2) continue;
  if (py<0 || py>=cakl*2) continue;
  if (chk[px][py]) continue;
  chk[px][py]=1;
  q.push(MP(px,py));
  }
  }
  }
  int HoleCakeCuts::cutTheCake(int ca, int hole, vector ycut, vector xcut) {
  cakl=ca;
  memset(chk,0,sizeof(chk));
  memset(go,0,sizeof(go));
  FOR(i,-hole+cakl,hole+cakl)
  FOR(j,-hole+cakl,hole+cakl)
  chk[i][j]=1;
  REP(i,SZ(ycut)) {
  int y=ycut[i]+cakl;
  REP(j,cakl*2+1) {
  go[j][y-1]^=8;
  go[j][y]^=4;
  }
  }
  REP(i,SZ(xcut)) {
  int x=xcut[i]+cakl;
  REP(j,cakl*2+1) {
  go[x-1][j]^=2;
  go[x][j]^=1;
  }
  }
  int dp=0;
  REP(i,cakl*2)
  REP(j,cakl*2)
  if (chk[i][j]==0) {
  dp++;
  bfs(i,j);
  }
  return dp;
  }
  [/code]
  그런데 다른 해법도 존재했습니다. 저랑 같은 방에서 하던 _Romka_라는 분의 해법인데요.
  저는 처음에 DFS나 BFS가 정해라고 생각하고, "뭐야, 이거 당연히 안 되겠지~"
  이러면서 첼린지를 했는데, 바로 실패해서, 더이상 첼린지는 안 하고 sys test만 기다렸습니다.
  근데 sys test 끝나고보니, 이 코드가 통과하더군요.
  어떤 방법인지는 각자의 숙제로 남길게요 >_<
  [code]
  int HoleCakeCuts::cutTheCake(int cl, int hl, vector h, vector v) {
  sort( h.begin(), h.end() );
  sort( v.begin(), v.end() );
  ans = (h.size()+1)*(v.size()+1);
  int ch = 0;
  int cv = 0;
  for ( int i=0; i if ( h[i] >= -hl && h[i] <= hl ) ch++;
  for ( int i=0; i if ( v[i] >= -hl && v[i] <= hl ) cv++;
  if ( ch > 0 || cv > 0 )
  ans -= ( cv-1 )*( ch-1 );
  return ans;
  }
  [/code]
  [/spoiler]

  Hard (1000 pts.)

• 문제 설명
  제가 아직 SRM을 하면서 하드를 풀어본 적이 거의 없어서... 언젠가 풀게 되면 채우겠습니다ㅠ

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