[editorial] TCO09 Qual 2

  • Taeyoon_Lee
    Taeyoon_Lee

    11등한 기념으로(형들이 쓰래서) 에디토리얼을 써보겠습니다.
    qual2.PNG
    250, 500, 1000으로 구성된 set이었는데, 그럭저럭 알맞은(?) 난이도였다고 생각합니다.
    예상외의 인물이 1등을 했는데, 저도 1등 한번 해보고 싶어요.(?)

    Easy (250 pts.)

    문제 설명

    n*m 격자로 나뉘어져 있는 나무판이 있습니다.
    각 격자는 검정(B)색이나 흰(W)색이 칠해져 있습니다.
    우리는 8*8 크기로 나무판을 잘라서 체스판을 만들 것입니다.
    체스판은 인접한 모든 격자가 서로 다른 색이어야 합니다.
    그래서 나무판을 자른 후에, 각 격자에 색칠을 다시해야 하는데,
    색칠해야 되는 칸이 최소가 되도록 자르면, 몇 칸을 색칠하면 될까요?


    250답게 brute force로 해결할 수 있습니다.
    가능한 체스판은 아래와 같이 두종류가 있습니다.

    WBWBWBWB     
BWBWBWBW
BWBWBWBW     WBWBWBWB
WBWBWBWB     BWBWBWBW
BWBWBWBW     WBWBWBWB
WBWBWBWB     BWBWBWBW
BWBWBWBW     WBWBWBWB
WBWBWBWB     BWBWBWBW
BWBWBWBW     WBWBWBWB

    두가지 판을 가능한 모든 위치에 대응해보면서
    처음 칠해진 칸과 다른 칸의 개수를 세어보면 됩니다.

    #define FOR(i,a,b) for( int i=(a); i<(b); ++i) 
#define REP(i,n) for(int i=0; i<(n); ++i) 
#define SZ(X) (int)(X).size() 
class RepaintTheChessboard { 
public: 
  int minimumChanges(vector <string> dt) { 
    int n=SZ(dt),m=SZ(dt[0]); 
    int dp=234234234; 
    REP(i,n-8+1) { 
      REP(j,m-8+1) { 
        int su=0; 
        FOR(y,i,i+8) 
          FOR(x,j,j+8)  { 
            if ((y+x)%2==0 && dt[y][x]=='W') su++; 
            if ((y+x)%2==1 && dt[y][x]=='B') su++; 
          } 
        dp=min(dp,su); 
        dp=min(dp,64-su);
      } 
    } 
    return dp; 
  } 
};

    Medium (500 pts.)

    문제 설명

    1페이지부터 N페이지까지 적힌 책이 있습니다. 이 책에 0부터 9까지 각각의 digit는 몇번 등장할까요?

    N이 10억이기 때문에 간단한 O(n) 방법은
    시간 제한에 걸리게 됩니다. 덕분에 첼 하나 했죠. :)
    제 방법은 "10*N의 길이" 정도의 반복으로 풉니다. (결국 O(logN)이죠.)
    다른 방법도 있을 것 같은데,
    이미 푼 문제는 더 연구하지 않는 게으른 성격 탓에
    찾아보진 않았네요.
    예를 들어서 설명해볼게요.
    123부터 456까지 각각의 디지트의 개수를 구해보죠.
    우선 숫자를 늘어놓아 볼까요?

    123
124
125
.
.
.
454
455
456

    그리고 위 아래에서 숫자를 하나씩 처리합니다. (답에 누적시킵니다.)

    123
124
.
.
129
130
131
.
.
448
449
450
451
452
.
.

    시작 숫자의 1의 자리가 0이면 계산을 잠시 멈추고,
    마지막 숫자의 1의 자리가 9면 역시 계산을 잠시 멈춥니다.
    그리고 위에서부터 숫자를 10개씩 묶어 볼게요.
    0으로 시작해서 9로 끝나니까, 딱 맞게 묶이겠죠?
    그러면 우선 1의 자리부터 처리합시다.

    130
131
.
.
448
449

    0~9가 각각 (44-13+1)개가 있습니다. 계산하시구요.
    1의 자리를 처리하고나면, 문제는
    13부터 44까지 등장하는 각각의 디지트를 세는 문제로 바뀝니다.
    물론 곱하기 10을 해서 답을 구해야 겠죠?

    typedef vector<int> VI; 
#define REP(i,n) for(int i=0; i<(n); ++i) 
VI dp;
void ret(int ka,int kb) 
{ 
  while (ka>0) { 
    dp[ka%10]+=kb; 
    ka/=10; 
  } 
} 
class PageNumbers { 
public: 
  vector <int> getCounts(int N) { 
    int a=1,b=N,c=1;
    dp = VI(10,0);
    while (a<=b) { 
      while (a%10>0 && a<=b) 
        ret(a++,c); 
      if (a>b) 
        break; 
      while (b%10>0 && a<b) 
        ret(b--,c); 
      REP(i,10)
        dp[i]+=(b/10-a/10)*c; 
      ret(b--,c); 
      a/=10; 
      b/=10; 
      c*=10; 
    } 
    return dp; 
  } 
};

    Hard (1000 pts.)

    문제 설명

    매초 1씩 카운트가 증가하는 N자리 숫자 디지털 카운터가 있습니다.
    카운터는 숫자가 계속 돕니다. 10^N - 1 다음에 0이 됩니다.
    (자리수는 계속 유지되어 999 다음에는 000이 됩니다.)
    0부터 9까지 각각의 숫자는 7개 이하의 선분으로 이루어 집니다.
    0은 6개, 1은 2개, 2는 5개... 생략 {6,2,5,5,4,5,6,3,7,5}
    현재 카운터에 적힌 숫자가 주어집니다.
    현재 적힌 숫자를 쓰는데 이용된 선분의 합과,
    선분의 합이 같은 숫자가 나오려면 몇 초를 기다려야 될까요?


    제가 푼 방식보다 훨씬 좋은 방법이 있는 것 같은데,
    역시 이미 pass했기 때문에, 'ㅁ' 굳이 공부하진 않아서,
    제 방법을 써보겠습니다.
    시간에 쫓기면서 푸느라 코드가 더러워서,
    여기에 제 코드 전체를 쓰진 않겠구요,
    주요 부분만 보여드리겠습니다.
    우선 다이나믹 테이블을 하나 만듭니다.
    dy[i][j][k] = 길이 i에서, 선분이 j개 남았을 때, 제일 앞에 k라는 숫자가 올 수 있는가? (있다면 1, 아니면 0)
    dy[i][j][k] = dy[i-1][j-su[k]][0~9] 중에 1이 있으면 1, 아니면 0

    #define FOR(i,a,b) for( int i=(a); i<(b); ++i) 
#define REP(i,n) for(int i=0; i<(n); ++i) 
#define FORD(i,a,b) for( int i=(a); i>(b); --i) 
int dy[20][110][15]={0,}; 
int su[10]={6,2,5,5,4,5,6,3,7,5}; 
    REP(i,10) dy[1][su[i]][i]=1; 
    FOR(i,2,20) 
      FOR(j,1,110) 
        REP(k,10) if (j-su[k]>=0) 
          REP(q,10) if (dy[i-1][j-su[k]][q]) 
            dy[i][j][k]=1;

    이걸 구해놓으면 뒷자리부터 하나씩 올려가면서
    계산을 해볼 수 있습니다.
    예를 들어 현재 숫자가 123456이라고 하면
    끝에 6을 7, 8, 9로 하나씩 바꿔가면서 가능 여부를 검사합니다.
    6을 쓰는데 이용되는 선분의 수가 6이니까
    dy[1][6][7], dy[1][6][8], dy[1][6][9] 중에 1이 있나 검사를 해보고, 있으면 그렇게 바꾸면 됩니다.
    하지만 아쉽게도 전부 1이 아닙니다.
    그러면 다음 자리로 옮겨와서 5를 하나씩 올려봅니다.
    56을 쓰는데 이용된 선분의 수는 11개니까
    dy[2][11][6], dy[2][11][7], dy[2][11][8], dy[2][11][9]를 찾아보겠죠.
    dy[2][11][6]이 1이겠네요. 그럼 5를 6으로 바꿔주고,
    그 뒷자리는 무조건 가능한 가장 작은 수로 써줍니다. 역시 dy배열을 참고해서 해야 겠죠?
    dy[1][5][2]가 1일 테니, 처음에 "56"이었던 숫자가 "62"로 바뀌면 되겠군요.

    #define FOR(i,a,b) for( int i=(a); i<(b); ++i)
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FORD(i,a,b) for( int i=(a); i>(b); --i) 
// dt[0,n-1] 에 각 자리의 숫자가 들어가 있습니다.
    FORD(i,n-1,-1) { 
      int bu,sum; 
      bu=dt[i]; 
      sum=0; 
      FOR(j,i,n) sum+=su[dt[j]]; // 바꿀 숫자들의 선분 합을 구합니다.
      while (dt[i]<9) { // 9일 때까지 바꿔 봅니다.
        dt[i]++; 
        if (dy[n-i][sum][dt[i]]) { // 가능하다면, 그렇게 써주고
          sum-=su[dt[i]];
          i++; 
          while (i<n) { // 뒷자리는 가능한 제일 작은 수로 채웁니다.
            REP(j,10) 
              if (dy[n-i][sum][j]) { 
                sum-=su[j]; 
                dt[i]=j; 
                break; 
              } 
            i++; 
          } 
          // 현재 바뀐 숫자에서 원래 숫자를 빼서 답을 구합니다.
          // 생략했습니다.
          return ret; 
        } 
      } 
      dt[i]=bu; // 9일 때까지 바꿔 보았는데, 가능한 경우가 없으면 그냥 다시 돌려 놓습니다.
    }

    만약 입력이 "11111"나 "71111" 이런 형태면 "99999"가 될 때까지 가능한 답을 찾을 수가 없습니다.
    그렇다면 어떻게 하면 될까요?
    간단합니다. (하지만 더럽습니다.)
    "00000"이 될 때까지 시간이 흘렀다고 생각하고, 그때까지 걸린 시간을 구해놓고, 답을 구하세요.
    이때는 전체 성냥 개수를 미리 저장해서 계산해야 되는데..
    자세한 코드는 적지 않을게요.


    이해가 안 되는 부분 있으면 리플로 알려주세요~
    여기까지 읽어주신 분, 감사합니다. emoticon

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

    15년 전
6개의 댓글이 있습니다.
  • astein
    astein

    만약 입력이 "11111"나 "71111" 이런 형태면 "99999"가 될 때까지 가능한 답을 찾을 수가 없습니다.
    그렇다면 어떻게 하면 될까요?
    --> tricky 한 방법이 있는데,
    모든 입력의 앞에 "2"를 붙여주고 실행합니다. ( lit[2] = lit[3] 임을 이용 )
    "211111"의 답은 "311111"이 되고, "271111"의 답은 "311117"이 되는 식이지요.


    15년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    우왕ㅋ 좋은 방법이네요~


    15년 전 link
  • JongMan
    JongMan

    하드에서 더 좋은 방법은, 에디토리얼에도 나온 방법이지만, 두 가지 경우로 나눠 푸는 것인 것 같아요.
    1. 주어진 숫자를 A 라고 할 때, A < B 에 대해서 count(A) == count(B) 인 경우
    a. A 와 B 가 첫 자리에서 달라질 때: B 의 해당 자리 수는 A 의 해당 자리수보다 커야 합니다.
    b. A 와 B 가 두번째 자리에서 달라질 때: B 의 해당 자리 수는 A 의 해당 자리수보다 커야 합니다.
    c.
    d. ...
    2. B < A 인 경우: 99999...9 를 지나 wraparound 한 경우죠.
    두 경우 모두, smallest[i][j] = i개의 segment 를 가지고 만들 수 있는 j자리의 수 중 가장 작은 것은? 이라는 점화식을 풀면 쉽게 풀 수 있죠. 'X 보다 lexicographically larger 중 가장 작은 것 구하기' 스타일의 문제를 풀 수 있는 일반적 패턴인데.. 'X 와 Y 가 달라지는 첫 번째 위치' 를 찾는거죠. 그 전은 X 와 똑같아야 하고, 그 이후는 가능한 가장 작은 수일 테니까요.


    15년 전 link
  • astein
    astein

    음.. 제가 연습할 때 푼 방법도 위에서 JM님이 설명해 주신 방법과 완전히 같네요 :$
    wraparound인 경우는 첫번째 댓글에 달아뒀던 것처럼 string의 앞에 "2"를 붙여주면 해결이 되고요.
    " smallest[i][j] = i개의 segment, j자리의 수 중 가장 작은 것은? " 이라는 문제는 greedy 로 해결 가능한 문제입니다.
    k 자리의 digit을 채우는 segment는 최소 2k개, 최대 7k개임을 알 수 있기 때문이죠. 앞자리를 0 ~ 9 까지 채워넣어가면서,
    k-1 자리의 digit에서 사용할 수 있는 segment가 2(k-1)이상, 7(k-1)이하인 경우는 앞자리를 고정시킬 수 있으니까요 :3


    15년 전 link
  • Being
    Being

    오래 전 글이라 깨진 곳이 많아서 손봤습니다. :) 지금 생각해보면, 미듐에 대해 1부터 1345까지의 답을 구한다고 하면, 이 답이 [1, 133] 까지의 답에 10배한 것에다가 1340 1341 1342 1343 1344 1345만 더 고려하면 되는 것 아닌가 싶네요.


    10년 전 link
  • Being
    Being

    아, 1, 2, 3, 4, 5, 6, 7, 8, 9 도 생각해야겠군요.


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.