AtCoder Beginner Contest 303 후기 (ABC 303 4솔)

계피맛에서 녹차맛이되었다

B는 독해가 어렵고 D는 DP라서 어려웠고 A는 비트연산자를 잘못쓰는 실수를 했다

사람들이 느낀 난이도는 이러하다. E까지는 평이한 난이도이고 F는 어렵게 나옴

E는 잘 비비면 풀 수도 있었겠는데 딱 보고 아이디어가 떠오르지는 않더라 문제 이해가 어렵기도 했고

 

A - 조건문, 문자열

뭐 없다

B - 영어독해, 카운팅

코드가 좀 잘렸는데 잘린 부분엔 return 0밖에 없다

Two people who did not stand next to each other in any of the photos may be in a bad mood.

이거를

->> 어떤 사진에서도 한번도 바로 옆에 인접한 적이 없는 두명의 사람 쌍은 bad mood상태가 된다

라고 해석해야 함

 

 

C - 쉬운 시뮬레이션

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

int main(void) {
	fastio
	int N,M,H,K;cin>>N>>M>>H>>K;
	string S;cin>>S;
	set<pair<int,int>> ss;
	for (int i = 1; i <= M; i++)//체력이 K보다 낮다면 K로 변경, 아님 냅둬
	{
		int a,b;cin>>a>>b;
		ss.insert({a,b});
	}

	int nx = 0,ny=0;
	for (int i = 0; i < N; i++)
	{
		if(H<=0){
			cout<<"No";return 0;
		}
		if(S[i]=='R'){
			nx++;
			H--;
			if(ss.count({nx,ny})&&H<K){
				H=K;
				ss.erase({nx,ny});
			}
		}
		else if(S[i]=='L'){
			nx--;
			H--;
			if(ss.count({nx,ny})&&H<K){
				H=K;
				ss.erase({nx,ny});
			}
		}
		else if(S[i]=='U'){
			ny++;
			H--;
			if(ss.count({nx,ny})&&H<K){
				H=K;
				ss.erase({nx,ny});
			}
		}
		else if(S[i]=='D'){
			ny--;
			H--;
			if(ss.count({nx,ny})&&H<K){
				H=K;
				ss.erase({nx,ny});
			}
		}
	}
	cout<<"Yes";
	return 0;
}

그냥 읽히는 대로 구현하면 풀리는 쉬운 문제

 

D - DP

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

ll dp[300001][2];//캡락꺼짐, 캡락켜짐

int main(void) {
	fastio
	ll X,Y,Z;cin>>X>>Y>>Z;
	string S;cin>>S;

	if(S[0]=='a'){
		dp[0][0] = min(X,Z+Y+Z);//a입력하고 캡락 그대로
		dp[0][1] = min(Z+Y,X+Z);//a입력하고 캡락 켜기
	}
	else{
		dp[0][0] = min(Y,Z+X+Z);//A입력하고 캡락 그대로
		dp[0][1] = min(Z+X,Y+Z);//A입력하고 캡락 켜기
	}
	for (int i = 1; i < S.length(); i++)
	{
		if(S[i]=='a'){
			dp[i][0] = dp[i-1][0] + min(X,Z+Y+Z);//꺼진상태에서 a치고 캡락 그대로
			dp[i][1] = dp[i-1][1] + min(Y,Z+X+Z);//켜진상태에서 a치고 캡락 그대로
			dp[i][0] = min(dp[i][0],dp[i-1][1] + min(Z+X,Y+Z));//켜진상태 a치고 캡락 켜기
			dp[i][1] = min(dp[i][1],dp[i-1][0] + min(Z+Y,X+Z));//꺼진상태 a치고 캡락 켜기
		}
		else{
			dp[i][0] = dp[i-1][0] + min(Y,Z+X+Z);//꺼진상태에서 A치고 캡락 그대로
			dp[i][1] = dp[i-1][1] + min(X,Z+Y+Z);//켜진상태에서 A치고 캡락 그대로
			dp[i][0] = min(dp[i][0],dp[i-1][1] + min(Z+Y,X+Z));//켜진상태 A치고 캡락 켜기
			dp[i][1] = min(dp[i][1],dp[i-1][0] + min(Z+X,Y+Z));//꺼진상태 A치고 캡락 켜기
		}
	}
	cout<<min(dp[S.length()-1][0],dp[S.length()-1][1]);
	return 0;
}

와

그냥 DP도 젬병인데 이런 DP는 진짜 젬병이다 엄청 헷갈리게 만들어놓음

주석을 주렁주렁 달아놓은거만 봐도 헷갈렸다는 것이다

오래걸리긴 했어도 실수는 안하고 한번에 AC 받았다

 

E - 그래프

 

>>> 업솔빙

star그래프의 차수가 1인 정점들을 서로 연결해 트리를 만들었다고 하고, 우리는 입력으로 주어진 트리의 모양을 보고 원래 star 그래프들이 어떤 모습이었는지 추측해야 한다.

1. (예제1,2처럼)트리가 한방향으로 길게 늘어질 경우?? 그녀석들을 우선적으로 레벨 2짜리 스타로 분리해야 함.

2. 남은 것들을 스타로 분리해야 하는데, 이녀석들은 자식이 여러개일 것이고 부모를 포함시키거나 / 포함시키지 않으면서 스타로 분리해야 하는데, 처리하지 않은 정점의 개수가 2개 이하가 되지 않도록 하면 될듯??

 

 

 

 

>>> 에디토리얼

 

 

F - 모르겠다. imos라고 생각했으나 배열로 처리할 수 있는 게 아님. 그리디로 예상

 

>>> 업솔빙

 

>>> 에디토리얼