Codeforces Round #739 (Div. 3)

https://codeforces.com/contest/1560

Dashboard - Codeforces Round #739 (Div. 3) - Codeforces

쉬운 셋이었으나......F1을 보고 F2풀이를 바로 찾았으나..... 노트북이 멈춰버렸다...... 도킹 스테이션을 사기엔 너무 비싸서 전력 공급이 안되는 허브에 어거지로 모니터 두대를 연결해서 썼던게 문제였다. 몇달간 문제가 없어서 그냥 썼는데 하필 코포 중에 이게 터져버렸다........ F2 풀이 찾고 블루까지 바로가는 상상을 했는데 마음이 아프다.

---

A. Dislikes or Threes

Tag : Brute Force

 

풀이

조금 생각해보면 $K=1000$일 때 $10000$정도에 가까이 있겠다라고 생각해서 나이브를 짰고 시작 후 1분만에 맞았다. 이때 찐렌지 퍼포가 잠깐 떴는데 캡쳐할걸 그랬다. 시간복잡도의 C는 대충 작은 상수다.

 

시간복잡도 : $O(10000\ast C)$ 

 

전체 코드 

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
 
void solve(){
    int k;cin>>k;
    int c=0;
    for(int i=1;;i++){
        if(i%10 != 3 and i%3) c++;
        if(c==k) return cout<<i<<endl,void();
    }
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
}

---

B. Who's Opposite?

Tag : Math

 

풀이

$B-A$는 정$n$각형의 $\frac{n}{2}$가 되고 $(C-1+(B-A-2)mod(2\ast (B-A)))+1$을 하면 $C$의 반대 점이 나오게 되고 이제 $A,B,C$가 범위에 맞는지 체크하면 된다.

 

시간복잡도 : $O(1)$ 

 

전체 코드 

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
 
void solve(){
    ll a, b, c; cin >> a >> b >> c;
    a--,b--,c--;
    ll p=max(b,a)-min(b,a);
    if(c>2*p-1 or b>2*p-1 or a>2*p-1 or p<=1) cout<<-1<<endl;
    else cout<<(c+p)%(2*p)+1<<endl;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
}

---

D. Make a Power of Two

Tag : Brute Force, Greedy, Math

 

풀이

$A,B,C$번에서 무지성 완전탐색이 되는 것들만 나와서 $D$는 제한도 잘 읽지않고 무작정 나이브 다익스트라를 짰다....다짜고 제출하기 직전에 제한을 확인했고 급하게 다시 풀이를 구상했다. 오른쪽에만 더할 수 있는 것을 망각하고 $LCS$를 짜서 제출하기 직전 예제를 보고 다시 구상..... 예제에 $LCS$로 안풀리는 것이 있어서 다행이었다. 그리고 마지막으로 정해를 짜게됐다. 이렇게 덜렁대면서 문제를 푼 탓에 1시간 10분을 이 쉬운 문제 하나에만 소비했다. 

 

정해는 간단하다. 모든 2의 제곱수들을 순회하며 2의 0번부터 시작하는 substring의 최대길이를 구해주면 몇개를 지워야하고 몇개를 더해야하는지 쉽게 구할 수 있다.

 

시간복잡도 : $O(lo{g}^2({10}^{18}))$

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
	string a; cin >> a;
	int ans = 1e9;
	for(long long int i=1; i<=1e18; i*=2){
		string b = to_string(i);
		int p=0,q=0;
		for(int k=0; k<a.size(); k++){
			if(q<b.size() and a[k]==b[q]) q++; 	
		}
		int t = (int)a.size() - q + (int)b.size()-q;
		ans = min(ans, t);
	}	
	cout << ans << endl;
}
 
int main(){
	int t; cin >> t;
	while(t--){
		solve();
	}
}

---

E. Polycarp and String Transformation

Tag : Greedy, Math

 

풀이

일단 입력된 문자열 $S$를 뒤집으면 각 알파벳이 처음 나타나는 순서의 역순이 알파벳을 삭제하는 순서다. 

그리고 $a$를 $i$번째에 삭제한다면 전체 배열에는 $($원본 문자열의 $a$ 개수$)\ast i$개의 $a$가 존재할 것이다. 이것을 모든 알파벳에 돌려주면 원본 문자열의 길이를 얻을 수 있고, $S.substr(0,len)$으로 원본 문자열을 뽑을 수 있다. 이제 원본 문자열이 나왔으니 이것을 기준으로 다시 입력된대로 시뮬레이션해주며 불가능한 것을 판단해주면된다.

 

시간복잡도 : $O(|S|log|S|)$

 

전체 코드

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
 
void solve(){
    string s;cin>>s;
    reverse(all(s));
    map<char,int>mp,idx;
    set<char>st;string ans;
    for(auto&i:s){
        if(st.find(i)==st.end())ans+=i,idx[i]=ans.size();
        st.insert(i);mp[i]++;
    }
    for(auto&[i,j]:idx)j=st.size()+1-j;
    reverse(all(ans));
    int sz=0;
    for(auto&[c,i]:idx){
        if(mp[c]%i)return cout<<-1<<endl,void();
        sz+=mp[c]/i;
    }
    reverse(all(s));string t=s.substr(0,sz);
    pair<string,string>a={t,ans};
    map<char,int>chk;
    deque<char>dq;for(auto&i:s)dq.pb(i);
    for(int i=0;i<ans.size();i++){
        deque<char>q;for(auto&k:t)if(chk[k]==0)q.pb(k);
        while(q.size() and dq.size()){
            if(dq.size()==0)return cout<<-1<<endl,void();
            if(dq.front()!=q.front())return cout<<-1<<endl,void();
            dq.pop_front();q.pop_front();
        }
        chk[ans[i]]=1;
    }
    if(dq.size())return cout<<-1<<endl,void();
    cout<<a.fi<<' '<<a.se<<endl;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
}

---

F1,F2. Nearest Beautiful Number

Tag : Digit DP

 

풀이

전형적인 자릿수 $Dp$다. 각 자릿수마다 아직 $K$개의 수를 선택하지 않았다면 $0$부터 $9$까지의 수 중 현재 자리로 놓았을 때 답을 만드는 것이 가능한 최소를 현재 자리로 놓아준다. $K$개를 모두 선택했다면 이것도 고른 것 중 가능한 최소를 고르면 된다. $F$번 두개가 이렇게 쉬운건 말이 안된다.....아무리 div3여도...

 

시간복잡도 : $O(Klog|S|)$

 

전체 코드

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()),((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
using namespace std;
using ll = long long;
 
ll get(string s){
    if(s.size()==0)return 0;
    else return stol(s);
}
 
void solve(){
    ll n,k;cin>>n>>k;
    string s=to_string(n);
    set<int> st;
    string t="";
    for(int i=0;i<s.size();i++){
        if(st.size()==k){
            for(auto &p:st){
                string tmp=t;
                tmp+=(char)(p+'0');
                tmp+=string(s.size()-i-1,(char)(*prev(st.end())+'0'));
                if(get(tmp)>=n){t+=(char)(p+'0');break;}
            }
        } else {
            for(int p=i==0?1:0;p<=9;p++){
                int c=st.find(p)!=st.end();
                st.insert(p);
                string tmp=t;
                tmp+=(char)(p+'0');
                tmp+=string(s.size()-i-1,st.size()==k?(char)(*prev(st.end())+'0'):'9');
                if(get(tmp)>=n){t+=(char)(p+'0');break;}
                else if(!c) st.erase(p);
            }
        }
    }
    cout<<t<<endl;
}
 
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
}