본 대회에 직접 참여한 것이 아닌, 문제만 풀어본 것임을 미리 밝힙니다.
코포를 시작하게 된 이유?
최근 ICPC 2021 Seoul 문제들을 보면서 영어문제들을 빠르게 푸는 중요성을 느끼게 됐다.
codeforce처럼 주어진 시간 내에 다양한 알고리즘을 요구하는 문제들을 빠르고 정확하게 해결하기 위해 시작하게 됐으며, 코포에 굉장히 자주 나오는 주제인 greedy, adhoc, constructive를 보는 눈이 ps 전반적으로 큰 도움이 될 것이라는 생각이 들어 codeforce에 많은 관심을 가지게 됐다.
군복무중이 아니라면 직접 라운드에 참여해 내 백준 아이디에 초록색, 민트색이라도 띄워보고 싶은데 아쉽다.
그래서 전역 전까지는 코드포스 문제에 익숙해지는 시간을 가져보려고 한다.
그리하여 시작한 코드포스 3문제 풀어보기 ㅎㅎ.
비교적 최근에 시행된 라운드 문제들을 포스팅해보겠다.
Codeforce 제출 형식
- 여러 개의 test case로 이루어져 있으나, SCPC, 코드잼, 킥스타트와 다르게 "Case # :"을 따로 출력할 필요는 없다.
- input, output은 각각 stdin, stdout 표준 입출력을 따른다.
주의할 점은 모든 문제가 영어로 돼있기 때문에 해석하는 데에 상당한 시간이 걸릴 수 있다.
해석 대충 하다간, 조건을 놓쳐 WA를 향해 풀이를 작성할 수 있기 때문에 주의하도록 하자.
A. Divan and a Store
N이 100까지밖에 안되기 때문에 l~r까지의 가격대를 for문으로 탐색해주면 된다.
최대한 많이 사기 위해선, 그리디하게 작은 가격대의 물건을 사야 한다.
이를 이용하면 AC를 받는다.
#include <bits/stdc++.h>
using namespace std;
int t,n,l,r,k,a[101];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin>>t;
while(t--){
cin>>n>>l>>r>>k;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
int s=0,ans=0;
for(int i=0;i<n;i++){
if(a[i]<l)continue;
if(a[i]>r)break;
if(s+a[i]>k)break;
s+=a[i];
ans++;
}
cout<<ans<<"\n";
}
}태그: greedy, 800
B. Divan and a New Project
이문제도 그리디하게 많이 방문하는 곳일수록 가까운 곳에 배치해주면 된다.
index 실수로 test 1에서 틀린 적이 있다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
const int MAX = 200011;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
int t, N, a[MAX], res[MAX];
bool cmp(pi p1, pi p2) {
return p1.first > p2.first;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> t;
while (t--) {
cin >> N;
fill(a, a + MAX, 0);
fill(res, res + MAX, 0);
ll ans = 0;
vector<pi> v;
for (int i = 0; i < N; i++) {
cin >> a[i];
v.push_back({ a[i], i });
}
sort(all(v), cmp);
for (int i = 0; i < N; i++) {
ans += 1LL * 2 * v[i].first * (1LL * i / 2 + 1);
res[v[i].second] = i / 2 + 1;
if (i % 2)
res[v[i].second] = -res[v[i].second];
}
cout << ans << "\n";
cout << 0 << " ";
for (int i = 0; i < N; i++) {
cout << res[i] << " ";
}
cout << "\n";
}
}한번 틀린 후, 다시 제출할 때 폰으로 풀질 않아서 bits/stdc++.h를 사용하지 못했다.
태그: greedy, 1000
C. Divan and bitwise operations
이 문제부터 좀 난이도가 높아진 느낌이 있었다.
m개의 특정 구간에서의 OR value가 주어지는데, 이를 통해 sequence의 XOR 부분수열의 합을 구하는 문제였다.
맨처음에는 백준의 "행성x3" 문제가 생각났다.
그런데 조금 생각해보니 각 subsegment의 OR 연산자 값이 x라면, 특정 index에서 x, 나머지 index에서 0이어도 전혀 상관이 없다.
그렇기 때문에 이런 x를 비트로 가지는 값이 적어도 하나의 수열에는 반드시 존재할 것이고, xor연산은 홀수개일 때 1, 짝수개일 때 0을 출력하기 때문에 kC1 + kC3 + ... = 2^(k-1)을 이용하여 답을 출력해주면 된다.
N이 상당히 크기 때문에 분할정복 곱셈을 이용해 O(lgk)에 계산해주자.
사실 이렇게 적으니까 되게 쉽게 푼거처럼 느껴질 수 있는데 꽤 고민을 오래 했다.
실제 대회였다면 C까지 풀었거나, C에서 말려서 못풀었을 듯하다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int n,m,l,r,x;
ll power(ll M,ll k){
if(!k)return 1;
if(k==1)return M;
ll r=power(M,k/2)%mod;
r=(r*r)%mod;
if(k%2)r=(r*M)%mod;
return r%mod;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--){
cin>>n>>m;
ll ans=0,num=0;
while(m--){
cin>>l>>r>>x;
num|=x;
}
cout<<(power(2,n-1)*num)%mod<<"\n";
}
}태그: combinatorics, bitmasks, constructive, 1500
C번이 1500이라니...
그래도 1000까지 쉽게 느껴져서 정말 다행이다.
빨리 전역하고 코드포스 라운드를 돌려보고 싶다.
1차 목표는 우리학교에 거의 존재하지 않는(ㅠㅠ) 블루 색깔을 가지는 것이고,
2차 목표는 간지나는 퍼플, 오렌지를 가져보는 것이다.
굉장히 목표치가 높긴 한데, 꾸준히 해서 성장하는 사람들을 꽤 많이 봤기 때문에, 그리고 아직 졸업까지 꽤 많은 시간이 있기 때문에 일단 도전해보려고 한다 ㅎㅎ
(물론 코포와 같은 ps는 취미에 불과하다. 취미 그 이상을 넘어서 하진 않을 듯하다.)
'PS > Codeforces' 카테고리의 다른 글
| [Codeforces] Round 800 Div.2 인생 첫 코포 후기 (0) | 2022.06.21 |
|---|