Atcoder Typical 90
Updated:
Categories: Problem Solving
Atcoder Typical 90 문제들을 풀면서 인상깊었던 문제들만을 정리해 놓을 생각이다.
005 - Restricted Digits
$c_1 \sim c_k$ 의 한 자리수들로 N자리 문자를 만들었을 때 B의 배수의 갯수를 구하는 문제
풀이
n이 무지막지하게 크므로 무조건 $log_2(n)$을 만들어야 한다.
처음에는 분할정복으로 sol(길이 n, 값 val) := n자리 수로 mod B 했을 때 val이 되도록 하는 수의 갯수
를 구해서 l과 r 로 반으로 나눠서 l의 값이 0~B-1 일 때 $l_val \times 10^r + r_val = val$ 이 나오도록 하는 r_val을 구해서 재귀적으로 해결한다고 생각했다.
이때 시간복잡도는 $O(log(n) B^2)$으로 통과할 수 있어 보이지만 n 값이 크기 때문에 map으로 관리해줘야 하고 이로 인해서 인지 시간초과가 났다.
결국 풀이를 보았는데 비슷하긴 하나 n을 $10^{18}$말고 최대 60자리의 이진수로 표현할 수 있다.
n은 $10^{18}$이긴 하지만 2진수로 표현하면 60자리이다.
이를 이용해 dp[i][j]
:= ($10^{2^i} * j$를 현재 c1~ck로 만들 수 있는 갯수) 를 의미한다.
이를 이용해 반복문으로 dp[0][c1~ck] = 1로 초기화해서 모든 반복문을 돌아보면 원하는 값을 구할 수 있다.
코드
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
#include <bits/stdc++.h>
#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, n) for(int i=0; i<n; ++i)
#define For1(i, n) for(int i=1; i<=n; ++i)
#define For2(i, a, b) for(int i=(a); i<=(b); ++i)
#define ft first
#define sd second
#define Get(i, v) get<i>(v)
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;
const int INF = numeric_limits<int>::max();
const ll LNF = numeric_limits<ll>::max();
const int logmxn = 62, mxn = 1e3+1;
const ll MOD = 1e9+7;
ll N;
int B, K;
ll dp[logmxn][mxn];
ll ans[logmxn][mxn];
int pow10[logmxn];
// a^b mod c
ll pow(ll a, ll b, ll c) {
ll res = 1;
while(b) {
if(b%2) res = (res * a) % c;
a = (a * a) % c;
b >>= 1;
}
return res;
}
void solve() {
memset(dp,0,sizeof dp);
memset(ans, 0, sizeof ans);
cin >> N >> B >> K;
while(K--) {
int x; cin >> x;
dp[0][x%B]++;
}
for(int i=0; i<logmxn; i++) {
pow10[i] = (int)pow(10LL, 1LL << i, B);
}
for(int i=0; i<logmxn-1; i++) {
for(int j=0; j<B; j++) {
for(int k=0; k<B; k++) {
int nxt = (j*pow10[i] + k) % B;
dp[i+1][nxt] += dp[i][j]*dp[i][k];
dp[i+1][nxt] %= MOD;
}
}
}
ans[0][0] = 1;
for(int i=0; i<logmxn-1; i++) {
if((N & (1LL<<i)) == 0) {
for(int j=0; j<B; j++) ans[i+1][j] = ans[i][j];
continue;
}
for(int j=0; j<B; j++) {
for(int k=0; k<B; k++) {
int nxt = (j*pow10[i] + k) % B;
ans[i+1][nxt] += ans[i][j] * dp[i][k];
ans[i+1][nxt] %= MOD;
}
}
}
cout << ans[logmxn-1][0] << endl;
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tc = 1;
// cin >> tc;
while(tc--) {
solve();
// cout << solve() << endl;
}
return 0;
}
006 - Smallest Subsequence
길이가 N인 문자열 S에서 길이가 K인 S의 부분열 중 사전순 가장 작은 것을 출력하는 문제. 여기서 부분열은 원래 문자열에서 0개 이상의 문자를 제거한 뒤 남은 문자의 순서대로 이어붙인 문자열을 뜻한다.
풀이1
처음에는 lis 알고리즘처럼 증가하는 부분수열을 찾을까 생각하다가 lis가 k보다 작다면 문제가 생겨서 포기했다.
그 다음에는 segment tree를 이용해서 풀어보았다.
- start ~ n-k 중에서 가장 작은 문자와 그 문자의 index를 구한다. 그리고 해당 문자를 ans의 끝에 추가해준다.
- 그 다음 start = index+1, k– 시키고 다시 1번을 반복한다.
- 이를 k가 0이 될 때까지 반복한다.
위와 같이 풀면, k개의 부분문자열 중 가장 사전 순으로 낮은 부분열을 구할 수 있다.
O(nlogn) 정도에 구할 수 있다.
코드1
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
#include <bits/stdc++.h>
#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, n) for(int i=0; i<n; ++i)
#define For1(i, n) for(int i=1; i<=n; ++i)
#define For2(i, a, b) for(int i=(a); i<=(b); ++i)
#define ft first
#define sd second
#define Get(i, v) get<i>(v)
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;
const int INF = numeric_limits<int>::max();
const ll LNF = numeric_limits<ll>::max();
class Segment {
public:
vector<pair<char,int>> tree; //tree[node] := a[start ~ end] 의 합
Segment() {}
Segment(int size) {
this->resize(size);
}
void resize(int size) {
size = (int) floor(log2(size)) + 2;
size = pow(2, size);
tree.resize(size, {numeric_limits<char>::max(), 0});
}
pair<char,int> sol(int node, int start, int end, int left, int right) {
if(right < start || end < left) return {numeric_limits<char>::max(), 0};
if(left <= start && end <= right) return tree[node];
return min(sol(node * 2, start, (start + end) / 2, left, right),
sol(node * 2 + 1, (start + end) / 2 + 1, end, left, right));
}
void update(int node, int start, int end, int index, char value) {
if(index < start || end < index) return;
if(start == end) tree[node] = {value,index};
else {
update(node * 2, start, (start + end) / 2, index, value);
update(node * 2 + 1, (start + end) / 2 + 1, end, index, value);
tree[node] = min(tree[2*node], tree[2*node+1]);
}
}
};
void solve() {
int n, k; cin >> n >> k;
string s; cin >> s;
Segment root(n);
for(int i=0; i<n; i++) {
root.update(1,0,n-1,i,s[i]);
}
string ans;
int start=0;
while(k) {
auto [c,i] = root.sol(1,0,n-1,start,n-k);
ans += c;
start = i+1;
k--;
}
cout << ans << endl;
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tc = 1;
// cin >> tc;
while(tc--) {
solve();
// cout << solve() << endl;
}
return 0;
}
풀이2
그 다음에 해설을 찾아보니 O(n)만에 해결할 수 있었다.
stack을 이용해서 풀이를 구하는 것이다. erase라는 변수를 0으로 초기화한다.
stack의 top보다 들어오는 문자가 더 사전순으로 작다면 지울 수 있을 때까지 삭제해준다. 하지만 여기서 지울 때마다 erase++를 해준다. 하지만 우리는 k개의 부분열을 만들어야 하므로 erase는 최대 n-k 까지 할 수 있다.
이를 이용해서 erase < n-k 일 동안만 stack을 오름차순으로 만들어주면 된다.
코드2
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
#include <bits/stdc++.h>
#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, n) for(int i=0; i<n; ++i)
#define For1(i, n) for(int i=1; i<=n; ++i)
#define For2(i, a, b) for(int i=(a); i<=(b); ++i)
#define ft first
#define sd second
#define Get(i, v) get<i>(v)
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;
const int INF = numeric_limits<int>::max();
const ll LNF = numeric_limits<ll>::max();
void solve() {
int n,k; cin >> n >> k;
string s; cin >> s;
int erase=0;
stack<char> st;
for(char c : s) {
while(!st.empty() && erase < n-k && st.top() > c) { st.pop(); erase++; }
st.push(c);
}
string ans;
while(!st.empty()) {
ans += st.top();
st.pop();
}
reverse(all(ans));
cout << ans.substr(0,k) << endl;
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tc = 1;
// cin >> tc;
while(tc--) {
solve();
// cout << solve() << endl;
}
return 0;
}
후기
stack 이 더 좋은 풀이인데 익숙한 segment부터 떠올렸다.
stack이나 two-pointer 같은 기법도 한 번 정리해서 쭉 밀어봐야 할 것 같다.
비슷한 문제로는 백준 2812 - 크게 만들기가 있다. 해당 문제는 3년 전에 stack으로 풀었는데 기억하지 못 한 걸 보니 재활이 필요한 듯 하다.
Leave a comment