AtCoder Beginner Contest 290 후기 (ABC 290 3솔)

3108딩

72점 오름

 

A번

#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;cin>>N>>M;
	vector<int> A(N);
	int ans=0;
	for (int i = 0; i < N; i++)
	{
		cin>>A[i];
	}
	for (int i = 0; i < M; i++)
	{
		int t;cin>>t;
		ans+=A[t-1];
	}
	cout<<ans;
	return 0;
}

그냥 문제의 point를 벡터나 배열에 기록해놓고

B로 불러낼 때마다 그 벡터에 들어있는 값을 ans에다가 더해주면 됨

 

B번

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

int main(void) {
	fastio;
	string S;
    int N,K;cin>>N>>K>>S;
	string T="";
	for (int i = 0; i < S.length(); i++)
	{
		if(K&&S[i]=='o'){
			K--;
			T=T+"o";
		}
		else T=T+"x";
	}
	cout<<T;
	return 0;
}

N,K,S를 입력받은다음에

S의 처음부터 끝까지 탐색하면서 문자열에 'o' 또는 'x'를 append 하면서 정답 문자열 T를 만들면 된다

 

C번

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

int numcnt[320000];

int main(void) {
	fastio;
	int N,K;cin>>N>>K;
	for (int i = 0; i < N; i++)
	{
		int t;
		cin>>t;
		if(t>310000)continue;
		numcnt[t]++;
	}
	int ans=0;	
	for (int i = 0; i < K; i++)
	{
		if(numcnt[i])ans++;
		else break;
	}
	cout<<ans;
	return 0;
}

문제 설명이 좀 안 읽힌다

1≤K≤N≤3×10^5 로 범위가 주어지므로, 어떤 숫자가 몇 번 등장했는지 카운팅하는 배열을 사용 가능하다

 

0부터 n 까지의 숫자가 최소한 한번씩 등장했다면, 정답으로 n+1을 출력하면 된다.

그러니깐, 0부터 K-1까지의 숫자에 대해 이게 나왔는지 안나왔는지 확인하고

어떤 숫자가 안나오는 순간 그 숫자를 ans로 출력하면 됨

 

D번 - TLE

// TLE code  TLE code TLE code TLE code TLE code TLE code TLE code

#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 T;cin>>T;
	while (T--)
	{
		set<int> ss;
		ll N,D,K,A=0;
		cin>>N>>D>>K;
		ll cnt=1;
		ll now=0;
		ss.insert(0);
		while (cnt<K)
		{
			ll x=(A+D)%N;
			while (ss.count(x))
			{
				x=(x+1)%N;
			}
			now=x;
			A=x;
			ss.insert(x);
			cnt++;
		}
		cout<<now<<"\n";
	}
	return 0;
}
//TLE code TLE code TLE code TLE code TLE code TLE code TLE code TLE code TLE code

문제 설명이 그리 안 읽히지는 않는데 그대로 제출하면 시간초과가 나므로

정수론의 어떤 성질을 이용해 시간복잡도를 줄여야 하는 문제 같다

모르겠딩

 

E번 - 읽다가 포기

펠린드롬이 뭔지는 잘 아는데, 이건 단순히 구현이 복잡한 문제 같다.

 

F번 - 아이디어 생각하다가 끝

경우의 수를 따지는 문제 같은데, 트리의 크기가 커지면서 경우의 수가 매우 빠르게 늘어난다. 그래서 dp나 누적합이나 세그먼트 트리를 쓰는 문제 같고 계산 중간중간 모듈러 연산의 성질을 이용해 오버플로우를 방지해야 한다는 것까지는 알겠다.