1. 계단
첫인상은 무난한 수학 문제였으나 WA를 6번 받고 나서 생각이 바뀌었다. 풀이의 방향을 조금 바꿔서 무난하게 시뮬레이션 코드를 작성했더니 맞았다.
풀이
엘리베이터의 이용을 최소화하려면 한 번의 이용으로 최대한 많은 계단을 올라가야 한다.
따라서, 오르고 싶은 계단이 넉넉히 남았을 때는 엘리베이터를 타고 $1$층으로 내려간 뒤 $M$층까지 계단으로 올라가는 것이 최적이다.
이를 직관적으로 모델링해보자.
$0-based$ 의 $M$칸 배열이 있다. $F-1$에서 출발하여 오른쪽으로 $N$번 이동한다. ($M-1$의 오른쪽에는 $0$이 있다고 하자.)
엘리베이터를 타는 횟수는 $M-1$에서 $0$으로 이동하는 횟수와 같다. 물론 $N$번 이동에 $M-1$에서 $0$으로 가는 것은 포함되지 않는다.
이런 식으로 이동했을 때 마지막에 위치한 곳을 $X$라 하자. 이때 $X$가 $F-1$ 보다 작거나 같다면 엘리베이터를 더 이용할 필요가 없다. 마지막에 $M-1$에서 $0$이 아닌 적절한 곳으로 가면 되기 때문이다. 하지만 $X$가 $F-1$보다 크다면 엘리베이터를 한 번 더 이용해서 $F-1$에 가야 한다.
while 문은 많아봤자 한두 번 돌아가므로 시간 복잡도는 $O(1)$.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int m,f,n; cin >> m >> f >> n; f--;
int x=f+n, k=0;
while(1){
int dk=x/m; x%=m;
x+=dk, k+=dk;
if(x<m) break;
}
cout << k+(x>f);
}
2. 레이스 기록 검증
작년과 비슷한 구현 문제가 나왔다. $N, M$의 범위를 작게 줄 필요가 있었을까?
풀이
출발 시간을 저장하면서 조건들을 잘 처리해주면 된다. 시간이 $0$부터 들어올 수 있으므로 이 부분만 조심해주자. 시간 복잡도는 $O(N+M)$.
#include<bits/stdc++.h>
using namespace std;
#define no return cout <<"NO", 0
#define yes return cout <<"YES", 0
const int N=101;
int a[N];
int main()
{
memset(a,-1,sizeof a);
int n,m; cin >> n >> m;
while(m--){
int t,i,s; cin >> t >> i >> s;
if(a[i]<0){
if(s) no;
a[i]=t;
}
else{
if(!s) no;
if(t-a[i]<60) no;
a[i]=-1;
}
}
for(int i=1;i<=n;i++) if(a[i]>=0) no;
yes;
}
3. 근무표 짜기
어디서 본 듯한 스케줄링 문제이다. 그리디적인 사고와 우선순위 큐만 있다면 풀 수 있다. 사실 범위가 작아서 우선순위 큐 없이도 해결 가능하다.
풀이
출근 날 수가 많이 남은 개발자가 먼저 출근하는 것이 최적이다. 따라서 모든 개발자의 정보를 우선순위 큐에 넣고 각 날마다 출근할 개발자를 필요한 만큼 꺼내오면 된다. 시간 복잡도는 $O(KNlogN)$.
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
int main()
{
int n,k; cin >> n >> k;
priority_queue<pii> pq;
for(int i=1;i<=n;i++){
int x; cin >> x;
pq.push({x,i});
}
for(int i=1;i<=k;i++){
int x; cin >> x;
vector<pii> v;
while(x--){
if(!pq.top().X) break;
v.push_back(pq.top()); pq.pop();
}
cout << v.size() << ' ';
for(auto p : v) cout << p.Y << ' ', pq.push({p.X-1,p.Y});
cout << '\n';
}
}
4. 파티
자료형을 잘못 써서 두 번 틀렸는데 풀이의 정당성에 문제가 있는 줄 알았다..
풀이
'돈을 가장 많이 사용한 친구와 가장 적게 사용한 친구의 금액 차이가 1인 것까지는 허용한다'는 조건으로 인해, '돈을 가장 적게 사용한 친구가 내는 돈'을 $K$라 했을 때 $K$를 내는 친구의 수와 $K+1$을 내는 친구의 수가 결정된다.
돈을 주고 받는 과정에서 돈이 어떻게 이동하는지는 중요하지 않다. 문제를 해결하기 위해 필요한 정보는 '전달 전과 전달 후의 돈의 차이' 뿐이다. 이 차이들을 모두 더한 후 2로 나눈 값은 전달된 돈의 총 금액과 같다. (이를 가능하게 하는 전달 방법은 항상 존재한다.)
전달된 돈의 총 금액을 최소화하기 위해서는 친구들의 '전달 전과 전달 후의 돈의 차이'의 합을 최소화해야 한다. 이는 친구들이 낸 비용을 정렬했을 때, 돈을 적게 낸 친구가 $K$를 내고, 돈을 많이 낸 친구가 $K+1$을 내는 경우에서 최소가 된다. 증명은 아마 exchange argument로 할 수 있다.
시간 복잡도는 정렬에 지배적이므로 $O(NlogN)$.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,sum=0; cin >> n;
vector<ll> v(n+1);
for(int i=1;i<=n;i++){
cin >> v[i];
sum+=v[i];
}
sort(v.begin()+1,v.end());
ll p=sum/n, q=sum%n;
ll ans=0;
for(int i=1;i<=n;i++){
if(i<=n-q) ans+=abs(v[i]-p);
else ans+=abs(v[i]-(p+1));
}
cout << ans/2;
}
5. 페인트 칠하기
시뮬레이션 문제가 생각보다 쉬워서 당황했다. 대신 노다가해서 풀기는 많이 힘들어 보인다.
풀이
색칠하는 과정을 거꾸로 생각해보자. 마지막에는 어떤 한 줄이 같은 색으로 칠해져 있을 것이다. 이 줄을 지우고 나면 또 같은 색으로 칠해진 줄이 존재하고, 또 이 줄을 지우면 $\cdots $ . 이 과정을 색칠된 칸이 없어질 때까지 반복하면 된다. 내 구현의 시간 복잡도는 $O(NMK)$.
저장하는 것을 까먹었다! ㅜㅜ
답을 스택처럼 저장해야 한다는 것만 신경 쓰면, 귀찮긴 하더라도 어렵지 않게 구현하실 수 있습니다.
6. 폭탄 터트리기
2회차 문제 중 가장 늦게 해결했다. 하지만 그 정도로 어렵진 않은데, 스위핑으로 풀릴 거라는 잘못된 생각에서 늦게 빠져나온 것이 원인이었다.
여담으로 이 문제의 풀이를 쓰던 중에 갑자기 재채점이 시작되어서 이걸 계속 써야 하나 말아야 하나 고민했으나, 다행히 터지지 않았다. ㅎ
풀이
폭탄의 값이 중복되지 않는다고 가정하자. 값이 가장 작은 폭탄은 다른 폭탄에 의해서 터질 수 없다. 그럼 언젠가 본인이 터져야 하는데, 이왕이면 빨리 터지는 것이 다른 폭탄을 터트릴 가능성도 있어서 이득이다. 따라서 현재 남은 폭탄 중 값이 가장 작은 폭탄을 고르고 이를 터트리는 것이 최적이다. 이 과정을 우선순위 큐를 이용해 구현하면 시간 내에 들어온다. 시간 복잡도는 $O(NlogN)$.
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int n,k; cin >> n >> k;
vector<int> a(n+1);
priority_queue<pii,vector<pii>,greater<pii>> pq;
for(int i=1;i<=n;i++) cin >> a[i], pq.push({a[i],i});
int ans=0;
while(!pq.empty()){
auto [x,i]=pq.top(); pq.pop();
if(!a[i]) continue;
ans++;
for(int j=i;j>=1;j--){
if(!a[j]||a[j]-x>k) break;
a[j]=0;
}
for(int j=i+1;j<=n;j++){
if(!a[j]||a[j]-x>k) break;
a[j]=0;
}
}
cout << ans;
}
7. 루트가 많은 트리?
트리에서 중요한 관찰을 하고 DFS 몇 번 돌려주면 풀리는, 어떻게 보면 전형적인(?) 문제다. 트리 몇 개 그려보니 풀이가 금방 나왔다.
풀이
어떤 노드가 유방향 트리의 루트가 될 수 있으려면, 그 노드를 루트로 하는 트리를 그렸을 때 모든 화살표가 리프를 향해야 한다.
따라서, $u\rightarrow v$ 일 때 $\rightarrow $ 기준으로 $u$쪽 노드는 루트의 후보이며, $v$쪽 노드는 루트가 될 수 없다.
유방향 트리의 루트가 될 수 있는 노드는 모든 화살표에 대한 루트의 후보의 교집합이다. $1\rightarrow 4 : \left \{ 1, 2, 3, 5, 6, 7 \right \}, 2\rightarrow 5 : \left \{ 1, 2, 3, 4, 6, 7 \right \}, 3\rightarrow 7 : \left \{ 1, 2, 3, 4, 5, 6 \right \}$ 이므로 이의 교집합인 $\left \{ 1, 2, 3, 6 \right \}$ 은 루트가 될 수 있는 노드의 집합이다.
먼저, 트리에 화살표가 하나도 없다면 모든 노드가 유방향 트리의 루트가 될 수 있다.
화살표가 시작되는 임의의 한 노드를 루트로 잡고 트리를 만들자. 루트의 서브 트리 중 루트를 향하는 화살표가 있는 서브 트리의 개수를 $t$라 하자.
$t$가 $2$ 이상이라면 루트 후보 노드의 교집합이 $0$이므로 유방향 트리를 만들 수 없다.
$t$가 $0$이라면 현재 루트와 무방향으로 연결된 모든 노드가 유방향 트리의 노드가 될 수 있다.
$t$가 $1$이라면 그 서브 트리에서 화살표가 시작되는 부분을 루트로 잡고 다시 트리를 만들 수 있다. 루트와 서브 트리 사이의 관계에 따라 케이스를 잘 처리했다면, 새로 만든 트리는 $t$가 0이 되고 위와 같은 방법으로 답을 구할 수 있다.
시간 복잡도는 입력과 트리 순회에 걸리는 $O(N)$인데... 이제 보니 fastio를 안 했다. ㅋㅋ
#include<bits/stdc++.h>
using namespace std;
#define exit cout << 0, exit(0)
const int N=3e5+1;
struct edge { int v,t; };
vector<edge> ad[N];
struct info { int t,sz,v; };
info dfs(int u,int p) {
info ret={0,1,0};
for(auto [v,t] : ad[u]) if(v^p){
if(t==0){
auto tmp=dfs(v,u);
ret.sz+=tmp.sz;
if(tmp.t){
if(ret.t) exit;
else ret.t=1, ret.v=tmp.v;
}
}
if(t==1) if(dfs(v,u).t) exit;
if(t==2){
if(ret.t) exit;
auto tmp=dfs(v,u);
if(tmp.t) ret.t=1, ret.v=tmp.v;
else ret.t=1, ret.v=v;
}
}
return ret;
}
int main()
{
int n,r=0; cin >> n;
for(int i=1;i<n;i++){
int u,v,t; cin >> u >> v >> t;
if(t){
ad[u].push_back({v,1});
ad[v].push_back({u,2});
r=u;
}
else{
ad[u].push_back({v,0});
ad[v].push_back({u,0});
}
}
if(!r) return cout << n, 0;
auto ret=dfs(r,0);
if(ret.t) cout << dfs(ret.v,0).sz;
else cout << ret.sz;
}
8. 영역 나누기
첫 문장을 보자마자 이 문제가 떠올랐고, 실제로 비슷한 아이디어로 풀렸다. 글을 쓰다가 정해에 가까운 코드도 발견했다.
풀이
영역의 개수를 세는 것은 쉽지 않다. 그래서 이 원을 $v-e+f=2$ 가 성립하는 평면 그래프로 생각할 수 있다.
먼저, 원에 겹치지 않는 $N$개의 현을 그리자. 그럼 이 그래프는 $v=2N, e=3N, f=N+2$ 가 성립한다.
두 현이 교차하는 상황을 생각하자. $v$는 $+1$ , $e$는 $+2$ 이므로 $f$는 $+1$ 이다.
따라서 원 내부의 교차점의 수를 $K$라 하면 잘린 평면의 수는 $N+2+K$, 원 내부의 영역의 수는 $N+1+K$가 된다.
이제 원 내부의 최대 교차점의 수를 구하자. 두 현이 교차할 조건은 두 현의 꼭짓점의 위치 관계로부터 얻을 수 있다.
두 현의 꼭짓점을 각각 $(a, b)$ , $(c, d)$ $(a<b, c<d, a<c)$ 라 하면 두 현이 교차할 조건은 $a<c<b<d$ 이다.
사실 원 내부의 최대 교차점의 수는 교차하는 현의 쌍 수와 같다. 원 위의 점의 위치를 적절히 조절하면 세 현이 한 점에서 만나지 않도록 만들 수 있기 때문이다. 따라서 교차하는 현의 쌍의 수만 빠르게 구할 수 있으면 된다.
모든 현을 매칭시키는 방법으로는 $O(N^{2})$를 넘을 수 없다. 모든 현을 (각 점에 $1\sim 2N$ 의 번호를 붙였을 때) 번호가 작은 순서대로 정렬하자.
$i$번째 현 $(a_{i}, b_{i})$ 와 교차하는 현의 수는 $a_{i}<b_{j}<b_{i}$ $(j<i)$ 인 $j$의 수와 같다. 이는 구간 합을 빠르게 관리하는 자료구조(세그먼트 트리, 펜윅 트리) 를 이용해 구할 수 있다. 나는 섭테가 $N\leq 50000$ 과 $N\leq 500000$ 로 분리된 것이 불안해서 비교적 빠른 펜윅 트리를 사용했다. 시간 복잡도는 $O(NlogN)$.
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long ll;
const int N=5e5+1;
int n,m;
pii p[N];
int tree[N<<1];
void update(int i) {
for(;i<=m;i+=i&-i) tree[i]++;
}
int query(int i) {
int ret=0;
for(;i;i-=i&-i) ret+=tree[i];
return ret;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin >> n; m=2*n;
for(int i=1;i<=m;i++){
int x; cin >> x;
if(p[x].X) p[x].Y=i;
else p[x].X=i;
}
sort(p+1,p+n+1);
ll ans=n+1;
for(int i=1;i<=n;i++){
ans+=query(p[i].Y-1)-query(p[i].X);
update(p[i].Y);
}
cout << ans;
}
9. K-좀비
미션10 시뮬레이터를 열었을 때는 진짜 CRT인 줄 알고 식겁했다. 정신을 차리고 BFS를 짰는데, 방문 체크를 하지 않아 꼬박 1시간을 디버깅했다. 참고로, 미션 10의 답이 정확히 100,000번이다.
풀이
시간축을 더한 그래프 탐색에 좀비의 주기에 대한 조건만 추가하면 풀린다. 각 칸에 들어갈 수 있는 시간은 인접한 좀비들의 주기의 최소공배수로 전처리하고 시작하는 것이 깔끔하다.
#include<bits/stdc++.h>
using namespace std;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
char d[4]={'U','R','D','L'};
int n,m;
char a[27][27]; int v[27][27];
bool vst[27][27][100001];
int gcd(int a,int b) { for(;b;a%=b,swap(a,b)); return a; }
int lcm(int a,int b) { return a*b/gcd(a,b); }
struct node { int x,y; string s; };
bool in(int x,int y) { return 1<=x&&x<=n&&1<=y&&y<=m; }
int num(char c) { return c<'2'||c>'9'?0:c-'0'; }
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
char c; cin >> c; a[i][j]=c;
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
v[i][j]=1;
for(int d=0;d<4;d++){
int nx=i+dx[d],ny=j+dy[d];
if(!in(nx,ny)) continue;
int k=num(a[nx][ny]);
if(k) v[i][j]=lcm(v[i][j],k);
}
}
queue<node> q;
q.push({1,1,""});
while(!q.empty()){
auto [x,y,s]=q.front(); q.pop();
int t=s.size();
if(vst[x][y][t]) continue; vst[x][y][t]=1;
if(x==n&&y==m){
cout << t << '\n' << s;
break;
}
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(!in(nx,ny)) continue;
if(a[nx][ny]=='.'&&(t+1)%v[nx][ny]==0)
q.push({nx,ny,s+d[i]});
}
}
}
10. 다양성이 힘이다
머지 소트 트리를 쓰면 풀리는 줄 알고 새로 공부했는데, 알고 보니 그렇게 쉬운 문제가 아니었다.
풀이
절댓값의 합은 원소의 크기 순서가 결정되어야 계산하기 편하다. $(x_{1}, x_{2}, \cdots , x_{k})$ 가 정렬되어 있다고 가정하고 이 팀의 실력을 구해보자.
$|x_{2}-x_{1}|+|x_{3}-x_{1}|+\cdots +|x_{n}-x_{1}|+|x_{3}-x_{2}|+\cdots +|x_{n}-x_{n-1}|$
$= (x_{2}-x_{1})+(x_{3}-x_{1})+\cdots +(x_{n}-x_{1})+(x_{3}-x_{2})+\cdots +(x_{n}-x_{n-1})$
$= (-k+1)x_{1}+(-k+3)x_{2}+\cdots +(k-3)x_{k-1}+(k-1)x_{k}$
$= (-k+1)(x_{1}+x_{2}+\cdots +x_{k})+2(x_{2}+2x_{3}+\cdots (k-1)x_{k})$
$= (-k-1)(x_{1}+x_{2}+\cdots +x_{k})+2(x_{1}+2x_{2}+\cdots kx_{k})$
이제 가능한 모든 구간에 대해 원소를 정렬하고 식의 값을 계산하면 $O(KNlogK)$ 시간에 해결할 수 있고, 25점을 받는다.
더 빠른 풀이를 위해서는 앞에서 계산한 값을 재활용해야 한다.
$(x_{1}, x_{2}, \cdots , x_{k})$에 대한 식을 계산했을 때, $(x_{2}, x_{3}, \cdots , x_{k+1})$에 대한 식을 계산하는 과정을 '$x_{1}$이 수열에서 빠지는 것'과 '$x_{k+1}$이 수열에 추가되는 것'으로 나눌 수 있다. $x_{1}$이 빠지는 상황에서는 $(x_{1}+x_{2}+\cdots +x_{k})$의 값이 $x_{1}$ 만큼 감소하며, $(x_{1}+2x_{2}+\cdots kx_{k})$의 값은 $x_{1}*\sum_{i=1}^{k}(x_{i}\leq x_{1})+\sum_{x_{1}\leq x_{i}} x_{i}$ 만큼 감소한다. $x_{k+1}$이 추가되는 상황도 비슷하다.
이 쿼리는 수열 $X$를 좌표압축한 다음 구간의 개수와 구간의 합을 관리하는 자료구조를 사용해 처리할 수 있다. 나는 펜윅 트리를 이용했다. 시간 복잡도는 $O(NlogN)$.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+1;
int n,k; ll x[N],xx[N],idx[N],t[N];
struct Fenwick {
ll tree[N];
void update(int i,ll v) {
for(;i<=n;i+=i&-i) tree[i]+=v;
}
ll query(int i) {
ll ret=0;
for(;i;i-=i&-i) ret+=tree[i];
return ret;
}
} cnt, sum;
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin >> n >> k;
for(int i=1;i<=n;i++) cin >> x[i], xx[i]=x[i];
sort(xx+1,xx+n+1);
for(int i=1;i<=n;i++){
int j=lower_bound(xx+1,xx+n+1,x[i])-xx;
idx[i]=j+(t[j]++);
}
ll a=0,b=0;
for(int i=1;i<=k;i++){
a+=x[i];
cnt.update(idx[i],1);
b+=x[i]*cnt.query(idx[i]);
b+=sum.query(n)-sum.query(idx[i]);
sum.update(idx[i],x[i]);
}
ll ans=(-k-1LL)*a+2*b;
for(int i=k+1;i<=n;i++){
a-=x[i-k];
b-=x[i-k]*cnt.query(idx[i-k]);
b-=sum.query(n)-sum.query(idx[i-k]);
cnt.update(idx[i-k],-1);
sum.update(idx[i-k],-x[i-k]);
a+=x[i];
cnt.update(idx[i],1);
b+=x[i]*cnt.query(idx[i]);
b+=sum.query(n)-sum.query(idx[i]);
sum.update(idx[i],x[i]);
ans=max(ans,(-k-1LL)*a+2*b);
}
cout << ans;
}
11. 원룸 구하기
솔직히 다 직선 위에 올려서 정렬 후 스위핑하고 싶게 생겼지만 어림도 없었고, 이번에도 세그가 등장했다.
풀이
일단 투포인터를 이용해 $K$종류의 가게가 전부 존재하는 모든 구간을 구할 수 있다. 여기서 구한 구간은 다음과 같은 특징을 가진다.
1. 구간의 왼쪽 위치로만 만든 수열은 순증가수열이고, 이는 구간의 오른쪽 위치로만 만든 수열도 마찬가지다.
2. (1로 인해) 구간은 겹칠 수 있지만 포함되지는 않는다.
원룸의 위치 $x$에 대해 필수 생활 거리에 포함될 가능성이 있는 구간은 다음과 같다.
1. 구간의 오른쪽 위치가 $x$보다 작은 구간 중 가장 오른쪽에 위치한 구간
2. 구간의 왼쪽 위치가 $x$보다 큰 구간 중 가장 왼쪽에 위치한 구간
3. $x$를 포함하는 구간
3-1. 3에 해당하는 구간 중 가장 왼쪽에 위치한 구간은 구간의 오른쪽 위치가 $x$ 이상인 구간 중 가장 왼쪽에 위치한 구간이다.
3-2. 3에 해당하는 구간 중 가장 오른쪽에 위치한 구간은 구간의 왼쪽 위치가 $x$ 이하인 구간 중 가장 오른쪽에 위치한 구간이다.
1, 2, 3-1, 3-2에 해당하는 구간을 각각 이분탐색으로 찾을 수 있다. 1, 2는 $O(1)$, 3은 최솟값 세그를 이용해 $O(logN)$에 필수 생활 거리를 구할 수 있다. 각 상황이 성립하는지에 대한 반례를 주의해서 처리할 필요가 있다.
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+1;
int n,k,q;
struct info {
int x,t;
bool operator < (const info &op) const {
if(x!=op.x) return x<op.x;
return t<op.t;
}
} a[N];
int cnt[N],kk;
struct lr { int l,r; };
vector<lr> v;
vector<int> tree;
int mn(int l,int r) {
int ret=2e9+1;
for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
if(l&1) ret=min(ret,tree[l++]);
if(!(r&1)) ret=min(ret,tree[r--]);
}
return ret;
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k >> q;
for(int i=1;i<=n;i++) cin >> a[i].x >> a[i].t;
sort(a+1,a+n+1);
int l=1,r=0;
while(r<=n){
while(kk<k&&r<n){
if(!cnt[a[++r].t]) kk++;
cnt[a[r].t]++;
}
if(r==n&&kk<k) break;
while(kk>=k){
if(cnt[a[l].t]==1) kk--;
cnt[a[l++].t]--;
}
v.push_back({a[l-1].x,a[r].x});
}
n=v.size(); tree.resize(n<<1);
for(int i=0;i<n;i++) tree[n+i]=v[i].r-v[i].l;
for(int i=n-1;i>0;i--) tree[i]=min(tree[i<<1],tree[i<<1|1]);
while(q--){
int x; cin >> x;
if(x<v[0].l){
cout << v[0].r-x << '\n';
continue;
}
if(v[n-1].r<x){
cout << x-v[n-1].l << '\n';
continue;
}
int ret=2e9+1;
if(v[0].r<x){
int lo=0,hi=n-1;
while(lo+1<hi){
int mi=lo+hi>>1;
if(v[mi].r<x) lo=mi;
else hi=mi;
}
ret=min(ret,x-v[lo].l);
}
if(x<v[n-1].l){
int lo=0,hi=n-1;
while(lo+1<hi){
int mi=lo+hi>>1;
if(x<v[mi].l) hi=mi;
else lo=mi;
}
ret=min(ret,v[hi].r-x);
}
int s=0,e=n-1;
if(v[0].r<x){
int lo=0,hi=n-1;
while(lo+1<hi){
int mi=lo+hi>>1;
if(x<=v[mi].r) hi=mi;
else lo=mi;
}
s=hi;
}
if(x<v[n-1].l){
int lo=0,hi=n-1;
while(lo+1<hi){
int mi=lo+hi>>1;
if(v[mi].l<=x) lo=mi;
else hi=mi;
}
e=lo;
}
if(v[s].l<=x) ret=min(ret,mn(s,e));
cout << ret << '\n';
}
}
12. 생존 신호
지금 글을 쓰는 와중에도 열심히 긁고 있다. Naive한 랜덤 코드를 돌려서 근사해를 구하고, 이를 손으로 최적화하는 식으로 노가다하면 생각보다 점수가 잘 오른다. 지금 90점 정도까지 긁었는데 아마 여기가 한계인 것 같다.
- 정해는 Connection Profile DP 라고 한다..
풀이
'완성된 격자판에는 사이클이 생기지 않고, 서로 다른 레이저 구간은 만날 수는 있으나 겹치지 않는다.' 까지 밖에 관찰을 못했다. 그래서 정해는 잘 모르겠고, 대신 내 랜덤 코드의 발전 과정을 소개하겠다.
처음에는 백트래킹을 통해 모든 '?'칸을 채우고 출발점을 다르게 하여 매번 dfs를 돌리는 순수 Naive 코드를 작성했다. 이 구현의 시간 복잡도는 $O(NMK5^{NM})$이고, '|', '-' 를 후보에서 제외하면 $O(NMK3^{NM})$까지 내릴 수 있다. 그런데 사실 이 구현의 디테일을 신경쓰기가 만만치 않다. 나는 2시간을 짜고 2시간을 디버깅해서 겨우 코드를 완성시켰다. 미션 7까지는 '?'의 수가 많지 않아서 답이 잘 나오지만, 그 이상은 실행 시간을 대충 계산해봐도 대회 전에 결과가 나올 것 같지 않다.
백트래킹을 통해 '?'칸을 채우는 모든 경우를 시도해보는 것은 너무 느리다. '?'칸을 랜덤으로 채워넣은 후 답을 갱신하는 과정을 충분히 반복하면 근사해를 얻을 수 있지 않을까? 대충 분석해보면 '.' : '/' : '\' = 1 : 2 : 2 정도의 비율일 떄 답이 잘 나오므로 이 비율을 랜덤에 반영해줄 수 있다. 실제로 랜덤을 이용했을 때가 백트래킹을 돌릴 때보다 훨씬 빠른 속도로 점수가 높은 답을 찾는 것을 확인할 수 있었다. 휴리스틱을 개선하는 방안으로는 답금질 기법이라고 불리는 Simulate Annealing이 있다. 랜덤을 돌리는 과정을 SA에 맞게 바꾸고 상수를 적당히 설정해주면 최적해에 더 가까운 근사해를 얻을 수 있지 않을까 기대했는데, 적당한 상수를 찾기도 어려웠고 최적해에 가까워지는 속도도 그냥 랜덤을 돌릴 때보다 느렸다. 그래서 단순 휴리스틱을 다듬어서 실행하고, 적당히 나온 근사해를 손으로 최적화하는 과정을 반복하였더니 90.4점까지 얻을 수 있었다.
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
int n,m,k;
char a[15][25];
vector<pii> tmp,st;
vector<int> t;
int mx=-1;
void update(pii p,int s) {
mx=s;
cout << '\n' << mx << '\n';
cout << (p.Y==0?0:p.Y==m+1?2*m:2*p.Y-1) << ' '
<< (p.X==0?0:p.X==n+1?2*n:2*p.X-1) << '\n';
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cout << a[i][j];
cout << '\n';
}
}
void go(pii p,int x,int y,int d,int s) {
if(a[x][y]=='@') return;
if(a[x][y]=='.'){
int dx=(d==0?-1:d==2?1:0);
int dy=(d==1?1:d==3?-1:0);
x+=dx,y+=dy,s+=2;
while(1<=x&&x<=n&&1<=y&&y<=m){
if(a[x][y]!='.') { go(p,x,y,d,s); return; }
x+=dx,y+=dy,s+=2;
}
if(a[x][y]=='o'&&mx<s) update(p,s);
return;
}
if(a[x][y]=='|'){
if((d&1)&&mx<=s) update(p,s+1);
return;
}
if(a[x][y]=='-'){
if(!(d&1)&&mx<=s) update(p,s+1);
return;
}
if(a[x][y]=='/'){
int dx=(d==1?-1:d==3?1:0);
int dy=(d==0?1:d==2?-1:0);
int dd=(d<1?1:d<2?0:d<3?3:2);
x+=dx,y+=dy,s+=2;
while(1<=x&&x<=n&&1<=y&&y<=m){
if(a[x][y]!='.') { go(p,x,y,dd,s); return; }
x+=dx,y+=dy,s+=2;
}
if(a[x][y]=='o'&&mx<s) update(p,s);
return;
}
if(a[x][y]=='\\'){
int dx=(d==1?1:d==3?-1:0);
int dy=(d==0?-1:d==2?1:0);
int dd=(d<1?3:d<2?2:d<3?1:0);
x+=dx,y+=dy,s+=2;
while(1<=x&&x<=n&&1<=y&&y<=m){
if(a[x][y]!='.') { go(p,x,y,dd,s); return; }
x+=dx,y+=dy,s+=2;
}
if(a[x][y]=='o'&&mx<s) update(p,s);
return;
}
}
void bt(int idx) {
if(idx==t.size()){
for(int i=0;i<idx;i++)
a[tmp[i].X][tmp[i].Y]=(t[i]?t[i]<2?'/':'\\':'.');
for(int i=0;i<k;i++){
int x=st[i].X,y=st[i].Y,d=0;
if(x==0) x=1,d=2; if(x==n+1) x=n,d=0;
if(y==0) y=1,d=1; if(y==m+1) y=m,d=3;
go(st[i],x,y,d,0);
}
return;
}
for(int i=0;i<3;i++) t[idx]=i, bt(idx+1);
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin >> n >> m;
for(int i=0;i<=n+1;i++) for(int j=0;j<=m+1;j++){
if(1<=i&&i<=n&&1<=j&&j<=m){
char c; cin >> c; a[i][j]=c;
if(c=='?') tmp.push_back({i,j});
}
else a[i][j]='x';
}
cin >> k;
for(int i=0;i<k;i++){
int x,y; cin >> y >> x;
x=x?x/2+1:0, y=y?y/2+1:0;
st.push_back({x,y}); a[x][y]='o';
}
t.resize(tmp.size());
bt(0);
}#include<bits/stdc++.h>
#include<random>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
int n,m,k;
char a[15][25];
vector<pii> que,st;
int mx=-1;
void update(pii p,int s) {
mx=s;
cout << '\n' << mx << '\n';
cout << (p.Y==0?0:p.Y==m+1?2*m:2*p.Y-1) << ' '
<< (p.X==0?0:p.X==n+1?2*n:2*p.X-1) << '\n';
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cout << a[i][j];
cout << '\n';
}
}
void go(pii p,int x,int y,int d,int s) {
if(a[x][y]=='@') return;
if(a[x][y]=='.'){
int dx=(d==0?-1:d==2?1:0);
int dy=(d==1?1:d==3?-1:0);
x+=dx,y+=dy,s+=2;
while(1<=x&&x<=n&&1<=y&&y<=m){
if(a[x][y]!='.') { go(p,x,y,d,s); return; }
x+=dx,y+=dy,s+=2;
}
if(a[x][y]=='o'&&mx<s) update(p,s);
return;
}
if(a[x][y]=='|'){
if((d&1)&&mx<=s) update(p,s+1);
return;
}
if(a[x][y]=='-'){
if(!(d&1)&&mx<=s) update(p,s+1);
return;
}
if(a[x][y]=='/'){
int dx=(d==1?-1:d==3?1:0);
int dy=(d==0?1:d==2?-1:0);
int dd=(d<1?1:d<2?0:d<3?3:2);
x+=dx,y+=dy,s+=2;
while(1<=x&&x<=n&&1<=y&&y<=m){
if(a[x][y]!='.') { go(p,x,y,dd,s); return; }
x+=dx,y+=dy,s+=2;
}
if(a[x][y]=='o'&&mx<s) update(p,s);
return;
}
if(a[x][y]=='\\'){
int dx=(d==1?1:d==3?-1:0);
int dy=(d==0?-1:d==2?1:0);
int dd=(d<1?3:d<2?2:d<3?1:0);
x+=dx,y+=dy,s+=2;
while(1<=x&&x<=n&&1<=y&&y<=m){
if(a[x][y]!='.') { go(p,x,y,dd,s); return; }
x+=dx,y+=dy,s+=2;
}
if(a[x][y]=='o'&&mx<s) update(p,s);
return;
}
}
mt19937 gen(504);
uniform_real_distribution<double> rnd(0,1);
void query() {
for(auto &q : que){
double tmp=rnd(gen);
a[q.X][q.Y]=(tmp<0.2?'.':tmp<0.6?'/':'\\');
}
for(int i=0;i<k;i++){
int x=st[i].X,y=st[i].Y,d=0;
if(x==0) x=1,d=2; if(x==n+1) x=n,d=0;
if(y==0) y=1,d=1; if(y==m+1) y=m,d=3;
go(st[i],x,y,d,0);
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin >> n >> m;
for(int i=0;i<=n+1;i++) for(int j=0;j<=m+1;j++){
if(1<=i&&i<=n&&1<=j&&j<=m){
char c; cin >> c; a[i][j]=c;
if(c=='?') que.push_back({i,j});
}
else a[i][j]='x';
}
cin >> k;
for(int i=0;i<k;i++){
int x,y; cin >> y >> x;
x=x?x/2+1:0, y=y?y/2+1:0;
st.push_back({x,y}); a[x][y]='o';
}
while(1) query();
}#include<bits/stdc++.h>
#include<random>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
int n,m,k,sz;
char a[15][25];
vector<pii> que,st;
int mx=-1,now=-1;
void update(pii p,int s) {
mx=s;
cout << '\n' << mx << '\n';
cout << (p.Y==0?0:p.Y==m+1?2*m:2*p.Y-1) << ' '
<< (p.X==0?0:p.X==n+1?2*n:2*p.X-1) << '\n';
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cout << a[i][j];
cout << '\n';
}
}
void go(pii p,int x,int y,int d,int s) {
if(a[x][y]=='@'){ now=max(now,s); return; }
if(a[x][y]=='.'){
int dx=(d==0?-1:d==2?1:0);
int dy=(d==1?1:d==3?-1:0);
x+=dx,y+=dy,s+=2;
while(1<=x&&x<=n&&1<=y&&y<=m){
if(a[x][y]!='.') { go(p,x,y,d,s); return; }
x+=dx,y+=dy,s+=2;
}
if(a[x][y]=='o'&&mx<s) update(p,s);
now=max(now,s); return;
}
if(a[x][y]=='|'){
if((d&1)&&mx<=s) update(p,s+1);
now=max(now,s); return;
}
if(a[x][y]=='-'){
if(!(d&1)&&mx<=s) update(p,s+1);
now=max(now,s); return;
}
if(a[x][y]=='/'){
int dx=(d==1?-1:d==3?1:0);
int dy=(d==0?1:d==2?-1:0);
int dd=(d<1?1:d<2?0:d<3?3:2);
x+=dx,y+=dy,s+=2;
while(1<=x&&x<=n&&1<=y&&y<=m){
if(a[x][y]!='.') { go(p,x,y,dd,s); return; }
x+=dx,y+=dy,s+=2;
}
if(a[x][y]=='o'&&mx<s) update(p,s);
now=max(now,s); return;
}
if(a[x][y]=='\\'){
int dx=(d==1?1:d==3?-1:0);
int dy=(d==0?-1:d==2?1:0);
int dd=(d<1?3:d<2?2:d<3?1:0);
x+=dx,y+=dy,s+=2;
while(1<=x&&x<=n&&1<=y&&y<=m){
if(a[x][y]!='.') { go(p,x,y,dd,s); return; }
x+=dx,y+=dy,s+=2;
}
if(a[x][y]=='o'&&mx<s) update(p,s);
now=max(now,s); return;
}
}
mt19937 gen(504);
uniform_real_distribution<double> rnd(0,1);
uniform_int_distribution<int> rndi(0,2e9);
void query(int i1,int i2,int i3) {
if(~i1){
a[que[i1].X][que[i1].Y]="./\\"[rndi(gen)%3];
a[que[i2].X][que[i2].Y]="./\\"[rndi(gen)%3];
a[que[i3].X][que[i3].Y]="./\\"[rndi(gen)%3];
}
else{
for(auto &q : que){
double tmp=rnd(gen);
a[q.X][q.Y]=(tmp<0.2?'.':tmp<0.6?'/':'\\');
}
}
now=0;
for(int i=0;i<k;i++){
int x=st[i].X,y=st[i].Y,d=0;
if(x==0) x=1,d=2; if(x==n+1) x=n,d=0;
if(y==0) y=1,d=1; if(y==m+1) y=m,d=3;
go(st[i],x,y,d,0);
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin >> n >> m;
for(int i=0;i<=n+1;i++) for(int j=0;j<=m+1;j++){
if(1<=i&&i<=n&&1<=j&&j<=m){
char c; cin >> c; a[i][j]=c;
if(c=='?') que.push_back({i,j});
}
else a[i][j]='x';
}
sz=que.size();
cin >> k;
for(int i=0;i<k;i++){
int x,y; cin >> y >> x;
x=x?x/2+1:0, y=y?y/2+1:0;
st.push_back({x,y}); a[x][y]='o';
}
query(-1,-1,-1);
double t=1,d=0.99999999999,kv=100,lim=0.0000000000001;
while(t>lim){
double e1=2*(n+1)*(m+1)-now;
int i1=rndi(gen)%sz,i2=rndi(gen)%sz,i3=rndi(gen)%sz;
char c1=a[que[i1].X][que[i1].Y];
char c2=a[que[i2].X][que[i2].Y];
char c3=a[que[i3].X][que[i3].Y];
query(i1,i2,i3);
double e2=2*(n+1)*(m+1)-now;
double p=exp((e1-e2)/(kv*t));
if(p<rnd(gen)){
a[que[i1].X][que[i1].Y]=c1;
a[que[i2].X][que[i2].Y]=c2;
a[que[i3].X][que[i3].Y]=c3;
}
t*=d;
}
}
13. 선물 상자
개인적으로 3회차 문제들보다 쉬웠다.
풀이
$N$과 $D$의 범위를 보면 $O(N^2)$ 풀이가 정해라는 것을 예상할 수 있다. 원에 남아 있는 아이들의 인덱스를 잘 관리해주면 $O(N)$ 시간에 가장 먼저 빠지는 아이를 구할 수 있고, 이를 $N$번 반복하면 선물 상자를 받는 아이를 찾을 수 있다.
#include<bits/stdc++.h>
using namespace std;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int N,m; cin >> N >> m;
vector<int> a(N);
for(int i=0;i<N;i++) cin >> a[i];
int t=N-1;
for(int n=N;n>=1;n--){
vector<int> v,vv;
for(int i=1;i<=N;i++) if(a[(t+i)%N]) v.push_back((t+i)%N);
int k=(m-1)%n;
for(int i=k;;){
vv.push_back(v[i]);
i=(i+m)%n; if(i==k) break;
}
t=vv[0]; int idx=0;
for(int i=1;i<vv.size();i++) if(a[t]>a[vv[i]]) t=vv[i],idx=i;
int val=a[t];
for(int i=0;i<=idx;i++) a[vv[i]]-=val;
for(int i=idx+1;i<vv.size();i++) a[vv[i]]-=val-1;
}
cout << t+1;
}
14. 파스칼 삼각형
전처리를 해서 갖다 박는 다소 무식한 풀이로 38점을 받았다. 정해는 많이 더럽다.
풀이
하키스틱 정리를 응용하면 삼각형의 합을 $\binom{a+c-1}{b}+\binom{a+c-1}{b+1}+\cdots +\binom{a+c-1}{b+c-2}+\binom{a-1}{b-1}$ 로 정리할 수 있다. 이 식과 $c\leq log_{2}K$ 일 때만 가능함을 적용하면 Naive한 $O(N^{2}logN)$ 컷팅 풀이가 나오고 이를 로컬에서 구한 뒤 전처리하여 해결할 수 있다. 출력해보면 알겠지만, 답이 4인 수가 상당히 많아서 이를 따로 처리해줘야 코드 길이를 줄일 수 있다. (코드 길이 제한이 있는지는 모르겠음)
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const ull K=1e6;
short cnt[K+1];
map<pii,ull> dp;
ull C(int n,int r) {
if(r<0||n<r) return 0;
if(r==0||n==r) return 1;
if(dp[{n,r}]) return dp[{n,r}];
return dp[{n,r}]=C(n-1,r-1)+C(n-1,r);
}
ull f(int a,int b,int c) {
ull ret=C(a-1,b-1);
for(int i=b;i<=b+c-2;i++) ret+=C(a+c-1,i);
return ret;
}
int main()
{
for(int c=1;c<20;c++)
for(int a=1;a<=K+1;a++){
ull x=f(a,1,c);
if(x>K) break;
cnt[x]+=1+(a>1);
for(int b=2;b<=(a+1)/2;b++){
x+=C(a-1,b-1)-C(a-1,b-2);
x+=C(a+c-1,b+c-2)-C(a+c-1,b-1);
if(x>K) break;
if((a&1)&&a+1==2*b) cnt[x]++;
else cnt[x]+=2;
}
}
vector<int> v[11];
for(int i=2;i<=K;i++) v[cnt[i]].push_back(i);
for(int i=1;i<=10;i++){
if(i==4) continue;
cout << i << " : ";
for(auto &x : v[i]) cout << x << ',';
cout << '\n';
}
}/*
K<=8,000 일 때의 코드
K<=1,000,000 일 때도 같은 방법으로 해결 가능
*/
#include<bits/stdc++.h>
using namespace std;
const int K=8001;
int a[K];
int main()
{
a[1]=-1, a[2]=1, a[3]=3;
vector<int> v={6,7,8,20,31,52,63,70,90,114,127,240,252,255,272,322,426,511,692,918,924,994,1004,1023,1604,1920,2026,2047,2578,3432,3518,3684,3944,4072,4356,6076,7456};
for(auto &x : v) a[x]=5;
v={10,11,13,16,19,21,28,29,34,35,36,37,38,42,43,46,53,55,57,60,66,67,71,78,79,84,91,92,93,94,99,103,106,118,121,130,134,137,148,151,153,154,158,161,163,165,169,171,176,190,191,201,208,211,213,219,220,225,228,229,231,247,253,254,256,265,266,274,276,277,286,295,298,299,300,301,323,325,326,330,341,346,349,352,364,374,379,381,382,386,404,406,407,414,430,433,435,436,455,459,462,463,465,470,495,496,502,523,526,528,529,533,557,559,560,561,572,576,588,593,595,596,597,615,628,630,631,632,638,651,664,666,667,680,693,697,701,703,704,715,739,741,742,751,778,780,781,785,789,792,794,802,816,818,820,821,830,834,841,859,861,862,880,901,903,904,936,944,946,947,960,968,969,978,984,990,991,1001,1002,1013,1018,1024,1033,1035,1036,1046,1079,1081,1082,1088,1093,1105,1126,1128,1129,1140,1156,1160,1174,1177,1221,1223,1225,1226,1273,1275,1276,1287,1289,1293,1324,1326,1327,1330,1347,1351,1365,1371,1376,1378,1379,1420,1429,1431,1432,1434,1466,1471,1479,1483,1485,1501,1535,1538,1541,1558,1562,1580,1586,1594,1596,1597,1617,1653,1654,1709,1711,1712,1716,1730,1759,1768,1770,1790,1794,1808,1816,1820,1828,1830,1831,1842,1886,1889,1891,1892,1936,1941,1951,1953,1954,1972,2002,2014,2016,2017,2024,2036,2044,2048,2078,2080,2081,2122,2143,2145,2146,2178,2184,2209,2211,2212,2255,2267,2276,2278,2279,2300,2321,2324,2325,2344,2346,2347,2374,2413,2415,2416,2452,2458,2483,2485,2486,2497,2503,2510,2512,2517,2553,2554,2556,2557,2600,2622,2628,2629,2699,2701,2702,2773,2775,2776,2835,2848,2850,2851,2876,2924,2925,2926,2927,2948,2952,3001,3004,3038,3060,3079,3081,3082,3151,3158,3160,3161,3168,3209,3213,3214,3225,3240,3241,3276,3294,3300,3302,3304,3319,3321,3322,3401,3403,3404,3412,3467,3473,3484,3486,3487,3568,3570,3571,3601,3620,3653,3654,3655,3656,3679,3683,3718,3728,3739,3741,3742,3788,3795,3797,3802,3826,3828,3829,3876,3914,3916,3917,3981,4003,4006,4007,4017,4032,4043,4048,4060,4083,4086,4089,4090,4093,4184,4186,4187,4276,4278,4279,4368,4369,4371,4372,4438,4463,4465,4466,4495,4522,4526,4556,4558,4560,4561,4588,4654,4656,4657,4751,4753,4754,4849,4851,4852,4878,4901,4938,4944,4948,4950,4951,4960,4965,4988,4992,5005,5031,5036,5048,5050,5051,5149,5151,5152,5251,5253,5254,5335,5354,5356,5357,5369,5395,5456,5458,5460,5461,5485,5489,5490,5563,5565,5566,5661,5669,5671,5672,5741,5776,5778,5779,5804,5812,5884,5886,5887,5921,5984,5985,5993,5995,5996,6014,6018,6103,6105,6106,6121,6126,6188,6191,6196,6214,6216,6217,6292,6326,6328,6329,6406,6435,6439,6441,6442,6469,6474,6476,6480,6545,6553,6555,6556,6576,6580,6668,6670,6671,6756,6784,6786,6787,6814,6879,6885,6897,6901,6903,6904,6954,7019,7021,7073,7090,7099,7138,7141,7172,7176,7258,7260,7261,7315,7379,7381,7382,7468,7501,7503,7504,7542,7547,7553,7624,7626,7627,7701,7732,7748,7750,7751,7770,7803,7804,7807,7814,7873,7875,7876,7999};
for(auto &x : v) a[x]=6;
v={15,22,76,188,494,1176,4095};
for(auto &x : v) a[x]=7;
v={45,56,64,89,105,126,136,172,210,232,251,351,376,378,497,562,848,988,1486,1540,1651,1771,1981,2380,2626,3238,4005,4096,4845,7022,7140};
for(auto &x : v) a[x]=8;
a[26]=9, a[120]=a[466]=a[3003]=10;
for(int i=0;i<K;i++) if(!a[i]) a[i]=4;
cin.tie(0)->sync_with_stdio(0);
int tc; cin >> tc;
while(tc--){
int k; cin >> k;
cout << a[k] << '\n';
}
}
15. 낙하 데미지
선분이 아니라 직선이라면 자명하게 CHT를 쓸 수 있다. 그런데 도대체 저 X축 범위를 어떻게 처리해야 되는 건지 전혀 모르겠다. 나는 세그 노드에 리차오 트리를 넣고 레이지로 비비는 코드를 짰는데 디버깅이 힘들어서 그냥 포기했다. 레이지가 잘 전파되는 것 같지도 않고..
풀이
$O(N^2)$ dp는 어렵지 않다. 높이 순서대로 정렬한 후 낮은 높이부터 답을 구해주면 된다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
struct line {
ll y,l,r,c,i;
bool operator < (line &op) {
if(y^op.y) return y<op.y;
return l<op.l;
}
};
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
vector<line> ln(n+1);
ln[0]={0,-INF,INF,0};
for(int i=1;i<=n;i++){
ll y,l,r,c; cin >> y >> l >> r >> c;
ln[i]={y,l,r,c,i};
}
sort(ln.begin(),ln.end());
vector<ll> dp(n+1,INF); dp[0]=0;
for(int i=1;i<=n;i++) for(int j=0;j<i;j++)
if(ln[j].l<=ln[i].r&&ln[i].l<=ln[j].r)
dp[i]=min(dp[i],dp[j]+(ln[i].y-ln[j].y)*(ln[i].y-ln[j].y)+ln[j].c);
vector<ll> v(n+1);
for(int i=1;i<=n;i++) v[ln[i].i]=dp[i];
for(int i=1;i<=n;i++) cout << v[i] << '\n';
}'Contest > NYPC' 카테고리의 다른 글
| NYPC 2022 본선 후기 (19) | 2022.11.01 |
|---|
