Wednesday, July 30, 2014

2013 Canadian Computing Competition, Stage 2, Day 2, Problem 3: Repetitivity

음... 일단 처음에 잘못된 dp로 접근해서... dm을 가지고 이리저리 관찰하다보니
aaaa.. bbbb... cccc ...
이런 것들은
aaaa... 에서 생성되는 파스칼 삼각형 * bbbb... 에서 생성되는 파스칼 삼각형 * ....로 되는 걸 관찰했다. 그런데 aaa...bbb...aaaa...cccc... 같이 되어버리면 aaaa..bbb...aaaaa.... 에다가 ccc...를 곱해주어야 되더라..ㅠㅠ
그래서 하는 수 없이 규칙성으로는 안되겠다고 생각하고 다시 dp로 접근해봤다.
d[i][j] : i번째 문자까지 고려하였을 때, subsequence의 길이가 j일 때의 sum(f(k)^2)의 값.
S[j] == S[i] (j < i)가 된다면 d[j-1]에다가 S[i]를 붙일 수 있는 걸 생각하고 열심히 짜보다가 말려서 irc에 도움을 요청했다. 한동안 어려움을 겪으시는 것 같아서 일단, 문제를 던져준 지훈이한테 해법을 받아서 봄.
가지고 있던 해법이라던 게 소스코드랑 주석인데, 주석에는 f(i)^2을 '어떤 특정한 subsequence가 나타나는 횟수가 f(i)인 것들의 pair 수'로 생각하면 문제를 풀기가 쉽다는 것과, 앞의 관찰을 통해 O(N^3)에서 O(N^2)으로 줄일 수 있다고 적혀있었다. 그러니까.. 예를 들어서 aaaba가 있고 특정한 subsequence인 aaa에 대해서 pair를 나열해보면 {(1,2,3),(1,2,3)}, {(1,2,3),(1,2,5)}, {(1,2,3), (1,3,5)} .... {(2,3,5),(2,3,5)} 총 16(=4^2)개.

소스 코드

D[i]를 i번째 문자까지 고려하였을 때, 'distinct한 subsequence들의 pair 수'의 합이라고 정의한다. 위에서 내가 생각했던 걸 써서, S[j] == S[i](j<i)가 되면 D[j-1]에다가 S[i]를 붙일 수 있기 때문에 D[j-1]값을 다음 S[k] == S[i](j<k<i)가 나올 때까지 D[r]에 (j ≤ r < k) 다 누적해준다. 그리고 최종적으로는 D[i]에서는 D[i-1]에다가 i번째 문자를 넣은 페어와 / 안 넣은 페어가 생기므로 D[i] = D[i-1]*2가 된다. 이해하기 위해서 뭔가 억지로 끼워맞춘 느낌인데... 그리디틱해서 명쾌하게 이해가 안된다ㅠㅠ 여담으로 이 문제를 대회 당시에 푼 사람은 딱 1명으로 Deng Calvin이라는 캐나다 친구인데, ioi 2013에서 은메달을 받았고 지금은 하버드에 있다고 한다... 똑똑한 친구구나...

으아.. N^3을 짰는데 자꾸 고쳐도 틀린다ㅠㅠ 중복 처리가 안되서 답보다 크게 나오는데... 음... N^3부터 올바르게 생각해야 N^2이 완벽히 이해가 될텐데...오늘은 자고 다음에 다시 생각해봐야지..

3 comments:

  1. d[i][j] = i>=j일 떄, 앞에서부터 i글자의 서브스트링의 임의의 subsequence 가 앞에서부터 j글자의 서브스트링의 임의의 subsequence 와 같은 경우의 수.

    예를 들어서 aba에 대해 d[3][2] = 5가 됩니다 - ___/___, a__/a__, __a/a__, _b_/_b_, ab_/ab_

    이렇게 정의하고 유도해보니 되네요.

    str이 1-based idx의 input string, len이 길이라고 하면,

    d[i][0] = 1
    if j<i, d[i][j] = d[i-1][j] + sum(d[i-1][k] if str[k+1]=str[i])
    if j=i, d[i][j] = d[i][j-1]*2

    이고 d[len][len] 이 답이 됩니다.

    ReplyDelete
    Replies
    1. 오오 테이블 정의부터가 완전 다르군요! 정말 감사합니다!ㅎㅎ

      Delete
    2. N^2 방법은 답글 달아주신 d[i][j]의 테이블 정의에서 조금 바꿔서 'd[i] : 앞에서부터 i글자의 서브스트링의 임의의 subsequence 가, 앞에서부터 i이하인 글자의 서브스트링의 임의의 subsequence 와 같은 경우의 수'라고 하면 되는 거군요!

      Delete