Codeforces Round 972 (Div. 2)

코드포스 대회에 참여하고 3번째 대회이다.

 

지금까지 본 코포중 제일 잘 친 대회인 것 같다..

C번은 거의 신뢰의 제출이었는데 운좋게 한번에 맞았다. ㄷㄷ

 

어쩌다보니 블루 퍼포를 받아버렸다. 

3번째 대회인만큼 보정치가 합해져서 +401 ㄷㄷ..

첫 코포를 좀 잘쳤으면 그린 갔을듯하다..

 

A(00:00 ~ 00:30)

처음에 일단 무작정 제출해봤다가 망했음을 감지하고 3틀을 해서 푼 문제다..

나름(?) 어려웠었는데 틀려서 새로고침할때마다 푼사람이 1000명씩 늘어나는걸 보고 접고싶은 생각이 들었다.

(이걸 왜 못풀었지)

 

아무튼 aeiou를 배치해서 펠린드롬의 개수를 최소하 하는 방법은 aaaaaeeeeeiiiiiooooouuu와 같이 배치하는 것이다.

int main(){
    fastio;
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		string s="aeiou";
		if(n<=5){
			for(int i=0; i<n; i++)cout<<s[i];
			cout<<endl;
		}
		else{
			int cnt[5]={0,};
			int idx=0;
			while(n){
				cnt[idx]++;
				n--;
				idx=(idx+1)%5;
			}
			for(int i=0; i<5; i++){
				for(int j=0; j<cnt[i]; j++)cout<<s[i];
			}
			cout<<endl;
		}
	}
	return 0;
}

 

B1(00:30 ~ 00:38)

BFS문제인줄 알고 접근했다가 틀렸다.

학생 - 선생 - 선생, 선생 - 학생 - 선생, 선생 - 선생 - 학생으로 배치된 상태로 나누어서 처리해주면 된다.

2번째 경우에는 두 선생위치의 중앙이 최대가 된다.

 

B2(00:38 ~ 00:46)

선생들의 위치를 정렬한 후 B1의 전략을 그대로 사용하면 된다.

 

int main(){
    fastio;
	int t;
	cin>>t;
	while(t--){
		int n,m,q;
		cin>>n>>m>>q;
		vector<int>t(m);
		for(auto&v:t)cin>>v;
		sort(all(t));
		while(q--){
			int a;
			cin>>a;
			auto up=lower_bound(all(t),a);
			if(up==t.end()){
				cout<<n-t.back();
			}
			else if(*up==t.front()){
				cout<<t.front()-1;
			}
			else{
				cout<<(*up-*(up-1))/2;
			}
			cout<<endl;
		}
	}
	return 0;
}

 

C(00:46 ~ 01:06)

 

어캐풀었지;; 대충 느낌대로 dp를 짜니까 맞았다.

int main(){
    fastio;
	int t;
	cin>>t;
	string target="narek";
	while(t--){
		int n,m;
		cin>>n>>m;
		vector<string>arr(n);
		for(auto&v:arr)cin>>v;
		vector<vector<int>>dp(n+1,vector<int>(5,-iinf));
		dp[0][0]=0;
		for(int i=1; i<=n; i++){
			string now=arr[i-1];
			int cnt=0;
			for(int j=0; j<now.size(); j++){
				if(target.find(now[j])==string::npos)continue;
				cnt++;
			}
			for(int j=0; j<5; j++){
				int css=j;
				int save=0;
				for(auto&v:now){
					if(v!=target[css])continue;
					css++;
					if(css!=5)continue;
					save++;
					css=0;
				}
				int nscore=10*save-cnt;
				dp[i][css]=max(dp[i][css],dp[i-1][j]+nscore);
				dp[i][j]=max(dp[i][j],dp[i-1][j]);
			}
		}
		cout<<*max_element(all(dp[n]))<<endl;
	}
	return 0;
}