배치 첫판
살면서 처음으로 코드포스 컨테스트를 참가했다.
레이팅 1600 미만을 대상으로 하는 Div3였다.
순위는 ACM-ICPC 스타일로 매기기 때문에 맞힌 문제 개수로 순위가 매겨지고 동점자는 패널티가 작을 수록 순위가 높아진다.
이번에는 7문제를 풀었고 전체 순위는 460위, 레이팅 대상 중에는 147위를 했다.
레이팅은 672점이 올랐는데, 처음에는 500점을 기본으로 주니까 실제로는 172점이 오른 셈이다.
문제 난이도가 전체적으로 낮았고, 대부분 그리디였기 때문에 거의 편하게 풀었다.
A. Problemsolving Log
https://codeforces.com/contest/1914/problem/A
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <string>
using namespace std;
int table[256];
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int x = 0; x < T; x++) {
int t;
cin >> t;
string s;
cin >> s;
fill(&table[0], &table[256], 0);
for (int i = 0; i < t; i++) {
table[s[i]]++;
}
int res = 0;
for (int i = 0; i < 26; i++) {
if (table['A' + i] > i) {
res++;
}
}
cout << res << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/A는 각각 알파벳 대문자 하나가 대응되는 문제가 있고, 입력으로 주어진 문자열에 그 문자가 나온 횟수만큼 생각할 때 총 몇 문제를 풀 수 있는지를 출력하는 문제이다.
각 문자가 등장한 횟수를 셀 테이블을 만들고, 문자열 전체를 탐색하면서 해당되는 문자를 +1 해주고, 마지막에 26문제에 대해 맞은 문제를 세주면 풀린다.
단순 구현 문제라 거의 바로 풀었다.
B. Preparing for the Contest
https://codeforces.com/contest/1914/problem/B
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int n, k;
cin >> n >> k;
// k + 1 sequence [n - k, n]
for (int i = n - k; i <= n; i++) {
cout << i << " ";
}
// remainder
for (int i = n - k - 1; i >= 1; i--) {
cout << i << " ";
}
cout << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/B는 1부터 N까지의 자연수로 이루어진 길이 N짜리 순열 중에서 증가하는 부분이 정확히 K개인 순열을 출력하는 문제이다.
항상 조건에 맞는 무언가를 출력하는 문제에서는 가장 단순한 답을 출력하는 쪽으로 설계했고, 앞에서부터 K+1개는 증가하고 이후로는 감소하도록 출력하면 정답이다. 이때, 증가하는 부분의 마지막을 N으로 설정해야 간단히 짤 수 있다.
처음에 증가하는 부분 개수가 아니라 LIS로 보고 제출했다가 한번 틀려서, AC를 받은 시간이 약간 늦다.
C. Quests
https://codeforces.com/contest/1914/problem/C
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int A[200000];
int B[200000];
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> A[i];
}
for (int i = 0; i < n; i++) {
cin >> B[i];
}
long long int res = 0;
long long int curr = 0; // sum of A to here
long long int Bmax = 0;
for (int i = 0; i < n; i++) {
// used i + 1 times to reach here
if (i >= k) {
break;
}
curr += A[i];
Bmax = max(Bmax, (long long int)B[i]);
// remaining k is k - i - 1
res = max(res, curr + Bmax * (k - i - 1));
}
cout << res << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/C는 최대 이득을 보도록 퀘스트를 선택하는 최적화 문제이다. k개의 퀘스트를 선택할 때, a에 사용하는 횟수와 b에 사용하는 횟수로 나누어 생각할 수 있다. a는 그냥 순서대로 선택하고, b는 현재 선택된 a와 대응되는 b중에서 최대값만 선택하면 된다.
a는 1개에서 min(n, k) 개까지 선택할 수 있고, a에서 선택하는 개수가 정해지면 b에서 선택하는 개수도 정해진다.
각 구간을 구할 때는 naive하게 풀면 구간 길이만큼의 연산 (+, max)가 필요하므로 O(n^2)시간이 소요된다.
이때 i-1구간을 구했을 때의 a합과 b최대값을 저장해놓으면 i구간에서는 덧셈 한번과 max연산 한번이면 새로운 a합과 b최대값이 구해지기 때문에 O(n)시간에 풀 수 있다.
D. Three Activities
https://codeforces.com/contest/1914/problem/D
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
class Bests {
public:
int v1 = -1, i1;
int v2 = -1, i2;
int v3 = -1, i3;
pair<int, int> Get(int n) {
if (n == 0) {
return make_pair(v1, i1);
}
if (n == 1) {
return make_pair(v2, i2);
}
if (n == 2) {
return make_pair(v3, i3);
}
}
void Insert(int v, int i) {
if (v1 < v) {
swap(v1, v);
swap(i1, i);
}
if (v2 < v) {
swap(v2, v);
swap(i2, i);
}
if (v3 < v) {
swap(v3, v);
swap(i3, i);
}
}
};
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int t = 0; t < T; t++) {
Bests a, b, c;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int v;
cin >> v;
a.Insert(v, i);
}
for (int i = 0; i < n; i++) {
int v;
cin >> v;
b.Insert(v, i);
}
for (int i = 0; i < n; i++) {
int v;
cin >> v;
c.Insert(v, i);
}
long long int res = 0;
long long int curr;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
auto A = a.Get(i);
auto B = b.Get(j);
auto C = c.Get(k);
if (A.second != B.second && B.second != C.second && A.second != C.second) {
curr = A.first;
curr += B.first;
curr += C.first;
res = max(res, curr);
}
}
}
}
cout << res << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/D는 크기가 같은 3개의 배열에서 하나씩 값을 골랐을 떄 최대값을 찾는 최적화 문제이다.
서로 다른 두 배열에서 같은 인덱스를 고를 수 없기 때문에 어떤 배열에서는 3번째로 큰 값을 골라야 할 수도 있다.
정렬하면 쉽게 풀 수 있지만, O(N log N) 이 아니라 O(N)으로 풀고싶어서 큰 값 3개를 저장하는 클래스를 만들고 각 배열에서 스위핑으로 3개의 큰 값과 그 값의 인덱스를 골랐다.
그리고 결과를 출력하기 위해서 인덱스가 어떻게 겹치나에 따라서 if문을 많이 써줘야 할 것 같았지만, 생각하기 귀찮아서 각 배열에서 고를 수 있는 값 3개를 brute force로 총 27가지 경우에 대해 모두 시도해보고 그중 최대값을 골랐다(cout << res 직전에 있는 3중 for문이 이것이다). 이 과정은 한번만 실행되기 때문에 O(1)시간이고, 시간복잡도에는 영향이 거의 없다.
E2. Game with Marbles
https://codeforces.com/contest/1914/problem/E2
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
using namespace std;
int A[200000];
int B[200000];
class Choice {
public:
int a;
int b;
Choice() {}
Choice(int a, int b) : a(a), b(b) {}
bool operator < (const Choice& c) const {
return (a + b) > (c.a + c.b);
}
};
Choice table[200000];
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> A[i];
}
for (int i = 0; i < n; i++) {
cin >> B[i];
table[i] = Choice(A[i] - 1, B[i] - 1);
}
sort(&table[0], &table[n]);
bool alice = true;
long long int res = 0;
for (int i = 0; i < n; i++) {
if (alice) {
res += table[i].a;
}
else {
res -= table[i].b;
}
alice = !alice;
}
cout << res << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/E는 easy와 hard가 있었는데, hard가 풀릴 것 같아서 hard부터 풀고 easy에는 코드를 복붙했다.
게임 이론이고, 처음부터 모든 인덱스를 고를 수 있기 때문에 그리디로 풀린다. 점수를 상대적으로 매기기 때문에 (Alice가 선택했을 때 얻을 점수 - (Bob이 선택했을 때 Alice가 손해볼 점수)) = (Alice가 얻을 점수 + Bob이 얻을 점수)가 이득이다.
이것을 기준으로 정렬하고 앞에서부터 차례대로 선택하면 답이 나온다. 이때 각 항목당 이득과 손해는 int범위 안쪽이지만, 선택 횟수가 200000까지 될 수 있으므로 결과는 long long int로 계산해서 출력해야 한다.
F. Programming Competition
https://codeforces.com/contest/1914/problem/F
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> tree[200001];
// first: unpairables, second: pairables
pair<int, int> DFS(int p) {
pair<int, int> large = make_pair(0, 0);
int rem = 0; // sum of others
if (tree[p].size() == 0) {
return make_pair(1, 0);
}
for (int n : tree[p]) {
pair<int, int> curr = DFS(n);
if (curr.first > large.first) {
rem += large.first + large.second;
large = curr;
}
else {
rem += curr.first + curr.second;
}
}
if (rem >= large.first) {
rem += large.first + large.second;
return make_pair((rem & 1) + 1, rem & (~1));
}
else {
return make_pair(large.first - rem + 1, large.second + rem * 2);
}
}
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int n;
cin >> n;
fill(&tree[1], &tree[n + 1], vector<int>());
for (int i = 2; i <= n; i++) {
int p;
cin >> p;
tree[p].push_back(i);
}
cout << DFS(1).second / 2 << '\n';
}
return 0;
}
/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/F는 트리의 노드들을 두개씩 짝짓는데, 조상이 아닌 노드와만 짝지을 때 최대 몇 쌍을 만들 수 있느냐를 묻는 문제이다. 어떤 노드에 여러개의 서브트리가 있다면, 서로 다른 서브트리에 있는 노드들은 모두 짝지을 수 있다. 그러므로 서브트리중에 가장 큰 서브트리의 노드 수보다 나머지 서브트리에 있는 노드 수의 합이 더 많다면 모든 노드(홀수라면 하나 제외)를 짝지을 수 있게 되고, 그렇지 않다면 가장 큰 서브트리에서 짝짓지 못한 노드를 더 상위 노드로 올리는 방식으로 그리디하게 DFS를 돌리면 풀 수 있다.
이때 주의해야 할 점이 서브트리 안에서도 짝을 지을 수 있기 때문에, 이미 짝지을 수 있는 상태로 넘어온 노드와 짝지어지지 못한 상태로 넘어온 노드를 구분해야 한다. 그래서 DFS를 돌릴 때 리턴 타입을 pair<int, int>로 해서 이미 짝지을 수 있는 노드와 아직 짝을 짓지 못한 노드를 구분해서 처리해주었다. 가장 큰 서브트리를 고를 때도 전체 노드 수가 아닌 짝지어지지 않은 노드 수를 기준으로 골랐다.