[Codeforces] Round 927 (Div. 3) 후기
https://codeforces.com/contest/1932
Dashboard - Codeforces Round 927 (Div. 3) - Codeforces
codeforces.com
2024.02.18
블로그 첫 글!
최근들어 블로그에 내가 공부했던 것들을 저장하면 좋을 것 같다는 생각을 했다.
근데 생각만하고 정작 실행에 옮기지는 못했는데
그 러 다 가!
평소엔 코포 div2는 2솔도 간당간당하고, div3는 3솔밖에 못하다가
어제 열렸던 div3에서 ABCD 4솔을 해버렸다...
19번의 코포에 참여하면서 매번 그레이에 머물던 내가, 이번 대회에서 생전 처음으로 민트 퍼포를 받고 드디어 그린에 승급했다. 🎉 🎉 🎉
기분도 좋겠다. 쇠뿔도 단김에 빼라고, 대회 친 다음날에 바로 후기글을 작성하기 시작했다!
목표는 코포 블루! 졸업하기에 꼭 찍었으면 좋겠다.
A. Thorns and Coins (00:03)
입력으로 주어진 string을 앞에서부터 탐색하다가 **이 나올때 멈추고 여태 나온 @의 수를 반환해주면 된다.
더 일찍 풀 수 있었는데 딴짓한다고 바로 시작을 못했다...ㅜㅜ
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin>>t;
while(t--){
int n; cin>>n;
string str; cin>>str;
ll ans = 0;
rep(i,0,n){
if(str[i]=='.') continue;
if(str[i]=='@') ans++;
if(str[i]=='*' && str[i+1]=='*'){
break;
}
}
cout<<ans<<'\n';
}
}
B. Chaya Calendar (00:10)
배열의 앞에서부터 탐색하면서 a[i] = (a[i-1]보다 큰 a[i]의 배수)를 저장하면 된다. 이후 a[n-1]을 출력.
예를들어 [3,2,4,5,9,18]은 [3,4,8,10,18,36]이 되고, a[n-1] = 36이므로 답은 36이 된다.
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main(){
ios::sync_with_stdio(0); cin.tie(0);
ll t; cin>>t;
while(t--){
ll n; cin>>n;
vector<ll> v(n);
rep(i,0,n) cin>>v[i];
rep(i,1,n){
ll k = (v[i-1]/v[i]) + 1;
v[i] *=k;
}
cout<<v[n-1]<<'\n';
}
}
C. LR-remainders (00:29)
배열값들을 모두 deque에 저장하고, string의 순서대로 deque에서 값을 뽑아 순서대로 배열에 저장한다.
이후, 순차적으로 값들을 모두 곱해 모듈러 연산을 해주어야하는데... overflow의 위험이 있으므로 다른 방법으로 계산해주어야 한다.
배열을 역순으로 탐색하면서 mod연산을 진행하면 overflow없이 계산할 수 있다.
overflow생각 안하고 코드를 짜는 바람에 1번 틀렸다 ㅠㅠ..
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main(){
ios::sync_with_stdio(0); cin.tie(0);
ll t; cin>>t;
while(t--){
ll n,m; cin>>n>>m;
deque<ll> dq;
rep(i,0,n){
ll x; cin>>x;
dq.push_back(x);
}
string str; cin>>str;
vector<ll> tmp;
rep(i,0,str.length()){
if(str[i]=='L'){
tmp.push_back(dq.front()); dq.pop_front();
}
else{
tmp.push_back(dq.back()); dq.pop_back();
}
}
reverse(tmp.begin(),tmp.end());
vector<ll> ret;
ll x = 1;
rep(i,0,tmp.size()){
x *= tmp[i];
x%=m;
ret.push_back(x);
}
reverse(ret.begin(),ret.end());
rep(i,0,ret.size()){
cout<<ret[i]<<' ';
}
cout<<'\n';
}
}
D. Card Game (01:11)
그냥 빡구현 문제였다.
승패가 결정나는 카드 쌍은 다음과 같이 총 3종류로 나눌 수 있다.
[문양이 같은 일반카드 2장], [트럼프카드, 일반카드], [트럼프카드, 트럼프카드]
1. 문양이 같은 일반카드 두장씩 묶고,
2. 남은 일반카드는 트럼프카드와 묶고,
3. 남은 트럼프카드끼리 묶으면 된다.
이때, 1번과정에서 남은 일반카드의 수가 트럼프카드보다 많으면 IMPOSSIBLE,
또, 3번과정에서 트럼프카드의 개수가 홀수라면 IMPOSSIBLE을 출력한다.
코드가 길어져서 틀릴까봐 제출하고 조마조마하고있었는데 다행이 원트클했다 ㅎㅎ
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main(){
ios::sync_with_stdio(0); cin.tie(0);
ll t; cin>>t;
while(t--){
int n; cin>>n;
char trump; cin>>trump; //트럼프 선정
int tr=-1;
if(trump=='C') tr = 0;
else if(trump=='D') tr = 1;
else if(trump=='H') tr = 2;
else if(trump=='S') tr = 3;
vector<string> card[4]; // C,D,H,S
vector<pair<string,string>> ret;
rep(i,0,2*n){
string str; cin>>str;
if(str[1]=='C') card[0].push_back(str);
else if(str[1]=='D') card[1].push_back(str);
else if(str[1]=='H') card[2].push_back(str);
else if(str[1]=='S') card[3].push_back(str);
}
int cnt=0;
int trcnt = card[tr].size();
rep(i,0,4){
sort(card[i].begin(),card[i].end());
if(tr==i) continue;
cnt += card[i].size()%2;
}
if(trcnt < cnt){
cout<<"IMPOSSIBLE\n";
continue;
}
vector<string> tmp; //트럼프랑 이어줄거
rep(i,0,4){
if(tr==i) continue;
for(int j=1;j<card[i].size();j+=2){
ret.push_back({card[i][j-1],card[i][j]});
}
if(card[i].size()%2){
tmp.push_back(card[i][card[i].size()-1]);
}
}
int k = trcnt - cnt;
if(k%2==1){
cout<<"IMPOSSIBLE\n";
continue;
}
rep(i,0,tmp.size()){
ret.push_back({tmp[i], card[tr][i]});
}
for(int i=cnt;i<card[tr].size();i+=2){
ret.push_back({card[tr][i],card[tr][i+1]});
}
rep(i,0,ret.size()){
cout<<ret[i].X<<' '<<ret[i].Y<<'\n';
}
}
}
E. Final Countdown
길이 400,000짜리 숫자가 입력으로 주어진다니... 뭔가 규칙을 잘 찾아서 큰수연산을 하면 될 것같다는 느낌이 들었다.
아니나 다를까, 그게 맞더라.
규칙의 힌트는 문제 맨아래 Note에 있었다.
1234에서 4초,3초,2초,1초 걸리는 숫자의 수를 각각 구해서 계산을 해봤더니 다음과 같은 식이 나왔다.
4*1 + 3*(12-1) + 2*(123-12) + 1*(1234-123)
= 1 + 12 + 123 + 1234
= 1370
어 이건가? 싶어서 예제의 12345를 위의 방법대로 계산해봤더니
12345 + 1234 + 123 + 12 +1
= 13715
계산결과가 예제 그대로 나왔고, 이대로 구현하여 제출하니 AC가 떴다.
사실 D번까지만 풀고 E문제보고 어떻게 구현할지 생각을 좀 하다가 도저히 안떠오르길래 "아 이 정도 풀었으면 됐겠지.."하는 생각에 걍 쉬었다... 한 20분? 이후 다시 컴퓨터 앞에 앉아 문제를 보는데 실마리가 보였고, 코드를 짰지만... 아쉽게도 시간안에 제출하지 못했다.. 코포 끝나고 제출하니 AC를 받았다. 안쉬었으면 대회시간안에 E까지 풀었을 것 같은데... 아쉽다ㅠㅠ
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main(){
ios::sync_with_stdio(0); cin.tie(0);
ll t; cin>>t;
while(t--){
ll n; cin>>n;
string str; cin>>str;
vector<int> t;
rep(i,0,str.length()){
t.push_back(str[i]-'0');
}
rep(i,1,t.size()){
t[i] += t[i-1];
}
for(int i=t.size()-1;i>0;i--){
t[i-1] += t[i]/10;
t[i] %= 10;
}
int idx=0;
while(t[idx]==0) idx++;
rep(i,idx,t.size()){
cout<<t[i];
}
cout<<'\n';
}
}
F. Feed Cats
-
G. Moving Platforms
-