티스토리 뷰
놀고만 있던 저에게 urd05가 셋을 돌자고 제안을 했다.
그 셋은 바로 BAPC 2017
같이 푸는거라 그나마 재미가 더 있었다!
5시간동안 했는데, 너무 힘들었다. (오랜만에 몇시간 연속으로 코딩..)
간략하게 내가 아는 풀이를 적어보겠다!
플랫이 슥삭해서 나는 모른다.
플랫이 최적화 어쩌구 저쩌구 하면서 추하게 뭘 엄청 박았다.
난 뭔지 모른다.
다익스트라를 짯는데 틀렸습니다가 나왔다.
플랫이 뭘 더 어떻게 슥삭슥삭 하면 나온다고 하고 슥삭했다.
내림차순 정렬후 A_1+A_3+A_5+... , A_2+A_4+A_6+... 를 출력하면 된다.
대회때 3팀 밖에 풀지 못했는데, 내 생각에는 뒤에 있는 문제는 더 어려울 것이라 생각해서 앞에 문제들을 잡고 있다가 못 본거 같다.
sx < ex, sy < ey 이라면, (sx,sy) -> (ex,ey) 로 갈때 심부름 들을 x좌표로 정렬하면
가장 긴 증가하는 부분 수열 을 구하는 문제가 된다!
이때 조심해야 할 점은, y좌표가 같은 경우에도 가능하다.
즉, A가 가장 긴 증가하는 부분 수열이라고 하면, 어떤 i에 대해 A_i <= A_i+1 이여야 한다.
x좌표로 정렬하고 좌표 압축을 한 후에 lis를 구하면 된다.
이때 조심해야 할 점은, x좌표가 같다면 y좌표가 작은 것 부터 넣는다.
sx > ex, sy > ey 인 경우에도 똑같다.
이제, sx < ex, sy > ey 인 경우에는 생각해보면
가장 긴 감소하는 부분 수열을 구하는 문제가 된다!
sx > ex, sy < ey 인 경우에도 똑같다.
이것도 똑같은 방법으로 한다.
#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
int n;
int sx,sy,ex,ey;
pi a[100005];
vector <int> rex;
vector <int> rey;
vector <int> num[100005];
vector <int> lis;
int b[100005];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> sx >> sy >> ex >> ey;
int rn = 0,v = 0;
if(sx > ex) swap(sx,ex),swap(sy,ey);
if(sy > ey) {
v = 1;
swap(sy,ey);
}
for(int i = 1;i <= n;i++) {
int x,y;
cin >> x >> y;
if(x < sx||x > ex||y < sy||y > ey) {
rn++;
continue;
}
a[i-rn] = {x,y};
rex.push_back(x);
rey.push_back(y);
}
n -= rn;
sort(rex.begin(),rex.end()); rex.erase(unique(rex.begin(),rex.end()),rex.end());
sort(rey.begin(),rey.end()); rey.erase(unique(rey.begin(),rey.end()),rey.end());
for(int i = 1;i <= n;i++) {
a[i].x = lower_bound(rex.begin(),rex.end(),a[i].x)-rex.begin()+1;
a[i].y = lower_bound(rey.begin(),rey.end(),a[i].y)-rey.begin()+1;
num[a[i].x].push_back(a[i].y);
}
int g = 0;
for(int i = 1;i <= n;i++) {
if(!v) sort(num[i].begin(),num[i].end());
else sort(num[i].rbegin(),num[i].rend());
for(int j : num[i]) {
b[++g] = j;
}
}
if(!v) {
lis.push_back(b[1]);
for(int i = 2;i <= n;i++) {
if(lis.back() <= b[i]) lis.push_back(b[i]);
else lis[upper_bound(lis.begin(),lis.end(),b[i])-lis.begin()] = b[i];
}
}
else {
lis.push_back(b[n]);
for(int i = n-1;i >= 1;i--) {
if(lis.back() <= b[i]) lis.push_back(b[i]);
else lis[upper_bound(lis.begin(),lis.end(),b[i])-lis.begin()] = b[i];
}
}
if(n == 0) cout << 0;
else cout << lis.size();
}
내 코드는 뒤에서 부터 가장 긴 증가하는 부분 수열을 구하는 걸로 바꿨다.
케이스 분류를 해보자.
i) p = 1
이때는 내가 맘대로 자를 수 있다.
그래서 q가 홀수 일때는, 그냥 다 가져가는게 이득이고 (답 : 1)
짝수 일때는, 1개빼고 다 가져가는게 이득이다. (답 : 2)
ii) q = 1
이때는 여동생이 모든걸 가져가는 것만이 최소이므로
p 가 홀수 일때 (답 : 1)
짝수 일때 (답 : 0) 이다.
iii) p > 1, q > 1, p is even
내가 어떻게 가져가도 여동생이 남은 모든걸 가져가면 둘다 0이 된다. (답 : 0)
iV) p > 1, q > 1, p is odd, q is odd
내가 홀수개의 열을 끊는다고 하면, 여동생이 남은걸 다 가져가 버린다. (나 : 1, 여동생 : 0)
짝수개의 열을 끊는다고 하면, 여동생이 남은걸 다 가져가 버린다. (나 0 : 여동생 : 1)
그러므로 답은 1이다.
V) p > 1, q > 1, p is odd, q is even
최적의 방법으로 플레이 할때는 맨 처음 내가 한줄 가져가고
그 다음 서로 2줄씩 가져가는 것이다.
그러면, 먼저 2줄을 가져갈 수가 없는 사람에 따라 결과가 달라진다.
ㄱ) 내가 가져갈 수가 없는 경우 (p >= q)
여동생이 1개빼고 다 가져가면, 나는 0점, 여동생도 0점이 된다. (답 : 0)
ㄴ) 여동생이 가져갈 수가 없는 경우 (p < q)
내가 1개빼고 다 가져가면, 나는 1점, 여동생은 -1점이 된다. (답 : 2)
#include <bits/stdc++.h>
using namespace std;
int main() {
int p,q;
cin >> p >> q;
if(p == 1) cout << 2-q%2;
else if(q == 1) cout << p%2;
else {
if(p % 2 == 0) cout << 0;
else if(q % 2) cout << 1;
else cout << 2*(p < q);
}
}
잘 생각을 해보면, A[i][j] 가 1일때, i -> j로 가는 간선을 잇는다.
만드면 이제 루트에서 모든 정점을 갈 수 있는지 판별하자.
만약 모든 정점을 갈 수 있다면, PostOrder 로 선택을 해보면 가능 한 경우가 나온다.
갈 수 없다면, 불가능 하다.
(매우 설명이 부실하다..)
#include <bits/stdc++.h>
using namespace std;
int n,c[1005],cnt;
vector <int> v[1005];
char str[1005];
void dfs(int x,int pr) {
if(c[x]) return;
c[x] = 1; cnt++;
for(int i : v[x]) dfs(i,pr);
if(pr) cout << x-1 << ' ';
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i = 1;i <= n;i++) {
cin >> str+1;
for(int j = 1;j <= n;j++) {
if(i == j) continue;
if(str[j] == '1') v[i].push_back(j);
}
}
dfs(1,0);
if(cnt != n) {
cout << "impossible";
return 0;
}
memset(c,0,sizeof(c));
dfs(1,1);
}
레몬에이드를 적절히 잘 교환해보자.
long double 같은데에 담으면, 최대 2^100000 까지 될 수 있으므로, 담을때 log2 로 담아보자.
그러면, 최대 10만까지 담을 수 있고, 소수차이는 믿음을 가지고 짰는데, 맞아서 기분이 좋았다.
#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#define x first
#define y second
using namespace std;
typedef long double ld;
typedef pair<int,int> pi;
int n;
map <string,int> name;
string str1,str2;
ld x;
ld ans[100005],INF = 1e18;
struct GG {
int x,y;
ld g;
}a[100005];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
int g = 2;
name["pink"] = 1;
name["blue"] = 2;
for(int i = 1;i <= n;i++) {
cin >> str1 >> str2 >> x;
if(name.find(str1) == name.end()) name[str1] = ++g;
if(name.find(str2) == name.end()) name[str2] = ++g;
a[i].x = name[str1];
a[i].y = name[str2];
a[i].g = x;
}
for(int i = 1;i <= g;i++) ans[i] = -INF;
ans[1] = log2(1.0);
for(int i = 1;i <= n;i++) {
if(ans[a[i].y] == -INF) continue;
ans[a[i].x] = max(ans[a[i].x],ans[a[i].y]+log2(a[i].g));
}
if(ans[2] > log2(10.0)) cout << "10.000000000000000";
else cout << fixed << setprecision(15) << pow(2.0,ans[2]);
}
힘들다 이렇게 BAPC 2017 글을 마친다!
- Total
- Today
- Yesterday
- 알고리즘 문제 풀이
- Rabin-Karp
- 쿼리
- Offline Dynamic Connectivity
- 1909
- 정렬
- 세그먼트 트리
- 김춘배
- PS
- 오일러 경로
- 앳코더
- Constructive
- 누적 합
- 비요뜨 존맛
- BOJ
- codeforces
- gunwookim
- 비요뜨
- 스택
- 수열과 쿼리
- 냄새 싫어
- 하이퍼
- hyper
- 간단한 풀이
- combination
- DP
- ABC
- AtCoder
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |