미러에서 풀었어야 했는데 괜히 능지 더 쓰려다가 못 풀었다. 3시간 째 실제 대회에서 푼 사람이 안 나오길래 엄청 어려운 줄... 

그래도 문자열 문제 어떻게 푸는지 기억이 아예 사라진 것은 아니어서 조금 신기했다. 가뭄에 콩 나듯 하는 PS....

 

Suffix Array + LCP를 만들자. 여기서 만약에 $$\max(lcp_{i-1}, lcp_{j+1}) < \min(lcp_i, lcp_{i+1}, \cdots, lcp_j)$$가 성립한다면, $i-1$번째 substring 부터 $j$번째 substring까지 총 $j-i+2$개의 substring이 $$\min(lcp_i, lcp_{i+1}, \cdots, lcp_j)$$ 길이의 common prefix를 가지며, 특히 $$[\max(lcp_{i-1}, lcp_{j+1}) + 1, \min(lcp_i, lcp_{i+1}, \cdots, lcp_j)]$$ 구간에 속하는 길이의 prefix 들은 정확히 $j-i+2$번 등장하게 된다. 즉, 이들은 $f(j-i+2)$에 들어가는 후보군이라고 볼 수 있다. 

 

그래서 일단 저런 경우들을 모두 관리해야 하는데, 이건 stack을 써서 할 수 있다. 대충 $st$번째 문자열부터 $en$번째 문자열까지 common prefix가 $l$이라는 것을 하나의 struct로, 즉 $(st, en, l)$ 형태로 관리한다고 치자. 그러면 $lcp_i$를 보면서 얻는 것은 $(i-1, i, lcp_i)$라는 struct다.

 

이제 stack을 머리속으로 그리면서 생각을 해보자. 스택의 top을 $S$라고 생각을 하고, 지금 $(i-1, i, lcp_i)$를 본다고 하자.

  • $S_l > lcp_i$인 경우를 생각해보면, 현재 [$S$ 이전의 원소인 $T$], [$S$], [$(i-1, i, lcp_i)$]가 순서대로 stack에 대기중이다.
    • stack 상 invariant를 하나 유지하자. 이제부터 stack에 쌓인 순서대로 $l$ 값이 증가하도록 한다. 자연스러운 생각이다.
    • 그러면 $S_l > \max(T_l, lcp_i)$이므로, 여기서 $f$ 값을 update 할 케이스가 발생한다. 
    • 즉, $[\max(T_l, lcp_i) + 1, S_l]$ 구간에 속하는 prefix들은 정확히 $S_{en} - S_{st} + 1$번 등장하게 된다. 
    • 이제 $f$를 계산하려면 disjoint occurrence 횟수를 계산해야 한다. 
      • 이는 $S$에 대응되는 suffix array 값들을 set으로 관리하고, naive 하게 lower bound를 사용하면서 계산하면 된다.
      • 결국 "최대 occurrence를 유지하는 최대 길이"를 계산해야 하는데, 이는 $[\max(T_l, lcp_i) + 1, S_l]$에서 이분탐색을 하면 된다.
    • 이제 다시 $T_l \ge lcp_i$인 경우와 $T_l < lcp_i$인 경우로 나뉘게 된다. 
    • $T_l \ge lcp_i$인 경우를 생각해보면, 이제 $S_l = T_l$인 것으로 생각해도 무방하다는 것을 알 수 있다.
      • 그러므로, $S_l \leftarrow T_l$로 $S$를 바꾸고, $S$와 $T$를 하나로 합친다.
      • 여기서 합친다는 것은, $(T_{st}, S_{en}, S_l = T_l)$을 만든다는 것이다. 
      • 만약 여전히 $T_l > lcp_i$이면 다시 맨 처음부터 반복하면 된다.
      • 앞서 확인했듯이 $(st, en, l)$에 대응되는 suffix array 값들의 집합을 set으로 관리해야 한다. 
        • 이는 $S$에 대응되는 집합과 $T$에 대응되는 집합을 합치는 것과 같다. 그러니 small-to-large 하면 ok.
    • $T_l < lcp_i$인 경우, 이제 $S_l < lcp_i$인 경우와 같은 방식으로 대응하면 된다. 
  • $S_l = lcp_i$인 경우, 단순히 $S \leftarrow (S_{st}, i = S_{en} + 1, S_l)$으로 바꾸고 set을 관리하면 된다.
  • $S_l < lcp_i$인 경우, stack에 $(i-1, i, lcp_i)$를 push 하면 된다. 

모든 과정이 끝나면, stack에 원소들이 남을 것이며 $l$이 증가하는 순서일 것이다.

위 과정과 마찬가지로 pop하고 prefix들 handle 하고 스택의 다음 원소와 합치는 과정을 반복하면 답을 모두 구할 수 있다.

 

disjoint occurrence 계산을 naive 하게 할 수 있을 거라고 koosaga가 말해줬는데 안 믿은 게 문제다 ㅠㅠ 

엄청나게 어려운 자료구조를 관리해야 할 거라고 생각해서 망했다. 시간복잡도 증명이 매우 궁금한 문제.

 

꾸베릴과 알대인

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <stack>
#include <set>
using namespace std;
typedef long long int ll;
 
bool debug = false;
int ord[51111], nord[51111], cnt[51111], aux[51111];
int sfx[51111], rev[51111], lcp[51111];
string s;
int ans[51111]; 
int app[51111];
 
struct L {
    int len_com;
    int st; int en; int idx;
    L(int len_com, int st, int en, int idx): len_com(len_com), st(st), en(en), idx(idx) {}
};
 
int iidx = 0;
set<ll> VALUES[51111];
stack<L> stk;
 
void SFSA(string str) {
    int n = str.length();
    int p = 1;
    memset(ord, 0sizeof(ord));
    for(int i=0; i<n; i++){
        sfx[i] = i;
        ord[i] = str[i];
    }
    int pnt = 1;
    while(1) {
        memset(cnt, 0sizeof(cnt));
        for(int i=0; i<n; i++) cnt[ord[min(i+p, n)]]++;
        for(int i=1; i<=|| i<=255; i++) cnt[i] += cnt[i-1];
        for(int i=n-1; i>=0; i--)
        aux[--cnt[ord[min(i+p, n)]]] = i;
        memset(cnt, 0sizeof(cnt));
        for(int i=0; i<n; i++) cnt[ord[i]]++;
        for(int i=1; i<=|| i<=255; i++) cnt[i] += cnt[i-1];
        for(int i=n-1; i>=0; i--)
        sfx[--cnt[ord[aux[i]]]] = aux[i];
        if(pnt == n) break;
        pnt = 1;
        nord[sfx[0]] = 1;
        for(int i=1; i<n; i++){
            if(ord[sfx[i-1]] != ord[sfx[i]] || ord[sfx[i-1+ p] != ord[sfx[i] + p]){
            pnt++;
        }
        nord[sfx[i]] = pnt;
        }
        memcpy(ord, nord, sizeof(int* n);
        p *= 2;
    }
    for(int i=0; i<n; i++) rev[sfx[i]] = i;
    int h = 0;
    for(int i=0; i<n; i++){
        if(rev[i]){
            int prv = sfx[rev[i] - 1];
            while(str[prv + h] == str[i + h]) h++;
            lcp[rev[i]] = h;
        }
        h = max(h-10);
    }
}
 
int get_count(int idx, int jump) {
    int ret = 0;
    auto it = VALUES[idx].begin();
    while(it != VALUES[idx].end()) {
        ret += 1;
        it = VALUES[idx].lower_bound((*it) + jump);
    }
    return ret;
}
 
void printL(L S) {
    cout << "len_com: " << S.len_com << endl;
    cout << "st: " << S.st << endl;
    cout << "en: " << S.en << endl;
    cout << "idx: " << S.idx << endl;
}
 
void finish_handle(int upper_cut, L S) {
    if(S.len_com == 0return;
    if(debug) {
        cout << "finish_handle " << upper_cut << endl;
        printL(S);
    }
    int num_times = S.en - S.st + 1;
    int num_app = get_count(S.idx, upper_cut);
    if(num_app < app[num_times]) return;
    int l = upper_cut;
    int r = S.len_com;
    int best = upper_cut, mid;
    while(l <= r) {
        mid = (l + r) / 2;
        if(get_count(S.idx, mid) == num_app) {
            best = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    if(debug) {
        cout << "num_times: " << num_times << endl;
        cout << "num_app: " << num_app << endl;
        cout << "best: " << best << endl;
    }
    if(num_app > app[num_times]) {
        app[num_times] = num_app;
        ans[num_times] = best;
    }
    else if(num_app == app[num_times]) {
        ans[num_times] = max(ans[num_times], best);
    }
}
 
L merge(L S1, L S2) {
    int from, to;
    if(VALUES[S1.idx].size() < VALUES[S2.idx].size()) {
        from = S1.idx; to = S2.idx;
    }
    else {
        from = S2.idx; to = S1.idx;
    }
    int new_st = min(S1.st, S2.st);
    int new_en = max(S1.en, S2.en);
    int new_len = min(S1.len_com, S2.len_com);
    int new_idx = to;
    for(auto it = VALUES[from].begin() ; it != VALUES[from].end() ; it++) {
        VALUES[to].insert((*it));
    }
    return L(new_len, new_st, new_en, new_idx);
}
 
int main(void) {
    cin >> s; SFSA(s);
    ans[1= s.length();
    for(int i = 1 ; i < s.length() ; i++) {
        if(debug) cout << "on " << i << endl;
        while(!stk.empty() && lcp[i] < stk.top().len_com) {
            L S = stk.top(); stk.pop();
            int upper_cut = 0;
            if(stk.empty() || stk.top().len_com < lcp[i]) {
                upper_cut = lcp[i] + 1;
                finish_handle(upper_cut, S);
                stk.push(L(lcp[i], S.st, S.en, S.idx));
            }
            else {
                upper_cut = stk.top().len_com + 1;
                finish_handle(upper_cut, S);
                L S2 = stk.top(); stk.pop();
                L TT = merge(S2, S);
                stk.push(TT);
 
            }
        }
            
        if(stk.empty() || lcp[i] > stk.top().len_com) {
            iidx++;
            VALUES[iidx].insert(sfx[i-1]); VALUES[iidx].insert(sfx[i]);
            L Lv = L(lcp[i], i - 1, i, iidx);
            stk.push(Lv); continue;
        }
 
        if(!stk.empty() && stk.top().len_com == lcp[i]) {
            VALUES[stk.top().idx].insert(sfx[i]);
            L stk_top = stk.top(); stk.pop();
            stk.push(L(stk_top.len_com, stk_top.st, i, stk_top.idx));
        } 
    }
 
    while(!stk.empty()) {
        L S = stk.top(); stk.pop();
        int upper_cut = 1;
        if(!stk.empty()) { upper_cut = max(upper_cut, stk.top().len_com + 1); }
        finish_handle(upper_cut, S);
        if(!stk.empty()) {
            L S2 = stk.top(); stk.pop();
            L TT = merge(S2, S);
            stk.push(TT);
        }
    }
 
    for(int i = 1 ; i <= s.length() ; i++cout << ans[i] << " ";
    cout << endlreturn 0;    
}
 
cs

 

 

'PS > Problem Solving' 카테고리의 다른 글

10, 11월의 PS 일지 - Part 1  (0) 2020.11.08
8월의 PS 일지 - Part 6  (0) 2020.08.31
8월의 PS 일지 - Part 4  (0) 2020.08.12
8월의 PS 일지 - Part 2  (0) 2020.08.09
7월의 PS 일지 - Part 2  (0) 2020.08.04

SCPC 준비하려고 PS에 시간을 좀 넣었다. 그래서 CTF를 제대로 못함 :( 풀이는 시간이 없으니 최대한 간략하게.

SCPC 풀이 자체는 푼 것만 최종 결과가 나오면 올릴 것 같다. 시간이 난다면 ㅋㅋㅋㅋ


BOJ 18969 Different Summands Counting

BOJ 12961 체스판 2

2020 KAIST Mock ICPC

2018 NEERC Northern Subregional

BOJ 18908 Brackets

BOJ 16833 Enlarge Circles

2019 ICPC Danang Regional


'PS > Problem Solving' 카테고리의 다른 글

ACM-ICPC 2022 Seoul Regional H  (0) 2022.11.21
8월의 PS 일지 - Part 6  (0) 2020.08.31
8월의 PS 일지 - Part 4  (0) 2020.08.12
8월의 PS 일지 - Part 2  (0) 2020.08.09
7월의 PS 일지 - Part 2  (0) 2020.08.04

이제 개강 + SNUPC 검수 + CTF 정식입문 + 등등으로 PS 일지가 일시정지 될 것 같다.

대신 CTF write-up을 최대한 열심히 써보려고 한다. 팀에 들어갔으니 진짜 열심히 해보려고 한다 :)


BOJ 1910 Two Parties

Petrozavodsk 2018 Winter Day 8 : Saratov SU Contest

BOJ 11617 Export Estimate

BOJ 19281 Short Random Problem

BOJ 19579 물건 가져가기

BOJ 14460 Why Did the Cow Cross the Road III (Platinum)

BOJ 15756 Disruption

BOJ 17031 Moorio Kart

BOJ 18356 Movie-goer

BOJ 18358 Gluttons

BOJ 18360 Logistics

BOJ 19651 수열과 쿼리 39


'PS > Problem Solving' 카테고리의 다른 글

ACM-ICPC 2022 Seoul Regional H  (0) 2022.11.21
10, 11월의 PS 일지 - Part 1  (0) 2020.11.08
8월의 PS 일지 - Part 4  (0) 2020.08.12
8월의 PS 일지 - Part 2  (0) 2020.08.09
7월의 PS 일지 - Part 2  (0) 2020.08.04

BOJ 17678 합병

BOJ 18448 Best Subsequence

BOJ 8875 장난감 정리 로봇

BOJ 10846 발리의 조각상

BOJ 10848 팔렘방의 다리

BOJ 18664 Minimums on the Edges

BOJ 15986 마법 목걸이

BOJ 10717 성벽

BOJ 18196 정기 모임


'PS > Problem Solving' 카테고리의 다른 글

10, 11월의 PS 일지 - Part 1  (0) 2020.11.08
8월의 PS 일지 - Part 6  (0) 2020.08.31
8월의 PS 일지 - Part 2  (0) 2020.08.09
7월의 PS 일지 - Part 2  (0) 2020.08.04
7월의 PS 일지 - Part 1  (0) 2020.07.21

USACO 문제를 집중적으로 풀었다. JOI도 약간 풀었고, 다른 문제도 조금 풀었다.

문제의 개수가 워낙 많으니까 풀이는 웬만하면 간단하게 쓰려고 한다.


BOJ 16982 Growing Vegetables is Fun 3

BOJ 16983 Coin Collecting

BOJ 18433 Collecting Stamps 3

BOJ 8222 Distance

BOJ 11961 High Card Low Card Platinum

BOJ 11991 Fenced In Platinum

BOJ 11982 Angry Cows Gold

BOJ 16760 Balance Beam

BOJ 11992 Circular Barn Platinum

BOJ 17018 Redistricting

BOJ 14522 Modern Art Platinum

BOJ 18778 Equilateral Triangles

BOJ 14164 삼각형 영역

BOJ 14448 Subsequence Reversal

BOJ 18264 Moortal Combat

BOJ 18263 Milk Visits

BOJ 15743 New Barns

BOJ 18260 Bessie's Snow Cow

BOJ 18777 Delegation Platinum

BOJ 15585 Sprinklers

BOJ 18871 Sprinklers 2 : Return of the Alfalfa


'PS > Problem Solving' 카테고리의 다른 글

8월의 PS 일지 - Part 6  (0) 2020.08.31
8월의 PS 일지 - Part 4  (0) 2020.08.12
7월의 PS 일지 - Part 2  (0) 2020.08.04
7월의 PS 일지 - Part 1  (0) 2020.07.21
5월의 PS 일지 - Part 2  (9) 2020.06.06

7월 말 ~ 8월 초에서는 먼저 UCPC 예선, 본선이 있었다. 문제를 몇 개 안 풀어서 나중에 업솔빙을 할 생각이다.

SNUPS에서 SCPC 대비 스터디가 있어서, SCPC 예선 문제를 가능한만큼 밀었다. 본선은 추후에 진짜 대회처럼 돌아볼 생각이다.

그리고 친구들과 만나서 셋을 돌거나 개인적으로 셋을 돌고, 덤으로 그냥 지나가는 문제들을 몇 개 풀었다. 


BOJ 1624 데크소트

BOJ 19548 그건 망고가 아니라 고양이에요

Pacific Northwest Regional 2019 (Division 1)

Codeforces Educational Round 92

SCPC 1차 예선

SCPC 2차 예선


'PS > Problem Solving' 카테고리의 다른 글

8월의 PS 일지 - Part 4  (0) 2020.08.12
8월의 PS 일지 - Part 2  (0) 2020.08.09
7월의 PS 일지 - Part 1  (0) 2020.07.21
5월의 PS 일지 - Part 2  (9) 2020.06.06
4월의 PS 일지 - Part 3  (0) 2020.04.18

NERC 2019


Yokohama 2018


NWERC 2015


'PS > Problem Solving' 카테고리의 다른 글

8월의 PS 일지 - Part 2  (0) 2020.08.09
7월의 PS 일지 - Part 2  (0) 2020.08.04
5월의 PS 일지 - Part 2  (9) 2020.06.06
4월의 PS 일지 - Part 3  (0) 2020.04.18
4월의 PS 일지 - Part 2  (2) 2020.04.09

시험 때문에 PS를 못하고 있고, 그래도 Project Euler Eulerian 랭킹은 도전하고 있다. Top 10은 충분히 가능할 듯.

6월에 글을 쓰지만 푸는 것 자체는 전부 5월에 했으므로 5월의 일지로 치려고 한다.

방학이 되면 새로 올라온 Petrozavodsk 캠프 수학 문제를 몇 개 밀고, 근본 PS도 챙기려고 한다.

다행인지 아닌지는 모르겠지만 새로 올라온 문제 중에 재미있는 수학 문제는 몇 개 없는 것 같다.


BOJ 18928 Joy With Cookies

BOJ 18929 Knights of Round Table

BOJ 17644 Magic Tree

BOJ 17005 Knight of the Tarot Cards

BOJ 16892 레몬 주스 게임

BOJ 14704 타일 뒤집기 (Hard)

BOJ 18617 From Modular to Rational

BOJ 18763 Knowledge Oriented Problem (Ruby I)


'PS > Problem Solving' 카테고리의 다른 글

7월의 PS 일지 - Part 2  (0) 2020.08.04
7월의 PS 일지 - Part 1  (0) 2020.07.21
4월의 PS 일지 - Part 3  (0) 2020.04.18
4월의 PS 일지 - Part 2  (2) 2020.04.09
4월의 PS 일지 - Part 1  (0) 2020.04.06