2024해커컵
해커컵이 1년만에 돌아왔다
최근에 O1이라는 녀석이 나와서 알고리즘 대회마다 AI 치터들이 깽판칠 수 있을 것 같기도 한데
뭐어쩌겠음
내가 신경쓸 영역도 아닌거같다
잘하자
내 실력이 작년보다 늘었는지는 잘 모르겠다
3라운드 진출(500등) 하면 티셔츠 준다
작년엔 2라운드에서 1700등 하면서 3라운드 못가고 티셔츠 못받음
해커컵 입출력 처리하기
일단 입출력이 까다롭다
작년에 내가 제출했던 코드를 참고하자
#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;
}위처럼 txt파일에서 입력을 받고 출력을 파일로 저장해야 함
그걸 위해 인풋파일스트림과 아웃풋파일스트림을 사용하고 그걸로 파일을 연 뒤 사용 후 꼭 닫아줘야한다
1라운드후기:
1번문제 풀고 2번문제 풀다가 잤다
2번문제까지 풀면 2라운드 가더라
근데못풀었다
#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 N;readFile>>N;
vector<pair<double,double>> v(N+1);
double mmax=-1;
for (int i = 1; i <= N; i++)
{
double a,b;
readFile>>a>>b;
v[i]={a,b};
mmax = max(i/b,mmax);
}
int flg = 0;
for (int i = 1; i <= N; i++)
{
auto [a,b]=v[i];
if(mmax>i/a)mmax=-1;
}
writeFile<<"Case #"<<fixed<<setprecision(9)<<to_string(tc)<<": "<<mmax<<"\n";
}
readFile.close();
writeFile.close();
return 0;
}1번문제 코드는이러하다
백준으로치면 실버중위권 정도 받을 문제 같은데
파일 입출력 하고 소수 다루다 보면 괜히 더 헷갈리는 것 같다
2번문제는 소수나오는걸로봐서 일단 정수론이구나 했는데
일단 문제가 안읽히는거임. 5 의 경우 {2,3}인데 8은 왜 {3,5}가 아니라 {2,3,5}인거지 싶었다
에디토리얼을 보니 애드혹처럼 대충 때려맞춰서 풀 수 있었겠다는 생각이 든다
근데 이론은 좀 심오함. 해석하면 이러하다
1. 정의에 의해 집합의 원소들은 무조건 소수들만 될 수 있음
2. 그렇기 때문에 N은 최소 5이고 그 집합은 {2,3}임
3. 짝수인 소수는 2밖에 없기에 쌍둥이 소수의 개수를 세고 그 중 큰 녀석이 나올때마다 답을 1씩 더해주는 것으로 모든 경우를 구할 수 있음.
4. 에라채를 이용해 소수의 개수를 세면 시간복잡도 내에 충분히 통과 가능하고 누적합으로 그 개수를 세라
3번문제는 무한히 계산되는 확률 나오는거보고 때려쳤다
그치만 공부할 필요는 있겠다
그치만 에디토리얼 봐도 이해안가는건 마찬가지임
검색하면 1라운드 한국 1위로 통과하신분이 블로그에 글 써 놓은 게 있는데 그거 참고하면 좀 낫다
조만간 이해하고 정리해서 풀이를 올려보겠다