https://codeforces.com/contest/1287
Dashboard - Codeforces Round #612 (Div. 2) - Codeforces
codeforces.com
아 ㅋㅋ
한 달 전의 내가 글 조금만 더 다듬고 올리려고 임시저장 해놨는데 그 후로 방치했다가 이제야 발견했다.
지금이라도 올려서 다행.
A.
A들 간의 간격 중 가장 큰 걸 구하면 된다.
근데 ('A'들 간의 인덱스 차 - 1)를 구해야 하는데 그냥 차이로 계산했다가 두 번 틀렸다. ㅠㅠ
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
string s; cin >> s;
int maxLen = 0;
int before = -1;
for (int i = 0; i < n; ++i) {
if (s[i] == 'A') {
if (before != -1 && i - before != 1) {
maxLen = max(maxLen, i - before - 1);
}
before = i;
}
}
if (before != -1 && before != n - 1) {
maxLen = max(maxLen, n - before - 1);
}
cout << maxLen << kEndl;
}
}
B.
n이 최대 1500이기 때문에 O(n^2) 풀이를 떠올리려고 했다.
카드 두 장을 고르고 나면 set을 만드는 데 필요한 카드의 종류는 유일하다는 걸 깨달았다.
그래서 카드 두 장을 골라서 모든 경우를 보는 데 n^2, 세 번째 카드를 만드는 데 k (k <= 30)의 시간이 소요되므로 O(n^2k)에 해결할 수 있다.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, k; cin >> n >> k;
vector<string> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
sort(arr.begin(), arr.end());
ll ans = 0;
for (int i = 0; i < n; ++i) {
const string& first = arr[i];
for (int j = i + 1; j < n; ++j) {
const string& second = arr[j];
string finding = "";
for (int idx = 0; idx < k; ++idx) {
if (first[idx] == second[idx]) {
finding += first[idx];
}
else {
const char& a = first[idx], b = second[idx];
if ((a == 'S' && b == 'E') || (a == 'E' && b == 'S')) {
finding += 'T';
}
else if ((a == 'E' && b == 'T') || (a == 'T' && b == 'E')) {
finding += 'S';
}
else {
finding += 'E';
}
}
}
if (binary_search(arr.begin() + j + 1, arr.end(), finding)) {
++ans;
}
}
}
cout << ans << kEndl;
}재밌는 점은
set의 세 번째 카드를 구하면서 카드의 특성이 모두 다른 경우를 처리할 때
저렇게 3!의 경우를 모두 고려하는 하드코딩으로 짜기가 싫어서 처음에는
map<char, bool> chk;
chk['S'] = chk['E'] = chk['T'] = false;
chk[first[idx]] = chk[second[idx]] = true;
for (auto iter = chk.begin(); iter != chk.end(); ++iter) {
if (iter->second == false) {
finding += iter->first;
break;
}
}이렇게 했다.
근데 TLE 뜨길래 혹시나 해서 저렇게 if문을 이용하는 방법으로 바꿨더니 맞음...
C.
(이 부분이 한 달 전의 내가 글을 올리기 전에 다듬으려고 했던 부분이다.
당시에는 설명에서 너무 모호한 게 많아 보여서 그랬던 건데 지금 보니까 이것도 나쁘지 않아서 그냥 그대로 올린다.)
그리디로 접근했다.
연속하는 0들에 대한 정보를 저장하고, 우선순위에 따라 정렬한 뒤, 최선의 경우로 채워나간다.
다양한 상황이 존재할 수 있는데, 그중에서 각각의 최선과 최악의 경우를 생각해보면 0 or 1 or 2만큼 증가한다.
그러므로 일단은 0이 될 수 있는 상황부터 해결하고, 그다음에는 1, 그다음에는 2.
0이 될 수 있는 상황: 양옆이 같고, 그 안을 채울 수 있을 만큼 수들이 남아있는 경우
1이 될 수 있는 상황: 양옆이 다른 상황. 이때는 사실상 이게 최악이면서도 최선임.
2가 되는 상황: 양 옆이 같고, 그 안을 채울 수 있을만큼 수가 없음.
0 뭉치가 양 끝에 있다면? -> 최선이면 0, 최악이면 1. 그렇지만 그냥 이건 맨 마지막에 고려해야 함. 한쪽만 신경 쓰면 되기 때문에, 다른 경우들에 대한 최선의 상태를 우선 만들어놓고, 여기를 처리하는 게 이득이다.
그래서 순서는
1. 양 끝이 같은 경우는 0 or 2이므로, 0들로 처리할 수 있는 것들을 많이 만들어야 함. 그래서 counting이 작은 순으로 오름차순 정렬한 거고.
2. 최선을 다해서, 양 끝이 같은 경우를 처리한다.
3. 처리가 불가능한 경우가 생기면, 그때부터는 개수를 고려할 필요가 없다. 어차피 그 사이에서 parity가 바뀌는 지점이 무조건 존재한다는 게 중요한 거기 때문에. 그 사이에 구체적인 개수는 알 필요 없고.
연속하는 0들의 정보는
- counting: 연속하는 0들의 개수 (default = 0)
- same: 양 끝의 수들의 parity가 같은지의 여부 (default = true)
- remainder: 만약 parity가 같다면 그 값이 무엇인지 (default = false)
- end: 연속하는 0이 수열의 끝에 위치하는지의 여부 (default = false)
그리고 이걸 저장하기 위해 structure를 선언했다.
struct Diff {
int counting;
bool same;
bool remainder;
bool end;
};
예를 들어
10
1 0 0 5 0 0 0 6 3 0
라는 인풋이 있으면
첫 번째 연속하는 0들은 counting = 2; same = true; remainder = true; end = false;
두 번째는 counting = 3; same = false; remainder = false; end = false;
세 번째는 counting = 1; same = true; remainder = false; end = true;
이런 식으로 저장된다.
그리고 이 정보를 저장한 벡터를 정렬했는데, 우선순위는
1. end == false
2. same == true
3. counting이 작은 순서
이다.
그리고 이제 차례대로 최선을 다해서 그리디하게 처리하면 된다. 이때 0을 채우는 데 현재 사용할 수 있는 짝수와 홀수의 개수를 저장해둬야 한다.
same == true이면서 그 구간을 동일한 parity의 수로 채울 수 있다면, 즉 짝수/홀수의 개수가 충분하다면 이때 사용한 짝수/홀수 개수를 차감하기만 하면 된다.
만약 개수가 충분하지 않다면 중간에 parity가 바뀌는 경우가 생기는데, 이때 만약 이 구간의 end == true라면 한 번, false라면 두 번 생긴다.
이후 same == false인 구간에 대해서는 parity가 무조건 한 번 바뀌고, 이 외 고려사항은 없다.
처음에 데이터를 처리할 때 end = true면 same = true로 설정했기 때문에 same == false이면서 end == true인 경우는 고려하지 않아도 된다.
struct Diff {
int counting;
bool same;
bool remainder;
bool end;
bool operator<(Diff comp) {
if (end != comp.end) {
return !end;
}
if (same == comp.same) {
return counting < comp.counting;
}
return same;
}
Diff() {};
Diff(int counting, bool same, bool remainder, bool end) {
this->counting = counting;
this->same = same;
this->remainder = remainder;
this->end = end;
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<int> arr(n);
vector<int> cnt(2);
cnt[0] = n / 2; cnt[1] = n / 2 + n % 2;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
if (arr[i] != 0) {
--cnt[arr[i] % 2];
}
}
vector<Diff> data;
int before = -1;
int ans = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] != 0) {
if (before == -1 && i != 0) {
data.push_back(Diff(i, true, arr[i] % 2, true));
}
else if (i != before + 1) {
data.push_back(Diff(i - before - 1, arr[i] % 2 == arr[before] % 2, arr[i] % 2, false));
}
before = i;
if (i - 1 >= 0 && arr[i - 1] != 0) {
ans += (arr[i] % 2 != arr[i - 1] % 2);
}
}
}
if (n == 1) {
cout << 0 << kEndl;
return 0;
}
if (before == -1) {
cout << 1 << kEndl;
return 0;
}
if (before != n - 1) {
data.push_back(Diff(n - before - 1, true, arr[before] % 2, true));
}
sort(data.begin(), data.end());
for (const Diff& diff : data) {
if (diff.same) {
if (diff.counting <= cnt[diff.remainder]) {
cnt[diff.remainder] -= diff.counting;
}
else {
if (diff.end) {
++ans;
}
else {
ans += 2;
}
}
}
else {
++ans;
}
}
cout << ans << kEndl;
}
그런데 알고보니 DP 문제였다.
ㅋㅋ!
문제 어렵게 풀기 장인.