별사탕와쟉와쟉
ICPC Seoul Regional 2020 풀어보기 - 1 본문
교수님께서 알고리즘 수업을 수강한 학생 중 1~2학년이고 성적 잘 받은 사람 중에서 ICPC 나가는걸 제안해 주셨다. 그래서 어느샌가 팀이 꾸려졌고 올해 ICPC에 출전하게 되었다...
교수님께서 내 주신 첫 과제는 ICPC 2020 Seoul Regional 세트 풀어오기 이다.
백준 OJ에 문제세트 카피가 있으며 쉬운 문제부터 풀어보려 한다.
문제 난이도는 solved.ac에 등재된 것을 기준으로 한다.
총 12문제 중, 난이도 순서대로 B, E, C, G, J, A의 풀이를 적는다.
B - Commemorative Dice
간단한 문제다. 경우의 수가 6x6=36가지밖에 없으므로 이기는 횟수를 카운트해 확률을 출력하면 된다.
다만, 기약분수로 출력해야 하므로 GCD를 한 번 돌려 주자.
코드
#include<bits/stdc++.h>
#define lld long long
using namespace std;
int dice1[6], dice2[6];
int gcd(int a,int b){
if(a==0) return b;
return gcd(b%a,a);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
for(int i=0;i<6;i++) cin >> dice1[i];
for(int i=0;i<6;i++) cin >> dice2[i];
int cnt = 0;
for(int i=0;i<6;i++){
for(int j=0;j<6;j++){
if(dice1[i]>dice2[j]) cnt++;
}
}
int d = gcd(cnt,36);
cout << cnt/d << '/' << 36/d;
}E - Imprecise Computer
1 차이의 대소비교는 랜덤하게 하는 부정확한 컴퓨터(IC)가 있다. 그리고 1~n의 수를 모두 한번씩 비교하며 각 수에 대해 이긴 횟수를 세는 행위를(즉, nC2 번) 한 라운드라고 한다. 라운드를 두 번 진행한다. 그러면 1부터 n까지 이긴 횟수를 나타내는 수열이 두 개가 나올 텐데, 이 수열의 각 원소 차를 구한 것이 문제의 difference sequence이다. 이 difference sequence가 주어졌을 때 이것이 유효한지 판단하라는 문제다.
키포인트 1
k는 자기 자신을 제외한, 1~k-1, k+1~n과 비교된다. 여기서 1 차이가 나는 k-1과 k+1을 제외하면 차이가 2 이상이므로 확실하게 비교된다. 즉, k가 이기는 경우는 1부터 k-2까지(확실), k-1과 k+1(랜덤)이므로 k-2번 확실하게 이기고 랜덤하게 2회 이길 수 있다.
키포인트 2
k가 확실히 이기는 횟수(k-2)는 항상 같으므로, 그 차이인 difference sequence에서 고려되지 않는다. 인접한 숫자(k 및 k+1)끼리 어떤 숫자가 승점을 빼앗았는지만 고려하면 된다.
키포인트 3
k가 k+1보다 크다고 IC가 판정하면 k+1은 k보다 작다고 판정된 것이므로, k는 1회 또는 2회 추가로 이기는 것이고, k+1은 0회 또는 1회 추가로 이기게 된다. k와 k+1의 비교에서 k가 승리했으므로, 1점을 k가 빼앗아 간 것이다. 이를 이용하면 적절한 DP 식을 세울 수 있다.
여기부턴 경우 나누기와 구현이다. DP 배열을 (수, 1라운드에서 이긴 수, 2라운드에서 이긴 수)로 정의했다.
'라운드에서 이긴 수'라는 표현이 조금 이상하긴 하지만, k가 이겼는지 k+1가 이겼는지를 각각 0/1로 적은 것이다. 즉 (N-1)x2x2 크기의 배열이 나온다.
difference sequence가 유효한지 불가능한지 판단만 하라고 했으므로, 주어진 difference sequence를 읽어가며 DP배열의 가능한 경우에 1을 체크하며 진행한다. N-1번째 DP 위치에서 4가지 경우 중 1이 없으면 NO, 하나라도 있으면 가능한 경우이므로 YES를 출력한다.
코드
#include<bits/stdc++.h>
#define lld long long
using namespace std;
int d[1000000];
int p[999999][2][2]; //0: k win, 1: k+1 win
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int N;
cin >> N;
for(int i=0;i<N;i++){
cin >> d[i];
}
//first case
if(d[0]==0){
p[0][1][1]=1; //all next => (round1, round2) = 00
p[0][0][0]=1; //all now => 11
} else if(d[0]==1){
//cannot be 21 or 12
p[0][1][0]=1; // next now => 10
p[0][0][1]=1; //now next => 01
} else if(d[0]==2){
//cannot be 20 or 02
cout << "NO";
return 0;
}
for(int i=1;i<N-1;i++){
for(int j=0;j<2;j++) for(int k=0;k<2;k++) if(p[i-1][j][k]) {
//j k be selection for round1 and round2 resp.
switch(d[i]){
case 0: // 00 11 22
if(j==k){
p[i][1][1]=1; // 00 and 11
p[i][0][0]=1; // 11 and 22
}else if(j!=k){
p[i][j][k]=1; // 11
}
break;
case 1: // 01 10 12 21
if(j==k){
p[i][0][1]=1; // 10 and 21
p[i][1][0]=1; // 01 and 12
} else if(j!=k){
p[i][0][0]=1; // 12 and 21
p[i][1][1]=1; // 01 and 10
}
break;
case 2: // 02 20
if(j!=k){
p[i][k][j]=1; // 02 and 20
}
break;
}
}
}
//last case
bool qual = false;
for(int j=0;j<2;j++) for(int k=0;k<2;k++) if(p[N-2][j][k]) {
//j k be selection for round1 and round2 resp.
if(j==k && d[N-1]==0){
qual=true;
} else if(j!=k && d[N-1]==1){
qual=true;
}
}
if(qual) cout << "YES";
else cout << "NO";
}C - Dessert Cafe
분류를 봐도 '이걸 어떻게 풀지' 싶었던 문제였다.
가중치 트리 그래프에 아파트가 있고, 카페를 세우기 좋은 'Good Place'를 찾는 것이다. Good Place p의 정의는 p가 아닌 모든 q에 대해 d(p, z)<d(q, z) 인 아파트 z가 (적어도 하나씩)존재하는 것이다. 즉, 해당 정점이 다른 정점에 대해 적어도 하나 더빠르게 접근 가능한 아파트가 있는지를 판단해야 한다.
키포인트
조건이 어려워보이나, 그래프가 트리인 것(유일한 경로가 최단경로)과 가중치가 양수인 것을 비교해 보면, good place를 찾는 데 가중치를 무시해도 된다. 아파트로 둘러싸인 정점들은 반드시 good place이며 그 외는 good place가 아니다.
아파트가 good place임은 자명하고, 아파트 A와 B의 최단경로 상의 임의의 정점 K는 K~A에 있는 정점들보다 B에 가깝고, B~K 사이의 정점들보다 A에 가깝다. 그 외의 정점이 K에 비해 A쪽에 가깝다면 K는 그들보다 B에 가깝고, 반대도 성립하므로 아파트 사이 최단경로 안의 정점이 good place이다. 손으로 그려가며 생각해보면 간단하고 AC로 증명해도 될 듯 하다.
이 원리를 이용해 DFS + DP를 실행하면 된다. DFS에서 부모노드로 올라오면서, '지금까지 센 good place'와 '부모에 good place가 있다면 추가할 정점들(후보 정점)'을 리턴해야 한다. good place는 아파트로 둘러싸여있으므로 DP를 위해 경우를 나누면,
- 부모가 아파트
- 자식에 아파트가 두 개 이상
- 자식에 아파트가 한 개
- 자식에 아파트 없음
먼저, 자식에 아파트가 있다는 것은 good place 수가 1 이상인 것으로 알 수 있다.
부모가 아파트면 자식에 있는 good place 수, 후보 place, 부모노드 모두 good place가 된다.
자식에 아파트가 두 개 이상이면 부모 노드는 반드시 아파트 사이에 있는 것이므로(트리) 위와 같다.
자식에 아파트가 하나만 있다면 후보 노드만 1 추가된다.
자식에 아파트가 없다면 후보노드도 0, good place도 0이다.
코드
#include<bits/stdc++.h>
#define lld long long
using namespace std;
int n,k;
int apt[100001];
vector<pair<int,int>> tree[100001];
int v[100001];
pair<int,int> dfs(int from){
v[from]=1;
int connect = 0;
int total = 0;
int tba = 0;
for(int i=0;i<tree[from].size();i++){
int to = tree[from][i].first;
if(from !=to && v[to]==0){
pair<int,int> a = dfs(tree[from][i].first);
if(a.first>0) connect++;
total+=a.first;
tba += a.second;
}
}
if(apt[from]){
return make_pair(total+tba+1,0);
}
if(connect == 1){
return make_pair(total,tba+1);
} else if(connect>=2){
return make_pair(total+tba+1,0);
}
return make_pair(total,tba);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> k;
for(int i=0;i<n-1;i++){
int f,t,w;
cin >> f >> t >> w;
tree[f].push_back(make_pair(t,w));
tree[t].push_back(make_pair(f,w));
}
for(int i=0;i<k;i++){
int a;
cin >> a;
apt[a] = 1;
}
cout << dfs(1).first;
}G - Mobile Robot
로봇 위치를 주고, 로봇이 일렬 거리 d로 번호순서대로 정렬할 때 로봇이 이동하는 최대 거리의 최솟값을 구하는 문제다.
거대한 낚시가 있다. 0, 1, 2, ... n 순서도 정렬 가능하지만 n, n-1, n-2, ... 0 순서도 유효하다는 것이다. 따라서 두 방향 모두 값을 구해 최솟값을 구해야 한다.
키포인트
로봇이 정렬될 때 0, d, 2d, 3d, ... (n-1)d로 이동한다고 하자. 음의 방향으로 가장 많이(또는 양의 방향으로 가장 적게), 양의 방향으로 가장 많이(또는 음의 방향으로 가장 적게) 움직이는 로봇이 각각 반드시 존재한다. 편의상 각각 '음의 로봇', '양의 로봇'이라고 하겠다.
0, d, 2d, 3d... 위치로 움직이기 위해 '음의 로봇'이 +5를 움직이고 '양의 로봇'이 +25 움직여야 한다고 가정하자. 가장 크게 움직이는 로봇 둘이 적게 움직이기 위해선 로봇이 -15, -15+d, -15+2d ...로 이동해야 '음의 로봇'은 -10, '양의 로봇'은 +10를 이동한다. 나머지 로봇은 모두 -10~+10만큼 이동한다. 따라서 답은 10이다.
따라서 0, d, 2d, 3d, ...와 로봇의 각 위치를 뺀 값의 최댓값과 최솟값을 구하고, 최대최소 차이를 2로 나누면 된다.
다만.... 주의할 점은 차잇값이 10^16을 넘어가므로 double의 오차 범위가 커버하지 못한다. 다행인 것은 나누기 2만 하므로 홀수를 나누게 된다면 2로 나누고 .5를 출력해주자.
코드
#include<bits/stdc++.h>
#define lld long long
using namespace std;
lld N,d;
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N >> d;
lld dif;
lld mini1 = LONG_LONG_MAX;
lld mini2 = LONG_LONG_MAX;
lld maxi1 = LONG_LONG_MIN;
lld maxi2 = LONG_LONG_MIN;
for(lld i=0;i<N;i++){
lld a;
cin >> a;
dif = (d*i)-a;
if(mini1>dif) mini1=dif;
if(maxi1<dif) maxi1=dif;
dif = -d*i-a;
if(mini2>dif) mini2=dif;
if(maxi2<dif) maxi2=dif;
}
lld first = (maxi1-mini1);
lld second = (maxi2-mini2);
cout << fixed;
cout.precision(1);
lld res = first<second?first:second;
cout << res/2;
if(res%2!=0) cout << ".5";
else cout << ".0";
}J - Switches
스위치 N개가 있고 전등 N개가 있다. 스위치 하나 당 여러개의 전등이 연결되어 있는데, 전등에 연결된 켜진 스위치 수가 홀수개일때 불이 켜지고 짝수개면 꺼진다고 한다. 이때, 각 전등 하나만 켜지도록 하려면 어느 스위치를 켜야하는지 N줄에 걸쳐 출력하라는 문제이다. 방법이 없으면 -1을 출력해야 한다.
키포인트
전등 = 행렬 x 스위치 의 연립방정식이다. 행렬의 i행을 i번째 전등, j행을 j번째 스위치로 하고 역행렬을 구하자. 역행렬의 i열의 1의 위치가 i 전등만 켜기 위해 눌러야 할 스위치 번호가 된다.
역행렬은 가우스 소거법을 구현하면 되고 수 체가 Z/2Z이므로 덧셈만 하면 끝난다.
코드
#include<bits/stdc++.h>
#define lld long long
using namespace std;
int ls[500][500];
int id[500][500];
void swap(int &a,int &b){
int t;
t=a;
a=b;
b=t;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int N;
cin >> N;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cin >> ls[j][i];
}
id[i][i]=1;
}
for(int i=0;i<N;i++){
int target = -1;
for(int j=i;j<N;j++){
if(ls[j][i]){
target=j;
break;
}
}
if(target==-1){
cout << -1;
return 0;
} else{
for(int k=0;k<N;k++){
swap(ls[target][k],ls[i][k]);
swap(id[target][k],id[i][k]);
}
for(int j=0;j<N;j++){
if(ls[j][i] && i!=j){
for(int k=0;k<N;k++){
ls[j][k] = (ls[j][k]!=ls[i][k]);
id[j][k] = (id[j][k]!=id[i][k]);
}
}
}
}
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++)
if(id[j][i]){ cout << j+1 <<' ';}
cout << '\n';
}
}A - Autonomous Vehicle
악마같은 구현 문제다. 자율주행차가 시작점에서 시작해 교점을 만나면 좌회전, 끝점을 만나면 유턴한다. 계속하다보면 시작점으로 돌아올텐데 그래도 계속 순환한다고 한다. 출력해야 할 것은 시각 t가 주어지면 그때의 좌표를 계산하는 것이다. 속력은 1초당 단위길이이고 두 선분은 최대 한 점에서 교차하고 반드시 사거리가 생기며 끝점은 공유하지 않는다.
키포인트
1초에 한 칸 이동하면 교점 탐색 시간 * 10^7회가 걸리므로 시간 초과가 날 것이다. 따라서 교점과 끝점 정보를 저장해 구현할 수 있도록 적절한 구조체와 컨테이너를 만들어야 한다.
구현한 방법은 다음과 같다.
- 각 선분에 대해 끝점과 교점을 저장하는 컨테이너를 만든다.
- 교점을 구하고 저장한다. n^2.
- 끝점을 저장한다.
- 각 선분에 대해 임계점을 정렬한다. n^2 log n.
- 좌표,방향,현재선분, 누적시간을 이용해 시뮬레이션한다. 현재 선분 위치에서 현재 좌표에 해당하는 교점을 이분탐색으로 찾고 방향에 따라 이전/다음 포인터를 가져와 그 교점으로 현재 좌표를 갱신하고, 그 교점에 저장된 교선 id로 현재선분을 업데이트한다.
- 시작점으로 돌아올 때까지 반복하며 그 구간을 저장한다.
- 순환 시간에 대한 나머지를 구하고 이분탐색으로 어떤 구간에서 해당 시간을 보내는지 가져와 좌표를 구한다.
4~6번에서 n^2 log n의 시간이 걸리는데, 4번 이전에 선분을 정렬한다면 log n이 필요 없고, 교점 구조체끼리 서로를 참조하도록 하면 시뮬레이션 시 log n도 필요 없어지지만 귀찮으므로 구현하지 않았다.
이 알고리즘을 처음 생각하고 구현했을 때 틀렸고 재구현했을 때도 틀렸다. 다만 세 번째 구현했을 때는 AC를 받았다. 복잡한 구현에선 구조체나 클래스를 정교하게 만들고 연산자를 오버로딩해서 구현 시 혼란이 오지 않도록 하자...
코드
#include<bits/stdc++.h>
#define lld long long
using namespace std;
struct P{
P(){x=0; y=0;};
P(lld a ,lld b){
x=a;
y=b;
};
lld x,y;
P operator+(P z){
return P(z.x+x , z.y+y);
};
P operator-(P z){
return P(x-z.x , y-z.y);
}
bool operator==(P z){
return (z.x==x) && (z.y==y);
}
bool operator<(P z){
return z.x==x ? y<z.y : x<z.x;
}
lld operator*(P z){
return z.x*x+z.y*y;
}
lld cross(P z){
return x*z.y - y*z.x;
}
};
struct L{
P s,e;
L(){s=P(); e=P();};
L(P a, P b){s=a; e=b;};
P intersect(L l){
if( (e-s) * (l.e-l.s) == 0 ){ //perpendicular
if(((e-s).cross(l.s-e)<0 != (e-s).cross(l.e-e)<0) && ((l.e-l.s).cross(e-l.e)<0 != (l.e-l.s).cross(s-l.s)<0)){
if(l.s.x==l.e.x){
return P(l.s.x,s.y);
} else if(s.x==e.x){
return P(s.x,l.s.y);
}
}
}
return P(-1,-1);
}
}lines[510];
vector<pair<P,int>> critical[510];
int dirx[4] = {1,0,-1,0}; //R U L D
int diry[4] = {0,1,0,-1};
int main(){
lld N,T;
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N >> T;
for(int i=0;i<N;i++){
lld a,b,c,d;
cin >> a>>b>>c>>d;
lines[i]=L(P(a,b),P(c,d));
critical[i].push_back(make_pair(P(a,b),-1));
critical[i].push_back(make_pair(P(c,d),-1));
}
for(int i=0;i<N;i++){
for(int j=i+1;j<N;j++){
P temp = lines[i].intersect(lines[j]);
if(temp.x!=-1 && temp.y !=-1){
critical[i].push_back(make_pair(temp,j));
critical[j].push_back(make_pair(temp,i));
}
}
}
for(int i=0;i<N;i++){
sort(critical[i].begin(),critical[i].end(),[](pair<P,int> a , pair<P,int> b){return a.first<b.first;});
}
int line=0;
lld time=0;
int dir;
P startpos = lines[0].s;
P last=startpos;
for(int i=0;i<4;i++){
if((lines[0].e-lines[0].s)*(P(dirx[i],diry[i]))>0){
dir=i; break;
}
}
vector<pair<lld,P>> seq;
seq.push_back(make_pair(time,startpos));
while (true){
//cout << time << ' '<< last.x<< ' '<<last.y<<endl;
auto p = lower_bound(critical[line].begin(),critical[line].end(),make_pair(last,-1),[](pair<P,int> a , pair<P,int> b){return a.first<b.first;});
lld dot = P(dirx[dir],diry[dir]) * (lines[line].e-lines[line].s);
if(dot==0){
cout << "error!";
return -1;
} else if(dir<=1){
p = p+1;
} else if(dir>=2){
p = p-1;
}
if(p>=critical[line].end() || p<critical[line].begin()) return -1;
P temp = (p->first) - last;
time += (abs(temp.x)+abs(temp.y));
if(p->second==-1){
dir= (dir+2)%4;
} else{
dir= (dir+1)%4;
line = p->second;
}
last = p->first;
seq.push_back(make_pair(time,last));
if(last == startpos){
break;
}
}
T = T%time;
auto p =upper_bound(seq.begin(),seq.end(),make_pair(T,P()),[](pair<lld,P> a, pair<lld,P> b){return a.first<b.first;})-1;
if((p+1)>=seq.end() || p<seq.begin()) return -1;
int lastdir;
for(int i=0;i<4;i++){
if(((p+1)->second - p->second)*(P(dirx[i],diry[i]))>0){
lastdir=i; break;
}
}
T -= p->first;
cout << p->second.x + T*dirx[lastdir] << ' '<<p->second.y + T*diry[lastdir];
}여기까지가 (비교적 쉬운) 문제들이다. 이외의 문제들은 추후 두 번째 게시글에서 작성하겠다.
'알고리즘' 카테고리의 다른 글
| ICPC Seoul Regional 2020 풀어보기 - 2 (0) | 2022.01.28 |
|---|
