Codeforces Round 1011 (Div. 2)
셋: https://codeforces.com/contest/2085
A. Serval and String Theory
$k=0$인 경우, $s$가 universal이기 위해서는 처음부터 original < reversed여야만 한다.
$s$가 한 종류의 문자로만 이루어져 있을 경우, 답은 항상 불가능이다.
그 외의 경우 항상 $s$를 universal하게 만들 수 있다. 양 끝 문자가 다르다면 그 둘을 swap하면 되고, 양 끝 문자가 같으면 다른 곳에서 문자를 하나 가져와 양 끝 문자 중 적절한 것과 swap하면 되기 때문이다.
int n, k;
string str;
cin>>n>>k>>str;
string rev = str;
reverse(all(rev));
if(rev > str || str[0]!=str[n-1] && k>0){
cout<<"YES\n";
}
else{
fors(i, 0, n-1){
if((str[0]<str[i] || str[n-1]>str[i]) && k>0){
cout<<"YES\n";
return;
}
}
cout<<"NO\n";
}B. Serval and Final MEX
약간의 케이스 분류 문제이다. 배열에 포함된 0의 개수 및 위치에 따라 casework를 해 주면 된다.
1. 만약 0이 단 한 개도 포함되어 있지 않다면 그냥 배열 전체를 mex하면 0을 만들 수 있다.
2. 배열의 양 끝 원소가 0이라면 배열을 반으로 나눠서 각각 mex한 다음에 둘을 합쳐서 다시 mex하면 0이 된다.
3. 그 외의 경우 0 전체를 포함하는 구간을 적절하게 잡아서 mex한 후, 나머지 수들과 mex하여 0을 만들 수 있다.
int n;
cin>>n;
vi arr(n);
forr(i, n) cin>>arr[i];
int cnt=0;
forr(i, n) if(arr[i]==0) cnt++;
if(cnt==0) cout<<"1\n1 "<<n<<endl;
else if(arr[0]==0 && arr[n-1]==0){
cout<<3<<endl;
cout<<n/2+1<<" "<<n<<endl;
cout<<1<<" "<<n/2<<endl;
cout<<"1 2\n";
}
else{
int st=0, en=n-1;
while(arr[st]!=0) st++;
while(arr[en]!=0) en--;
int l=st, r=en;
if(st==en){
if(l!=0) l--;
else if(r!=n-1) r++;
}
cout<<2<<endl;
cout<<l+1<<" "<<r+1<<endl;
cout<<1<<" "<<n-r+l<<endl;
}C. Serval and The Formula
우선 $A + B = A \oplus B$는 $A \& B = 0$과 동치이다. $A \oplus B = A + B - 2(A \& B)$이기 때문이다.
따라서 $(x+k) \& (y+k) = 0$이 되는 $k$를 찾아주면 되는데, $x=y$라면 당연히 그러한 $k$는 존재하지 않을 것이고, $x \neq y$라면 $k = 2^{40} - max(x, y)$가 답이 된다.
일반성을 잃지 않고 $x > y$라 두자. $x$에다 $k$를 더하여 $x+k$를 $2^n$ 꼴로 만들면, $x+k$의 $n+1$번째 비트는 1이 됨과 동시에 $n$번째 이하의 비트들은 모두 $0$이 된다.
이 때 $x > y$이므로 $y+k$는 많아봤자 $n$개의 비트를 가지고, 따라서 $(x+k) \& (y+k) = 0$이 된다.
int x, y;
cin>>x>>y;
if(x==y) cout<<-1<<endl;
else cout << (1LL<<40) - max(x, y) << endl;D. Serval and Kaitenzushi Buffet (Upsolved)
우선 최대로 먹을 수 있는 회전초밥 접시의 개수는 $\lfloor \frac{n}{k+1} \rfloor$개이다.
관찰 1) 회전초밥은 최대 개수로 먹는 것이 좋다.
최대 개수로 먹지 않은 해가 있을 때, 가장 일찍 선택할 수 있는 접시를 추가하여 먹을 수 있다.
따라서 먹을 회전초밥의 개수를 $\lfloor \frac{n}{k+1} \rfloor$로 고정시켜두고 생각해볼 수 있다.
관찰 2) 뒤에서부터 $i$번째 회전초밥 접시를 가져오려면, $n - (k+1)(i-1) - k$분 이전에 가져와야 한다.
그래야만 이후에 $i-1$개의 접시를 가져와 먹고, $i$번째 접시를 가져옴으로써 생긴 $k$개의 초밥을 먹을 수 있기 때문이다.
관찰 3) 뒤에서부터 $i$번째 접시를 $n - (k+1)(i-1) - k$분 이전에 가져오기만 하면, 항상 가져온 초밥을 전부 먹을 수 있다.
앞에서부터 그리디하게 생각해보면 당연하다.
따라서, 시간 순서대로 접시를 순회하면서, 현재 시각이 $n - (k+1)(i-1) - k$ 꼴이 될 때마다 지금까지 본 접시 중 가장 만족도가 높은 접시를 선택하는 그리디 알고리즘을 적용할 수 있다.
구현은 우선순위 큐를 이용한다.
int n, k, ans=0;
cin>>n>>k;
priority_queue<int> pq;
fors(i, 1, n){
int t;
cin>>t;
pq.push(t);
if((n-i+1) % (k+1) == 0){
ans += pq.top();
pq.pop();
}
}
cout<<ans<<endl;
잘한 점: C를 풀었다.
못한 점: A에서 말렸다. B 케이스워크에서 말렸다. 푼 세 문제 모두 구현 실수가 있었다. D에서 감도 못 잡았다. (...)