Codeforces Round 700(Div.2) A~D1
A. Yet Another String Game
영어 소문자로 이루어진 한 문자열을 가지고 둘이 번갈아가면서 문자열의 한 글자씩을 바꾼다. 한 명은 문자열이 사전순으로 최대한 앞쪽으로 오게 만들려고 하고 한 명은 문자열이 사전순으로 최대한 뒤쪽으로 가게 만들려고 한다. 그러면 한 명은 자기가 고른 문자를 'a'로 바꾸려고 할 것이고 다른 한 명은 무조건 'z' 로 바꾸려고 할 것이다. 그런데 기존 문자가 a나 z일 수 있으므로 그런 경우 각각 b,y로 바꿔줘야 한다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int tc;
cin >> tc;
for (int z = 0; z < tc; z++) {
char s[55];
cin >> s;
int len = strlen(s);
for (int i = 0; i < len; i++) {
if (i % 2 == 0) { //alice
if (s[i] == 'a') { s[i] = 'b'; }
else { s[i] = 'a'; }
}
else {
if (s[i] == 'z') { s[i] = 'y'; }
else { s[i] = 'z'; }
}
}
cout << s << "\n";
}
return 0;
}
B. The Great Hero
영웅이 모든 몬스터를 처리할 수 있으면 YES, 아니면 NO다. 이때 몬스터의 수가 10만 이하이므로 하나하나 따져주면 된다. 몬스터의 체력과 영웅의 공격력을 비교해서 몇 번 공격해야 몬스터가 죽을지 따져주고, 그 공격 횟수만큼 영웅도 공격받는 걸 계산해 주면 된다. 그런데 유의할 점은, 영웅이 모든 몬스터를 처리한 후 죽는다 해도 똑같이 YES를 출력해 줘야 한다는 것이다. 이 말을 변형하면, 마지막 공격 한번은 영웅이 맞고 죽어도 된다. 그 마지막 공격은 몬스터들 중 가장 높은 공격력으로 하는 게 가장 이득이다. 마지막 공격을 제외한 다른 공격들은 영웅이 공격을 당한 후에도 살아 있어야 하기 때문이다.
풀이로 그대로 옮기면, 먼저 몬스터들이 영웅에게 주는 데미지를 다 계산해서 영웅의 체력에서 빼준다. 그리고 영웅이 마지막으로 맞아야 하는 공격을 계산하기 위해 몬스터들의 공격력들 중 가장 큰 것을 따로 계산해 준다. 그리고 그 공격 한 번은 무효로 돌려준다. 그 과정이 끝난 후의 영웅의 체력이 0보다 크면 YES이다. 즉 모든 몬스터를 처치할 수 있다. 그게 아니면 NO를 출력한다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
ll max(ll a, ll b) {
return a > b ? a : b;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int tc;
cin >> tc;
for (int z = 0; z < tc; z++) {
ll A, B, n;
cin >> A >> B >> n;
ll a[100005], b[100005];
ll max_attack = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
max_attack = max(max_attack, a[i]);
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
for (int i = 1; i <= n; i++) {
ll attack_num = b[i] / A;
if (b[i] % A != 0) { attack_num++; }
B -= a[i] * attack_num;
}
B += max_attack; //마지막 1번의 공격
if (B > 0) { cout << "YES\n"; }
else { cout << "NO\n"; }
}
return 0;
}
C. Searching Local Minimum
interactive하게 local minimum(양옆 원소보다 작은 원소)을 찾으면 된다. 이분탐색을 이용해서 구간을 계속 줄여나가면 되는 것이다. 문제에는 100번 미만의 쿼리를 사용하라고 되어 있지만 배열의 크기가 10만 정도이므로 이분탐색을 이용하면 아주 여유롭게 100번 훨씬 미만으로 끝난다.
사실 문제를 읽어보면 이분탐색을 쉽게 떠올릴 수 있겠지만, 어떤 식으로 구간을 줄여나갈지에 대한 아이디어가 부족하기 쉬운 문제였다. 나는 물론 대회 시간 내에 풀지 못했다..
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
int n, arr[100005];
void query(int x) {
if (1 <= x && x <= n) {
cout << "? " << x << "\n";
cout.flush();
cin >> arr[x];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
arr[0] = 1000000000; arr[n + 1] = 1000000000;
int low = 1, high = n;
while (low < high) {
int mid = (low + high) / 2;
query(mid); query(mid + 1);
if (arr[mid] < arr[mid + 1]) {
high = mid;
}
else { //mid 원소 >= mid+1 원소
low = mid + 1;
}
}
cout << "! " << low << "\n";
cout.flush();
return 0;
}
D1. Painting the Array I
- Geothermal의 아이디어를 보고 업솔빙하였다
배열의 원소들을 a그룹, b그룹에 차례로 넣었을 때 seg(a)+seg(b)(이 정의는 문제 참고) 를 최대화하는 문제이다. 세그먼트 트리를 이용해서 관리하는 dp로도 풀 수 있다고 하는데 나는 dp로 풀었다기에는 좀 부족하고, 배열의 i인덱스를 볼 때 a,b그룹의 마지막 원소가 무엇인지를 따로 저장해 두었다.
배열의 임의의 인덱스 idx의 원소를 x(==arr[idx])라 하고 이를 a,b그룹 중 하나에 넣는다고 할 때, 경우를 나눠서 생각할 수 있다. 이때 seg(a)+seg(b)는 n보다 절대 클 수는 없으므로 먼저 배열의 크기 n에서 시작해서 이를 이용해 풀이를 진행한다. ans=n 으로 해두고 경우에 따라서 ans를 줄여나가자.
a,b그룹의 마지막 원소가 둘 다(이는 dp[idx-1]에 저장되어 있다) x와 같은 경우, x를 어디에 넣느냐에 상관없이 seg(a)+seg(b) 를 늘릴 수 없다. 따라서 ans를 1 줄인다. 이걸 제외한 경우에는 언제든지 seg(a)+seg(b)를 1 늘릴 수 있으므로 ans를 줄일 필요가 없다.
그리고 배열에서 arr[idx]와 arr[idx-1]이 같을 경우, a,b그룹 둘 모두의 마지막에 arr[idx]가 들어가게 된다. 따라서 dp[idx]를 arr[idx]로 업데이트해준다.
또 위와 달리 arr[idx]!=arr[idx-1] 이고 arr[idx]==arr[idx-2]일 경우, arr[idx-2], arr[idx-1], arr[idx] 가 모두 어떤 그룹에든 연속하게 들어가서 각각 seg(a)+seg(b)를 늘릴 수 있다. 그 세 원소 모두가 한 그룹에 들어가므로 a,b 어디로 들어가든 그 마지막 원소는 유지되고 따라서 dp[idx]는 dp[idx-2]와 같다.
이걸 모든 idx에 대해 계산해 주면 ans를 최대한으로 만들 수 있다.
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
int ans = n;
int arr[100005], dp[100005] = { 0 };
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
for (int i = 1; i <= n; i++) {
if (i > 1 && arr[i] == dp[i - 1]) {
ans--;
}
if (i > 1 && arr[i] == arr[i - 1]) {
dp[i] = arr[i];
}
else if (i > 2 && arr[i] == arr[i - 2]) {
dp[i] = dp[i - 2];
}
}
cout << ans << "\n";
return 0;
}