tony9402
[Codeforces] Round #739 (Div.3) 본문
(소스코드 중요 부분만 있습니다.)
A. Dislike of Threes
Tag : 구현
Time Complexity : 전처리 $O(1666)$, 테스트 케이스 당 $O(1)$
3으로 떨어지는 수와 수의 일의 자리에 있는 숫자가 3인 경우를 제외한 나머지의 개수를 세면 된다.
입력으로 주어지는 수의 범위는 1000까지이므로 수가 1000개 뽑힐때까지 전처리하면 된다. (전처리 안 해도 충분히 돈다.)
vector<int> v;
bool chk(int x) {
if(x % 3 == 0) return false;
x %= 10;
if(x == 3) return false;
return true;
}
int main(){
fastio<>();
for(int i = 1, cnt = 0; cnt < 1000; i++) {
if(chk(i)) {
cnt ++;
v.push_back(i);
}
}
int t;cin >> t;
while(t--){
int k ;cin >> k;
cout << v[k - 1] << '\n';
}
return 0;
}
B. Who's Opposite?
Tag : 수학
Time Complexity : 테스트케이스 당 $O(1)$
1부터 $N$($N$은 짝수)까지의 번호가 원 위에 시계방향으로 존재한다. 간단한 규칙을 찾으면 되는 문제이다.
문제를 요약해보면 주어지는 입력을 보면 $a, b, c$가 주어지는데 a와 b는 서로 마주 보고 있을 때, $c$가 마주 보고 있는 것은 몇 번인지 구하는 문제이다.
a, b를 정보를 가지고 아래 식을 통해 N을 알 수 있다.
$N$ = $| a - b |$ * 2
숫자의 번호는 1부터 N까지 존재해야하므로 $a, b, c$가 1 ≤ $a, b, c$ ≤ N인지 확인한다.$c$가 마주보고 있는 수는 ($c$ + | $a$ - $b$ | - 1) % $N$ + 1로 구할 수 있다.
int main(){
fastio<>();
int t;cin >> t;
while(t--){
int a, b, c; cin >> a >> b >> c;
if(a < b) swap(a, b);
int d = a - b;
int last = d * 2;
if(d < b || last < c) cout << -1 << '\n';
else {
if(last < d + c) cout << d + c - last << ln;
else cout << d + c << ln;
}
}
return 0;
}
C. Infinity Table
Tag : 수학, 구현
Time Complexity : 테스트 케이스 당 $O(log k)$
문제에 있는 그림을 보면 (1, 1), (2, 1), (3, 1)는 제곱수인 것을 쉽게 알 수 있다. $k$보다 크거나 같은 수 중 가장 작은 제곱수를 찾고 계산을 해주면 쉽게 풀 수 있다.
int main(){
fastio<>();
int t;cin >> t;
while(t--){
int k; cin >> k;
int c = 1;
for(c = 1; 1LL * c * c < k; c++);
int cnt = c * c - (c - 1) * (c - 1);
int dis = k - (c - 1) * (c - 1) - 1;
int mid = (cnt - 1) / 2;
int y = 1, x = c;
if(dis <= mid) {
y += dis;
}
else {
y += mid;
dis -= mid;
x -= dis;
}
cout << y << ' ' << x << '\n';
}
return 0;
}
D. Make a Power of Two
Tag : 완전탐색, 문자열
Time Complexity : 테스트 케이스 당 $O(log k)$
수가 주어지는데 두 가지 연산이 있다.
- 수를 이루고 있는 숫자들 중에 하나를 골라 삭제한다.
- 수의 맨 오른쪽에 하나의 숫자를 추가한다.
두 가지 연산을 통해 주어진 수를 $2^k$로 만들 때 연산의 최소 횟수를 구하는 문제이다.
1번 연산할 때 조심해야하는게 있다. 수 301에서 숫자 3을 지운다고 하면 1이 되는 게 아니라 01이 된다. 따라서, 이를 문자열로 처리하면 편하다.
$2^k$로 구성된 수를 보면 k가 0부터 62까지 총 63개로 바꾸는 횟수를 구하고 이 중에 최솟값을 구하면 된다. 바꾸는 횟수를 구하는 건 간단하니 설명은 생략한다.
int cal(const string &a, const string &b) {
int i = 0, r = 0, ret = 0;
for(;i<siz(a)&&r<siz(b);i++) {
if(a[i] == b[r]) r++;
else ret++;
}
return siz(a) - i + ret + siz(b) - r;
}
int main(){
fastio<>();
int t;cin >> t;
while(t--){
int N; cin >> N;
int ans = INT_MAX;
string s = to_string(N);
for(int i = 0; i < 63; i++) {
ans = min(ans, cal(s, to_string(1LL << i)));
}
cout << ans << ln;
}
return 0;
}
E. Polycarp and String Transformation
Tag : 구현, 문자열, 시뮬레이션
Time Complexity : 테스트 케이스 당 $O(s)$
문제 지문에 있는 설명대로 문자열을 처리한 결과가 입력으로 주어진다.
어떤 순서로 문자를 지웠는지는 매우 쉽게 알 수 있다. 입력으로 주어진 문자열을 s라고 해보자. 문자열 s의 맨 뒤부터보면서 최초로 나온 문자열들을 모아서 다시 뒤집어주면 문자를 지운 순서를 알 수 있다.
abacabaaacaac 문자열 본다면 맨 뒤부터 최초로 나온 문자열을 나열해보면 cab가 된다. 이를 뒤집으면 bac로 문자를 지운 순서이다.
이제 abacabaaacaac 이 문자열이 어떤 문자열로부터 만들어졌는지 뽑아야한다. 그 어떤 문자열을 x라 하자. 문자열 x를 뽑는 방법은 아래와 같다. 아래 식을 이용해서 구할 수 있다.
주어진 문자열 s에 있는 알파벳의 개수 (s_cnt) = 문자열 x에 있는 알파벳의 개수 (x_cnt) * 해당 알파벳을 지운 index (e)
| index(오른쪽) | 1 | 2 | 3 |
| 지울 문자 | b | a | c |
| 지우기 전 문자열 | abacaba | aacaa | c |
| 알파벳 개수 | (a, b, c) = (4, 2, 1) | (a, b, c) = (4, 0, 1) | (a, b, c) = (0, 0, 1) |
주어진 문자열 abacabaaacaac에서 알파벳 개수를 구해보면 (a, b, c) = (8, 2, 3)이다. 알파벳이 지워지는 순서는 (a, b, c) = (2, 1, 3)이다. 위에 있는 식을 이용하면 문자열 x에 있는 알파벳의 개수를 구할 수 있다. 식에 적용하여 알파벳의 개수를 구해보면 (a, b, c) = (4, 2, 1)로 주어진 문자열 s에서 길이가 4 + 2 + 1 = 7인 것을 알 수 있다.
문자열 x를 뽑았으니, 문자를 지울 순서를 기반으로 다시 시뮬레이션 돌려 주어진 문자열 s랑 같은지 확인하면 된다.
-1을 출력하는 경우는 두 가지가 있다.
- 위에 식에서 s_cnt을 e으로 나눈 나머지가 0이 아닌 경우
- 문자열 x에서 시뮬레이션 돌렸더니 문자열 s랑 다른 경우
int main(){
fastio<>();
int t;cin >> t;
while(t--){
string s; cin >> s;
int index[27] = { };
string e;
for(int i = 0; i < 26; i++) index[i] = -1;
for(int i = siz(s) - 1; i >= 0; i--) {
int x = s[i] - 'a';
if(index[x] != -1) continue;
index[x] = i;
e += s[i];
}
int cnt[27] = {}, total = 0;
for(char ch : s) cnt[ch - 'a'] ++;
for(int i = 0; i < 26; i++) total += !!cnt[i];
int l = 0, len = 0;
bool answer = true;
for(char ch : e) {
if(cnt[ch - 'a'] % (siz(e) - l)) answer = false;
len += cnt[ch - 'a'] / (siz(e) - l);
l++;
}
if(!answer) {
cout << -1 << ln;
continue;
}
string L = s.substr(0, len);
string res = L;
reverseall(e);
vector<int> used(L.size());
for(int i = 0; i < siz(e); i++) {
string cur;
for(int j = 0; j < siz(L); j++) {
if(e[i] == L[j]) used[j]=1;
if(!used[j]) cur+=L[j];
}
res+=cur;
}
if(res!=s)cout << -1 << ln;
else cout << L << " " << e << ln;
}
return 0;
}
F1. Nearest Beautiful Number (easy version)
F2. Nearest Beautiful Number (hard version)
Tag : 그리디, 완전탐색
Time Complexity : 테스트 케이스 당 $O(10*10*log 10)$
hard version을 풀면 easy version을 그냥 풀 수 있다.
문제를 요약하자면, $N$보다 크거나 같은 수에서 최대 $K$가지 숫자로 구성된 수들의 최소를 구하는 것이다.
주어지는 수의 길이가 $L$이라 했을 때, 찾아야 하는 수의 길이는 반드시 $L$인 것을 쉽게 알 수 있다.
따라서, 맨 앞에 숫자를 0부터 9까지 둘 수 있는지, 사용한 숫자의 가짓수가 몇인지 체크하면서 선택하면 된다.
여기서 조심해야할 것은, 수의 맨 앞에 0이 올 수 없으므로, 1부터 보도록 하면 된다.
int main(){
fastio<>();
int t;cin >> t;
ll pw[11] = {1};
ll prefix[11] = { 0 };
for(int i = 1; i <= 10; i++) pw[i] = pw[i - 1] * 10;
for(int i = 1; i <= 10; i++) prefix[i] = prefix[i - 1] + pw[i - 1];
while(t--){
set<int> st;
ll N, K; cin >> N >> K;
int cnt = 0;
while(pw[cnt] <= N) cnt ++;
int ans = 0;
for(int i = cnt - 1; i >= 0; i--) {
for(int j = 0; j <= 9; j++) {
if((int)st.size() < K) {
bool exist = st.count(j); st.insert(j);
int mx = (int)st.size() == K ? *st.rbegin() : 9;
if(ans + pw[i] * j + prefix[i] * mx < N) {
if(!exist)st.erase(j);
continue;
}
}
else {
if(st.count(j)) {
if(ans + pw[i] * j + prefix[i] ** st.rbegin() < N) continue;
}
else continue;
}
ans += pw[i] * j;
break;
}
}
cout << ans << ln;
}
return 0;
}'알고리즘 > Codeforces' 카테고리의 다른 글
| Codeforces 1000 ~ 1400 set 2 (0) | 2020.08.12 |
|---|---|
| Codeforces 1000 ~ 1400 set 1 (0) | 2020.08.12 |
| 코드포스 - Codeforces Round #634 (Div. 3) (0) | 2020.04.15 |
| 코드포스 - Codeforces Round #544 (Div. 3) (0) | 2019.03.10 |
| 코드포스 - Educational Codeforces 49 Round (0) | 2018.08.19 |