Meta Hacker Cup 2023 (종료)

친구 소개로 처음 참여해봄

https://www.facebook.com/codingcompetitions/hacker-cup

Meta Hacker Cup

 

다른 온라인 저지 사이트들이나 경쟁 프로그래밍 사이트랑 다르게 제출이 좀 까다롭다
input 파일을 받아서 output 파일을 생성하고
소스코드랑 output 파일을 사이트에 제출하는 방식이다

https://www.facebook.com/codingcompetitions/hacker-cup/2023/practice-round/problems/A1

Problem A1: Cheeseburger Corollary 1 | Meta Hacker Cup - 2023 - Practice Round

#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(){
	fastio;
	ifstream readFile;
	ofstream writeFile;
	readFile.open("inp.txt");
	writeFile.open("ans.txt");
	int T;
	readFile>>T;
	for (int i = 1; i <= T; i++)
	{
		if(readFile.eof())break;
		int S,D,K;readFile>>S>>D>>K;
		int bread=S*2+D*2;
		int meat=S+D*2;
		string ans="NO";
		if(bread>=K+1&&meat>=K)ans="YES";
		writeFile<<"Case #"<<to_string(i)<<": "<<ans<<"\n";
	}
	readFile.close();
	writeFile.close();
	return 0;
}

위 문제를 이런식으로 풀어서 ans.txt를 생성하고 제출하면 됨

 

문제 지문이 전부 영어이고, 파일 입출력이 익숙하지 않아서 고전할지도 모르겠다

1 라운드는 10월 8일에, 새벽 2시부터 새벽 5시까지 진행된다

2 라운드는 10월 22일에, 새벽 2시부터 새벽 5시까지 진행된다

목표는 2라운드 진출

꼭 티셔츠 받아서 운동하러 갈 때 입고 가고 싶음

 

라운드	푼 문제 수	총평
1 (10/8)	2(21pt)	서버 터짐
2 (10/22)	2(17pt)	풀다가 잠듬

---

1라운드 후기

세계에서 손꼽히는 큰 대회인데 서버가 터졌다 그래서 내 등수가 어디이고 내 수준이 어느정도인지 모르겠다

아무튼 1점 이상 제출한 모든 인원이 2라운드에 진출했으니... 목표는 달성했다

 

A번 문제

A번 문제는 간단한 정렬 문제이다. 정렬 이후 1,2, N-1,N번째 엘프의 위치만 보면 답이 나온다

예외처리가 필요하다. 문제 조건에서 엘프를 혼자서 일하게 할 수 없기 때문에, N==5인 경우의 예외처리가 필요한데, 이 경우 1,2 / 3,4,5번째 엘프들이 같이 일하게 하거나, 1,2,3/4,5번째 엘프들이 같이 일하게 해 더 큰 것을 출력해야 함

 

#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(){
	fastio;
	ifstream readFile;
	ofstream writeFile;
	readFile.open("inp.txt");
	writeFile.open("ans.txt");
	int T;
	readFile>>T;
	for (int i = 1; i <= T; i++)
	{
		if(readFile.eof())break;
		int N;readFile>>N;
		vector<double> v(N);
		for (int j = 0; j < N; j++)readFile>>v[j];
		sort(v.begin(),v.end());
		double ans;
		if(N==5){
			ans = max(((v[N-1]+v[N-3])/2)-((v[1]+v[0])/2),((v[N-1]+v[N-2])/2)-((v[2]+v[0])/2));
		}
		else ans = ((v[N-1]+v[N-2])/2)-((v[1]+v[0])/2);
		writeFile<<"Case #"<<to_string(i)<<": "<<fixed<<setprecision(10)<<ans<<"\n";
	}
	readFile.close();
	writeFile.close();
	return 0;
}

 

B번 문제

소인수분해를 활용해 해를 구성하는 문제인데 삽질을 좀 했다

#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(){
	fastio;
	ifstream readFile;
	ofstream writeFile;
	readFile.open("inp.txt");
	writeFile.open("ans.txt");
	int T;
	readFile>>T;
	for (int i = 1; i <= T; i++)
	{
		if(readFile.eof())break;
		int P;readFile>>P;
		int flg = 0;

		if(P>1572864)flg=1;

		ll divsum=0;
		vector<int> ans;
		while (P>1)
		{
			if(flg)break;
			for (int dn = 2; dn <= P; dn++)
			{
				if(divsum>41){flg=1;break;}
				if(dn>41){flg=1;break;}
				if(P%dn==0){
					P/=dn;
					divsum+=dn;
					ans.push_back(dn);
					break;
				}
			}
		}

		if(divsum<41&&!flg){
			while (divsum!=41)
			{
				divsum++;
				ans.push_back(1);
			}
		}
		if(divsum>41){flg=1;}
		
		if(flg){
			writeFile<<"Case #"<<to_string(i)<<": "<<-1<<"\n";
			continue;
		}
		else{
			writeFile<<"Case #"<<to_string(i)<<": "<<ans.size();
			for (int z:ans)
			{
				writeFile<<" "<<z;
			}
			writeFile<<"\n";
		}
	}
	readFile.close();
	writeFile.close();
	return 0;
}

합이 41이 되도록 하면서 곱이 최대가 되는 경우를 생각해 보자.

3 * 2^19 이 경우에 합이 41이면서 곱이 최대임. 그래서 1572864보다 큰 P에 대해서는 무조건 -1을 출력하면 된다.

P가 인수분해 할 수 있을 정도로 충분히 작기 때문에 단순히 인수분해해도 시간 제한이 터지지 않는다

그래서 대충 인수분해해서 벡터에 때려박은 뒤, 인수분해의 합들이 41이 될 때까지 벡터에 1을 계속 집어넣으면 된다

내 코드가 좀 더러운 이유는 예외처리를 한번에 못 찾아서 삽질을 많이 했기 때문이다

 

B-2번 문제

B번 문제의 코드를 활용해 소인수분해된 원소들을 적당히 합치면 될 것 같다고 생각했으나 대회 서버도 이상하고 마땅한 방법도 떠오르지 않아 시도하지 않았다

 

C번 문제

최소공배수/최대공약수 + 포함 배제 원리를 사용하는 문제 같았다

set이나 bitset을 이용해, 퍼즐에 가해야 하는 연산의 개수를 최소로 줄인 뒤 어떻게 어떻게 하는 방법밖에 떠오르지 않았다

근데 생각나는 방법들로는 시간복잡도가 무조건 터질 것 같아서

일단 퍼즐의 초기상태를 퍼즐에 가한 연산들의 집합으로 나타낸 뒤 시작해야겠다고 생각했는데

모르겠음

어떤 정수론 지식이 필요하거나, 아니면 set이나 bitset을 사용하지 않는 다른 쉬운 방법이 있을 거 같다

---

2라운드 후기

 

A번문제

R,C<3000정도의 제한에서는 완전탐색하면서 흰돌 그룹을 bfs처리해주는것으로 간단히 풀린다

백준으로 넘어가면 딱 골드 5~골드4정도 받을 것 같은 문제

A2번의 주의할 점은, 흑돌을 놓을 수 있는 공간마다 인접한 흰돌 그룹이 여러개일 수도 있어서 그걸 잘 처리해줘야 한다는 거??

출제자 solution역시 R*C 시간복잡도의 BFS를 제안한다.

#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;

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

int main(){
	fastio;
	ifstream readFile;
	ofstream writeFile;
	readFile.open("inp.txt");
	writeFile.open("ans.txt");
	int T;
	readFile>>T;
	for (int tc = 1; tc <= T; tc++)
	{
		if(readFile.eof())break;
		int R,C;readFile>>R>>C;
		vector<string> v(R);
		vector<vector<int>> vis;
		vis.assign(R,vector<int>(C,0));
		for (int i = 0; i < R; i++)readFile>>v[i];
		int group = 0;
		queue<pii> qq;
		map<pii,int> mm;
		int ans = 0;
		for (int i = 0; i < R; i++)
		{
			for (int j = 0; j < C; j++)
			{
				//흰돌이면 거기부터 bfs하면서 모두 그룹화
				if(vis[i][j]==0&&v[i][j]=='W'){
					vis[i][j]=++group;
					qq.push({i,j});
					set<pii> airss;//숨구멍
					int groupcnt = 1;
					while (!qq.empty())
					{
						auto [cx,cy]=qq.front();
						qq.pop();
						for (int k = 0; k < 4; k++)
						{
							int nx = dx[k]+cx;
							int ny = dy[k]+cy;
							if(nx<0||ny<0||nx>=R||ny>=C)continue;
							if(vis[nx][ny])continue;
							if(v[nx][ny]=='.'){
								vis[nx][ny]=vis[cx][cy];
								airss.insert({nx,ny});
								continue;
							}
							if(v[nx][ny]=='B')continue;
							qq.push({nx,ny});
							vis[nx][ny]=group;
							groupcnt++;
						}
					}
					if(airss.size()==1){
						pii tmp = *airss.begin();
						mm[tmp]+=groupcnt;
						ans = max(ans,mm[tmp]);
					}
					for (auto airs:airss)
					{
						vis[airs.first][airs.second]=0;
					}
				}
			}
		}

		writeFile<<"Case #"<<to_string(tc)<<": "<<ans<<"\n";
	}
	readFile.close();
	writeFile.close();
	return 0;
}

 

B번문제

풀다가 그래로 잠들었다. 참고로 500등 안에 들려면 AB를 매우 빠르게 풀거나 C까지 제출했어야 하기 때문에 별로 아쉽지는 않다.

다음에 풀어봐야지....