AtCoder Beginner Contest 174 후기

https://atcoder.jp/contests/abc174

AtCoder Beginner Contest 174 - AtCoder

---

 

약 한 달 만에 열리는 Beginner 대회였습니다. 오랜만에 참가했지만 레이팅이 가장 높게 나와서 뿌듯했습니다.

6문제 중 5문제를 풀었는데, 마지막에있는 어려운 문제가 백준에서 풀었던 기억이 나는 문제여서 다행히 풀 수 있었습니다.

전반적으로 문제의 퀄리티는 좋았는데, 마지막 문제가 너무 웰 노운 문제였던 것 같아 조금 아쉬웠습니다.

20분가량을 남겨두고 결국 못 푼 제가 취약한 그리디 문제들도 꾸준히 노력을 해야 할 것 같습니다.

 

A- 생략합니다.

B- sqrt() 함수 사용할 줄 아니? 묻는 문제네요. 또 주의해야 할 점은 실수형을 다루는 것.. 빼고는 특별할 것 없이 구현하면 됩니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;

int main()
{
	int N, D, cnt = 0;
	cin >> N >> D;
	for (int i = 0; i < N; i++)
	{
		ll x, y;
		cin >> x >> y;
		double dist = sqrt(x*x + y*y);
		if (dist <= D)cnt++;
	}
	cout << cnt;
}

 

C- 처음엔 어떻게 접근을 해야 할지 몰라 조금 당황해서 일단 스킵했던 문제였습니다. 다행히 다른 문제를 풀고 돌아오니 해결방법이 보였는데, 복잡할 거 없이 나눗셈 연산을 구현하면 되는 문제입니다. 나누어 떨어질 때까지 계속 7을 추가하다가 이전에 방문했던 나머지가 나오면 false, 나누어 떨어진다면 추가되었던 7의 개수를 반환하면 됩니다. 처음엔 재귀로 구현을 했다가 재귀 스택이 너무 많았는지 visual studio가 오류가 나길래 반복문으로 구현을 했습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 1e7 + 2, INF = 987654321;
bool visited[MAX_N] = { 0, };

int main()
{
	int K;
	cin >> K;

	int now = 7, ret = 1;
	while (true)
	{
		if (visited[now]) {
			cout << -1;
			break;
		}
		visited[now] = true;
		if (now%K == 0) {
			cout << ret;
			break;
		}
		ret++;
		now %= K;
		now = now * 10 + 7;
	}

}

 

E- 이분 탐색을 쓸 수있다는 아이디어만 떠오르면 구현은 쉽게 할 수있습니다. 포인트는 길이를 자를때 서로 같은 길이로 잘라야 최적해가 나온다는 겁니다. 일부러 헷갈리게할려고한건지 예제설명에는 서로 다른 길이로 자르는데, 소수점단위의 다른 길이로 잘라야 하나? 라는 접근을 하면 문제를 포기하게됩니다.. K번을 잘라 모든 길이가 mid이하가 될수있는지를 반환하는 is_possible()함수를 사용해서 이분탐색을 쓰면 됩니다.

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;


bool is_possible(int mid, vector<int>&v, int K)
{
	int ret = 0;
	for (auto i : v)
	{
		ret += (i %mid == 0 ? i / mid - 1 : i / mid);
	}
	return (ret <= K);
}

int main()
{
	int N, K;
	cin >> N >> K;
	vector<int>v(N);
	for (auto&i : v)cin >> i;

	int left = 1, right = 1e9 + 2, ret = -1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (is_possible(mid, v, K))
		{
			ret = mid;
			right = mid - 1;
		}
		else left = mid + 1;
	}
	cout << ret << endl;

}

 

F-밑의 문제와 동일한 문제입니다. 한 가지 다른 점은, N제한이 F문제가 더 크기 때문에 수열과 쿼리 5번 문제를 조금 느리게 통과하는 코드라면 F문제에서 시간 초과가 날 수 있음에 주의해야 합니다.

https://www.acmicpc.net/problem/13547

13547번: 수열과 쿼리 5

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
const int MAX_N=(int)1e5+2,MAX_NUM=(int)1e6+2;
int N,q,sqrtN,cnt=0,visited[MAX_NUM]={0,},ans[MAX_N];
int queryLeft,queryRight;
vector<int>arr;


struct MOS_QUERY
{
    int left,right,idx;
    MOS_QUERY(){;}
    MOS_QUERY(int left,int right,int idx){this->left=left,this->right=right,this->idx=idx;}
};
vector<MOS_QUERY> query;

bool compare(MOS_QUERY &a,MOS_QUERY &b)
{
    if(a.left/sqrtN!=b.left/sqrtN)return a.left/sqrtN<b.left/sqrtN;
    else return a.right<b.right;
}

void getFirst()
{
    queryLeft=query[0].left,queryRight=query[0].right;
    for(int i=queryLeft;i<queryRight;i++)
        if(visited[arr[i]]++ ==0) cnt+=1;
    ans[query[0].idx]=cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>N;
    sqrtN=sqrt(N);
    arr.resize(N);
    for(int i=0;i<N;i++)cin>>arr[i];
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int a,b;
        cin>>a>>b;
        query.push_back(MOS_QUERY(a-1,b,i));
    }
    sort(query.begin(),query.end(),compare);
    getFirst();
    for(int i=1;i<q;i++)
    {
        MOS_QUERY now=query[i];
        while(now.left<queryLeft)
            if(visited[arr[--queryLeft]]++ ==0) cnt+=1;
        while(now.left>queryLeft)
            if(--visited[arr[queryLeft++]] ==0) cnt-=1;
        while(queryRight<now.right)
            if(visited[arr[queryRight++]]++ ==0) cnt+=1;
        while(queryRight>now.right)
            if(--visited[arr[--queryRight]] ==0) cnt-=1;
        ans[now.idx]=cnt;
    }

    for(int i=0;i<q;i++)cout<<ans[i]<<"\n";

}