본문 바로가기
C++/대회기록, CP기록

ABC 391 ABCDE (C++)

fepick포트폴리오 2025. 2. 2. 14:50

 

https://atcoder.jp/contests/abc391/tasks

 

Tasks - AtCoder Beginner Contest 391

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

 

퍼포먼스가 안정적으로 1200이상 나와야 앳코더 민트를 바라볼 수 있다

C번 문제 쉬운 아이디어가 필요해서 좋았다

D번 문제 개끔찍한 구현을 했지만 쉬운 아이디어가 필요한 문제라 좋았다

E번문제도 쉬운 문제인데 D를 푸는데 힘을 다 써버린 나머지.......... 생각없이 코드를 짜놓은 뒤 디버깅하다가 시간을 다 써버렸다

F번 문제의 경우 다양한 방법으로 풀 수 있다고 하고, 지문이 길지도 않으니 꼭 풀어볼 예정

 

A : 1분52초컷

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;

int main(void){
	fastio;
	string D;cin>>D;
	for (auto i:D)
	{
		if(i=='N')cout<<'S';
		if(i=='S')cout<<'N';
		if(i=='E')cout<<'W';
		if(i=='W')cout<<'E';
	}
	

	return 0;
}

string으로 받아서 문자 하나하나 처리할 경우 많은 조건 분기로 풀 필요가 없어지기 때문에 빠르게 풀 수 있는 문제였다

 

B : 6분30초컷

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;

int main(void){
	fastio;
	int N,M;cin>>N>>M;//50
	vector<string> A(N);
	vector<string> B(M);
	for (int i = 0; i < N; i++)
	{
		cin>>A[i];
	}

	for (int i = 0; i < M; i++)
	{
		cin>>B[i];
	}

	for (int i = 0; i+M-1 < N; i++)
	{
		for (int j = 0; j+M-1 < N; j++)
		{
			int chk = 0;
			for (int n = 0; n < M; n++)
			{
				for (int m = 0; m < M; m++)
				{
					if(B[n][m]!=A[i+n][j+m])chk=1;
				}
			}
			if(chk==0){
				cout<<i+1<<" "<<j+1;
				return 0;
			}
		}
	}
	return 0;
}

별거 없는 문제인데 지문이 길어지면 문제 설명 읽는데만 2분 이상씩 쓰는 것 같다. 

세계의 고수들은 이런 문제는 1분30초컷해버린다. 대단해~

 

C : 12분컷

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;

//N마리 비둘기 최대 100만
//쿼리 30만번

//N개 둥지 1~N번
int pg[1000001];//비둘기의 좌표
int ph[1000001];//비둘기집 인구수
int pc0;
int pc1;
int main(void){
	fastio;
	ll N,Q;cin>>N>>Q;
	pc1=N;
	for (int i = 0; i <= N; i++){
		pg[i]=i;
		ph[i]=1;
	}

	while (Q--)
	{
		int op;cin>>op;
		if(op==1){
			int P,H;cin>>P>>H;//P번 비둘기를 H로 이동
			if(ph[pg[P]]==1){
				pc0++;
				pc1--;
			}
			else if(ph[pg[P]]==2){
				pc1++;
			}
			ph[pg[P]]--;

			pg[P]=H;

			if(ph[H]==0){
				pc0--;
				pc1++;
			}
			else if(ph[H]==1){
				pc1--;
			}
			ph[H]++;
		}
		else{
			//비둘기가 둘 이상 들어있는 비둘기집의 개수를 출력
			cout<<N-pc0-pc1<<"\n";
		}
	}
	
	
	return 0;
}

"비둘기집의 원리" 를 떠올리기를 의도한 문제 제목과 설명 같다. 약간의 아이디어를 거쳐 2번 쿼리를 O(1)속도로 처리하는 것이 중요한 문제인데, N에서 비둘기가 1마리 이하로 들어있는 비둘기집의 개수를 빼면 비둘기가 둘 이상 있는 비둘기집의 개수를 알 수 있다.

Q : 그래서 이 문제에 비둘기집의 원리가 적용되었다고 볼 수 있나요??

A : 제가 이산수학을 제대로 배운 적은 없지만 비둘기집의 원리를 몰라도 풀 수 있는 문제이니 아닌 것 같아요.......

 

D : 47분컷

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;

//10억칸 줄과 W개 컬럼으로 된 그리드
//바닥으로부터 x,y만큼 떨어진 곳이 (x,y)좌표임 헷갈리네
//1x1짜리 블록이 N개 있고 i번째 블록은 0초에 xi yi 에 놓여있다
//t가 10^100으로 증가하는 동안 블록은 이동함
//바닥의 모든 행이 블록으로 차면, 바닥의 모든 블록이 제거된다
//블록이 공중에 떠 있다면 아래로 내려감(테트리스처럼)
//Tj+0.5초에 그 블록이 존재하는가를 쿼리로 출력

int main(void){
	fastio;
	int N,W;cin>>N>>W;

	//정렬 돌려놓고
	//저장할 때 가장 큰 Y열을 저장해놔야함.

	vector<int> BG(N+1);//블록이 몇번째 그룹에 속하나
	vector<pair<int,int>> blocks;//입력 배열
	map<int,pair<int,int>> mm;//번호로 블록 찾기
	map<pair<int,int>,int> ww;//블록 좌표로 번호 찾기
	vector<int> levcnt(N+1);//레벨에 해당하는 블록 개수(W개가 되면 그 행은 꽉 찬것)
	vector<vector<int>> v(W+1);//해당하는 열에 블록을 하나씩 쌓는다
	
	for (int i = 1; i <= N; i++)
	{
		int x,y;cin>>x>>y;
		mm[i]={x,y};
		ww[{x,y}]=i;
		blocks.push_back({x,y});
	}
	sort(blocks.begin(),blocks.end());

	vector<int> HM(N+1,0);//Height Max이다. 그룹에 해당하는 블록들 중 가장 큰 y값을 저장한다.
	int cur = 0;
	for (auto [bx,by]:blocks)
	{
		int pushpos = v[bx].size();
		v[bx].push_back(by);
		levcnt[pushpos]++;
		BG[ww[{bx,by}]]=pushpos;
		HM[pushpos]=max(HM[pushpos],by);
	}

	for (int i = 0; i < HM.size(); i++)
	{
		if(HM[i]==0){
			HM.resize(i);
			break;
		}
	}//시간복잡도 향상과 버그 방지를 위해 HM벡터의 마지막 0들을 없앴다
    
	// cout<<"\n----------\n";
	// for (int i = 0; i < HM.size(); i++)
	// {
	// 	cout<<HM[i]<<" ";
	// }
	// cout<<"\n----------\n";

	int Q;cin>>Q;
	while (Q--)
	{
		int T,A;cin>>T>>A;
		//T시간에 해결한 레벨이 A레벨보다 높으면 가능
		// int level = lower_bound(HM.begin(),HM.end(),T)-HM.begin(); //다시보니 이 코드는 필요가 없다
		// cout<<T<<" "<<A<<" "<<level<<" "<<BG[A]<<" "<<HM[BG[A]]<<": ";
		if(levcnt[BG[A]]<W)cout<<"Yes\n";	//그 행이 꽉 찰 수 없는 경우 그 블록은 영영 사라지지 않는다
		else if(T>=HM[BG[A]])cout<<"No\n";
		else cout<<"Yes\n";
	}
	return 0;
}

고수들은 이 문제 건너뛰고 E F 먼저 건드렸을 것 같다 구현과 디버깅이 힘들었다

이 문제 역시 C문제처럼 쿼리가 주어진다.
문제조건의 범위를 살펴보니 N과 Q가 20만이니깐 전처리를 O(NlogN)으로 처리하고 쿼리를 O(QlogN)으로 풀어야겠다는 생각을 했다

나의 경우 배열을 이것저것 선언해 놓고 전처리를 O(NlogN)으로 한 뒤 쿼리를 O(Q)으로 처리했다........

전처리

  1. 블록들을 입력받으면서 그 블록의 번호가 몇번인지 기억하기 위해 map을 사용했다
  2. 입력받은 블록들에 대해 정렬을 싹 돌렸다
  3. 같은 열에 저장되는 블록들 중 얘가 몇번째로 쌓이는가? 를 보고 레벨을 정해 주었다
  4. 같은 레벨에 저장되는 블록들 중 얘가 몇초에 쌓이는가?(y가 몇인가?) 를 보고 HM배열에 그 최댓값을 저장해 주었다
  5. 어떤 레벨(행) 이 꽉 차서 지워지는가? 를 판단하기 위해 그 레벨에 원소가 몇개 들어오는지를 카운트해 주었다

쿼리

  1. 어떤 레벨이 지워지기 위해선 그 레벨의 카운트가 W이어야 하니 levcnt를 이용해 예외처리
  2. 블록이 속하는 그룹이 지워지는 시간(HM)보다 T가 큰지를 판단해 블록이 지워졌다면 No출력 그렇지 않다면 Yes출력

 

고수의 코드 분석

고수들은 이 문제도 3분~4분컷을 한다 어떻게 풀었나 함 보자

1등한 중국인의 코드를 가져왔다. https://atcoder.jp/contests/abc391/submissions/62275860

가져온 다음 필요없는 전처리들 다 지우고 주석을 달아 보았다

#include <bits/stdc++.h>
#define INF 1000000000
#define F first
#define S second
#define N 200010
using namespace std;
int n,m,q,ans[N];
vector<pair<int,int> > seq[N]; //seq[x]={y,블록인덱스};
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		x--;
		seq[x].push_back(make_pair(y,i));
	}
	for(int i=0;i<m;i++) sort(seq[i].begin(),seq[i].end());//블록을 y좌표순으로 쌓는다(내아이디어와동일)
	memset(ans,63,sizeof(ans));	//63 memset은 처음보는데 신기하다
    
    //아래 for문의 전처리 논리는 나랑 똑같은데 단 2개의 배열과 간결한 코드로 답을 뽑아낸다
	for(int t=0;;t++){				//행 단위로 살펴볼거임(내 코드로 치면 level)
		int lim=0;
		for(int i=0;i<m;i++){		//첫번째 열부터 마지막 열까지 루프 
			if(t>=seq[i].size()){	//그 열에 t번째 블록이 없다면 그 행은 지워질 수 없음
				lim=INF+INF;		
				break;
			}
			lim=max(lim,seq[i][t].F);//lim의 값은 그 행의 최댓값
		}
		if(lim>INF) break;			//이후의 것들은 모두 INF일 테니깐 볼 필요도 없다
		for(int i=0;i<m;i++) ans[seq[i][t].S]=lim;	//정답배열 초기화 - 그 행의 블록들은 모두 lim에 처리된다
	}
	scanf("%d",&q);
	while(q--){//쿼리 O(Q)
		int x,y;
		scanf("%d%d",&y,&x);
		x--;
		puts(ans[x]>y?"Yes":"No");
	}
	return 0;
}

논리는 나랑 똑같은데 머리 구조가 나랑 다른건지.......문제를 보면 배열의 구조를 어떻게 해야 할지 머리에 떠오르나보다

혹은 비슷한 문제를 최적의 코드로 많이 짜 보면 나도 저렇게 할 수 있지 않을까? 아님 말고

 

E : 40분이상걸림

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;

//바이너리 스트링 B
//얘의 길이는 3^n이다...
//바이너리 스트링 C를 얻을 건데 얘의 길이는 3^n-1이다.

//C를 만드는 방법:
//B의 원소의 그룹을 3개로 나누고, 그룹에서 가장 큰 값을 추출
//Ci의 값은 B의 연속된 3개 원소 중 가장 많이 등장하는 녀석

//나는 A를 입력받는데요. A는 바이너리스트링이고 길이가 3^N임. 
//A'은 A'1 이고. 이것은 A에 위의 연산을 N번 적용한 어떤 숫자임.

//A'1의 값을 변경하기 위해선 A의 원소를 몇 개 토글해야 하는가?

//분할정복

pair<int,int> solve(string S,int n){
	if(n==1){
		if(S[0]=='1')return {1,1};
		if(S[0]=='0')return {0,1};
	}
	auto [aa,ab] = solve(S.substr(0,n/3),n/3);
	auto [ba,bb] = solve(S.substr(n/3,n/3),n/3);
	auto [ca,cb] = solve(S.substr(n*2/3,n/3),n/3);
	// cout<<aa<<" "<<ab<<" "<<ba<<" "<<bb<<" "<<ca<<" "<<cb<<"\n";
	int c0=0,c1=0;
	if(aa)c1++;else c0++;
	if(ba)c1++;else c0++;
	if(ca)c1++;else c0++;
	int ra;int rb=0;
	ra=(c0<c1);
	if(ra){//전체를 0으로 바꾸기 위한거 개수를 셀거임..
		if(c0==0){//2개를 0로 바꿔야한다
			rb=ab+bb+cb-max(ab,max(bb,cb));
		}
		else{//1개를 0로 바꿔야한다
			if(aa==0){
				rb=min(bb,cb);
			}
			if(ba==0){
				rb=min(ab,cb);
			}
			if(ca==0){
				rb=min(ab,bb);
			}
		}
	}
	else{//전체를 1으로 바꾸기 위한거 개수를 셀거임..
		if(c1==0){//2개를 1로 바꿔야한다
			rb=ab+bb+cb-max(ab,max(bb,cb));
		}
		else{//1개를 1로 바꿔야한다
			if(aa==1){
				rb=min(bb,cb);
			}
			if(ba==1){
				rb=min(ab,cb);
			}
			if(ca==1){
				rb=min(ab,bb);
			}
		}
	}
	return {ra,rb};
}

int main(void){
	fastio;
	int N;string S;cin>>N>>S;
	cout<<solve(S,S.length()).second;
	return 0;
}

깔끔하게 분할정복으로 풀리는 문제인데 재귀형으로 코드를 짜다 보면 아래를 한번씩 따져보게 되는듯

  1. 최적 부분 구조를 만족하는가
  2. 뭘 리턴해야 되냐
  3. 리턴 조건이 빠진 건 없는가(제일중요)
  4. dp를 같이 써야 되는건 아닌가

이중에 2번이 젤 어려운거같다 처음에 코드 짤 때 tuple로 {0의개수,1의개수,0과1을전환하기위해바꿔야하는애의최소개수} 리턴하다가 구현 난이도가 올라가서 시간 다 날렸다

pair<int,int>로 {얘가0인지1인지,0과1을전환하기위해바꿔야하는애의최소개수} 를 리턴하게 했더니 쉽게 풀렸다

뭐 설명할것도없음

 

고수의코드분석

1등했다는 중국인의 코드를 또 가져왔다. 이건 4분 30초컷했더라

#include <bits/stdc++.h>
#define INF 1000000000
#define F first
#define S second
#define ll long long
#define N 2400010
using namespace std;
int n;
string s;
pair<int,int> dfs(int l,int r){
	if(l==r) return make_pair(s[l]=='1',s[l]=='0');
	int len=r-l+1;
	auto v0=dfs(l,l+len/3-1);
	auto v1=dfs(l+len/3,r-len/3);
	auto v2=dfs(r-len/3+1,r);
	int x=INF,y=INF;
	x=min(x,v0.F+v1.F+v2.F);
	x=min(x,v0.F+v1.F+v2.S);
	x=min(x,v0.F+v1.S+v2.F);
	x=min(x,v0.S+v1.F+v2.F);
	y=min(y,v0.S+v1.S+v2.S);
	y=min(y,v0.S+v1.S+v2.F);
	y=min(y,v0.S+v1.F+v2.S);
	y=min(y,v0.F+v1.S+v2.S);
	return make_pair(x,y);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>s;
	auto [x,y]=dfs(0,s.size()-1);
	cout<<max(x,y)<<'\n';
	return 0;
}

똑같이 분할정복(dfs)으로 풀었다

이사람은 {1로바꾸는데 필요한 토글횟수,0으로바꾸는데 필요한 토글횟수}를 리턴하게 해서 풀었는데 이게 훨 깔끔하고 직관적이다

그리고 S.substr()을 하지 않고 인덱스로 문자열에 접근하게 해서, 오버헤드를 줄이고 시간복잡도 공간복잡도 쌀먹을 잘하는 모습이다

 

F : ???

3가지 이상의 풀이가 존재하고 이번 대회에서 꽤나 많이 풀린 문제이다(쉽게 나온듯)

다음주 중에 꼭 풀어보자...............................

 

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
using namespace std;

int main(void) {
	fastio;

    //길이 N인 3개 수열 ABC가 있는데
    //수열의 원소를 하나씩 골라 만들 수 있는 조합 N^3개
    //그걸 f로 계산한 숫자 중 K번째로 큰 수를 골라라

	/*
    풀이 1:
    우선순위 큐를 이용한다.
    제일 큰 원소를 빼는 과정을 K번 하는데 K가 20만이라서 이렇게 풀어도 풀림
    이 과정을 빠르게 하기 위해선 모든 원소를 내림차순으로 정렬해 놓고, pq에 튜플을 집어넣어야 함'

    풀이 2:
    가능한 정답을 매개변수로 이분탐색을 돌리는데
    결정 함수를 나이브하게 돌리면 O(N^3)이니깐, 가지치기를 한다
    가지치기를 통해 결정함수를 O(K)까지 줄일 수 있음

    풀이 3:
    내림차순 정렬해놓고 인덱스의 곱이 K보다 작도록 해서
    가능한 후보를 다 벡터에 집어넣은 뒤
    nth element를 구해버려도 된다
    */

	return 0;
}
저작자표시

'C++ > 대회기록, CP기록' 카테고리의 다른 글

마작컵 2024 - 우인전 3/4 님만 오면 ㄱ (6솔, C++)  (1) 2024.12.29
최근에 못푼 ABC 문제들(저장용)  (2) 2024.12.12
2024해커컵  (1) 2024.10.05
2024 모비스 알고리즘 경진대회 신청함!!  (0) 2024.05.30
Meta Hacker Cup 2023 (종료)  (0) 2023.09.26

'C++/대회기록, CP기록' Related Articles

티스토리툴바