NYPC 2020 예선이 마무리되었습니다! 사실 NYPC 2019에도 참여했었는데 그땐 200점대 받음 ㅋㅋ;(본선 점수 아니고 예선 점수임 ㅋㅋ;) 아무튼 그때는 뉴비도 아니고 그냥 입문도 안 했을 때고 이제 1년이 지난 후에 완전히 설욕전에 성공했다. 2000점 만점에 2000점!! 기분이 너무 좋당. 아무래도 제일 어려운 문제는 메이플 월드 라이딩 여행이었던 거 같은데 추하게 비빈 게 겨우 성공해서 만점을 받을 수 있었다. (버킷 크기 바꿔가며 9개 동시 제출했는데 한 개만 맞았다.) 그래서 풀이를 적어보려고 한다. 예선 잘 쳤으니까 본선도 잘 치겠지?
1. S OR T
(1) 100점 풀이
시간복잡도 : O(N)
그냥 하라는대로 짜면 됩니다.
#include <bits/stdc++.h>
using namespace std;
char str[100001];
int main() {
scanf("%s",str);
int now=0;
int n=strlen(str);
for(int i=0;i<n;i++) {
if (str[i]=='S') {
now++;
}
else {
now=(now/4+1)*4;
}
}
printf("%d",now);
return 0;
}2. 카트라이더 별 모으기
(1) 100점 풀이
시간복잡도 : O(N)
이것도 그냥 하라는대로 짜면 됩니다. ez
#include <bits/stdc++.h>
using namespace std;
int t1,t2,t3;
int main() {
int a,b,c;
scanf("%d:%d:%d\n",&a,&b,&c);
t1=a*6000+b*100+c;
scanf("%d:%d:%d\n",&a,&b,&c);
t2=a*6000+b*100+c;
scanf("%d:%d:%d\n",&a,&b,&c);
t3=a*6000+b*100+c;
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) {
int a,b,c;
scanf("%d:%d:%d\n",&a,&b,&c);
int t=a*6000+b*100+c;
if (t1<t) {
printf(":(\n");
continue;
}
int ret=0;
if (t1>=t) {
ret++;
}
if (t2>=t) {
ret++;
}
if (t3>=t) {
ret++;
}
for(int j=0;j<ret;j++) {
printf("*");
}
printf("\n");
}
return 0;
}3. 스피드전 할까 아이템전 할까
(1) 100점 풀이
시간복잡도 : O(T)
그냥 하라는대로 각각의 경우의 승리여부를 판별해주고 케이스대로 출력해주면 됩니다.
#include <bits/stdc++.h>
using namespace std;
int a[4];
int b[4];
int main() {
int tc;
scanf("%d",&tc);
for(int t=0;t<tc;t++) {
int asum=0;
int amax=0;
for(int i=0;i<4;i++) {
scanf("%d",&a[i]);
asum+=a[i];
amax=max(amax,a[i]);
}
int bsum=0;
int bmax=0;
for(int i=0;i<4;i++) {
scanf("%d",&b[i]);
bsum+=b[i];
bmax=max(bmax,b[i]);
}
if (asum>bsum&&amax<=bmax) {
printf("S");
}
else if (asum<=bsum&&amax>bmax) {
printf("I");
}
else {
printf("R");
}
printf("\n");
}
}4. 실력별 매칭
(1) 100점 풀이
시간복잡도 : O(N)
실력점수가 가장 가까운 K명은 실력순으로 연속일 것이 자명합니다. 그리고 최솟값과 S의 차이, 최댓값과 S의 차이를 생각해주면 최솟값과 S의 차이와 최댓값과 S의 차이가 뒤바뀌는 그 시점 주변에 답이 존재할 것을 알 수 있습니다. 변수를 움직이면서 구현해주면 되고, 모든 수가 S보다 크거나 작을 때를 조심합시다.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
P arr[500000];
int main() {
int n;
scanf("%d",&n);
int s,k;
scanf("%d %d",&s,&k);
for(int i=0;i<n;i++) {
scanf("%d",&arr[i].first);
arr[i].second=i;
}
sort(arr,arr+n);
int l,r;
if (arr[n-1].first>=s) {
auto iter=lower_bound(arr,arr+n,P(s,-1));
if (iter!=arr&&s-(*prev(iter)).first<=(*iter).first-s) {
iter--;
}
l=iter-arr;
r=iter-arr;
}
else {
auto iter=arr+n-1;
l=n-1;
r=n-1;
}
int now=1;
while (now<k) {
if (r!=n-1&&(l==0||arr[r+1].first-s<s-arr[l-1].first)) {
r++;
}
else {
l--;
}
now++;
}
for(int i=l;i<=r;i++) {
printf("%d ",arr[i].second+1);
}
}
5. 우승자 찾기
(1) 100점 풀이
시간복잡도 : O(NK)
자기보다 시작을 빠르게 하지 않았는데 자기보다 빨리 들어온 경우가 있으면 그 바퀴에서 1등을 차지할 수는 없습니다. 아닌 경우에는 차이를 어떻게든 극단적으로 조절해서 자신의 그 바퀴를 1등으로 만들 수 있습니다. 앞부분에서 동시에 출발했음에 주의해야합니다.
#include <bits/stdc++.h>
using namespace std;
int arr[10001];
vector<int> pos[1001];
int cnt[1001];
int main() {
int n,k;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++) {
pos[i].push_back(0);
}
for(int i=1;i<=k;i++) {
scanf("%d",&arr[i]);
pos[arr[i]].push_back(i);
}
vector<int> ret;
for(int i=1;i<=n;i++) {
if (pos[i].size()==1) {
continue;
}
bool flag=false;
for(int j=1;j<pos[i].size();j++) {
bool temp=true;
for(int l=pos[i][j-1]+1;l<pos[i][j];l++) {
cnt[arr[l]]++;
if (cnt[arr[l]]>=2||(j==1&&cnt[arr[l]]==1)) {
temp=false;
}
}
for(int l=pos[i][j-1]+1;l<pos[i][j];l++) {
cnt[arr[l]]--;
}
if (temp) {
flag=true;
break;
}
}
if (flag) {
ret.push_back(i);
}
}
printf("%d\n",ret.size());
for(int i=0;i<ret.size();i++) {
printf("%d ",ret[i]);
}
}
6. 도토리를 주워라
(1) 100점 풀이
시간복잡도 : O(N^2)
시뮬레이터를 직접 돌려보던가 해보면 가로로 연결된 컴포넌트 하나에 있는 도토리는 좌우로 움직이면서 다 먹는 것이 맞다는 걸 알 수 있습니다. 가로로 연결된 컴포넌트 하나씩을 정점으로 하고 거기에 존재하는 도토리 개수를 가중치로 둡니다. 이 그래프는 DAG이기 때문에 dp를 돌릴 수 있습니다. 그렇게 나오는 답을 하나하나 넣어주면 됩니다.
#include <bits/stdc++.h>
using namespace std;
int num[50][50];
int val[2500];
int dp[2500];
char arr[50][50];
int n;
int sz=0;
vector<int> adj[2500];
bool valid(int x,int y) {
return x>=0&&x<n&&y>=0&&y<n;
}
int ans(int v) {
if (v==sz-1) {
return val[v];
}
if (dp[v]!=-1) {
return dp[v];
}
int ret=-1e6;
for(int i=0;i<adj[v].size();i++) {
ret=max(ret,val[v]+ans(adj[v][i]));
}
dp[v]=ret;
return ret;
}
int main() {
scanf("%d\n",&n);
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
scanf("%c",&arr[i][j]);
}
scanf("\n");
}
for(int i=0;i<n;i++) {
int now=0;
while (now<n) {
if (arr[i][now]!='U') {
while (now<n&&arr[i][now]!='U') {
if (arr[i][now]=='D') {
val[sz]++;
}
num[i][now]=sz;
now++;
}
sz++;
}
else {
now++;
}
}
}
for(int i=0;i<n-1;i++) {
for(int j=0;j<n;j++) {
if (arr[i][j]!='U'&&arr[i+1][j]!='U') {
adj[num[i][j]].push_back(num[i+1][j]);
}
}
}
memset(dp,-1,sizeof(dp));
int x=0;
int y=0;
while (1) {
while (y!=n-1&&arr[x][y+1]!='U') {
printf("R");
y++;
}
while (y!=0&&arr[x][y-1]!='U') {
printf("L");
y--;
}
if (x==n-1) {
while (y!=n-1&&arr[x][y+1]!='U') {
printf("R");
y++;
}
return 0;
}
while (1) {
if (arr[x+1][y]!='U'&&ans(num[x+1][y])+val[num[x][y]]==ans(num[x][y])) {
printf("D");
x++;
break;
}
printf("R");
y++;
}
}
}
7. 난센스 퀴즈
(1) 100점 풀이
시간복잡도 : O(T)
스택 계산기를 구현해서 풀 수 있습니다. 근데 구현해보니 뭔가 20가지 케이스분류 노가다가 더 빠를 거 같습니다...
#include <bits/stdc++.h>
using namespace std;
char str[6];
long double solve() {
stack<long double> s;
stack<char> sp;
for(int i=4;i>=0;i--) {
if (i%2==0) {
s.push(str[i]-'0');
}
else {
sp.push(str[i]);
}
}
stack<long double> rs;
stack<char> rsp;
while (!sp.empty()) {
long double now=s.top();
s.pop();
char p=sp.top();
sp.pop();
if (p=='.') {
long double nt=s.top();
s.pop();
s.push(now+0.1*nt);
}
else {
rs.push(now);
rsp.push(p);
}
}
while (!rs.empty()) {
s.push(rs.top());
rs.pop();
}
while (!rsp.empty()) {
sp.push(rsp.top());
rsp.pop();
}
while (!sp.empty()) {
long double now=s.top();
s.pop();
char p=sp.top();
sp.pop();
if (p=='*') {
long double nt=s.top();
s.pop();
s.push(now*nt);
}
else if (p=='/') {
long double nt=s.top();
s.pop();
s.push(now/nt);
}
else {
rs.push(now);
rsp.push(p);
}
}
while (!rs.empty()) {
s.push(rs.top());
rs.pop();
}
while (!rsp.empty()) {
sp.push(rsp.top());
rsp.pop();
}
while (!sp.empty()) {
long double now=s.top();
s.pop();
char p=sp.top();
sp.pop();
if (p=='+') {
long double nt=s.top();
s.pop();
s.push(now+nt);
}
else if (p=='-') {
long double nt=s.top();
s.pop();
s.push(now-nt);
}
else {
rs.push(now);
rsp.push(p);
}
}
return s.top();
}
char pt[5]={'+','-','*','/','.'};
long double eps=1e-5;
int main() {
int tc;
scanf("%d",&tc);
for(int t=0;t<tc;t++) {
int a,b,c,d;
scanf("%d %d %d %d",&a,&b,&c,&d);
str[0]=a+'0';
str[2]=b+'0';
str[4]=c+'0';
bool flag=false;
for(int i=0;i<5;i++) {
for(int j=0;j<5;j++) {
if (i!=j) {
str[1]=pt[i];
str[3]=pt[j];
if (solve()>=d-eps&&solve()<=d+eps) {
printf("%d%c%d%c%d=%d\n",a,pt[i],b,pt[j],c,d);
flag=true;
break;
}
}
}
if (flag) {
break;
}
}
}
return 0;
}
8. 이어달리기
(1) 100점 풀이
시간복잡도 : O(N^3)
1등팀을 고정해줍시다. 1등팀으로 가능한 경우는 O(N^2)가지입니다. 그 후부터 투포인터 방식으로 매칭을 해줍니다. 실력이 좋은 사람부터 보면서 1등팀보다 10초 이하로 늦게 들어올 수 이는 한 가장 느린 선수를 찾아주고, 이렇게 팀을 맺으면 1등팀을 능가하면 스킵하고 아니면 매칭을 시켜주는 식으로 해주면 됩니다.
#include <bits/stdc++.h>
using namespace std;
int arr[400];
int main() {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) {
int a,b,c;
scanf("%d:%d:%d\n",&a,&b,&c);
arr[i]=6000*a+100*b+c;
}
sort(arr,arr+n);
int ret=0;
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
int now=n-1;
int sum=1;
for(int k=0;k<n;k++) {
if (k==i||k==j) {
continue;
}
if (now<=k) {
break;
}
if (arr[k]+arr[now]<arr[i]+arr[j]) {
continue;
}
while (now>k&&arr[now]+arr[k]>=arr[i]+arr[j]+1000) {
now--;
}
while (now==i||now==j) {
now--;
}
if (now<=k) {
break;
}
if (arr[k]+arr[now]<arr[i]+arr[j]) {
continue;
}
sum++;
now--;
}
ret=max(ret,sum);
}
}
printf("%d",ret);
}
9. 몰이 사냥
(1) 100점 풀이
시간복잡도 : O(NlogX)
모든 점이 0~X+R 내에 존재하면서 최댓값과 최솟값의 차이가 R 이하여야 합니다. 여기서 시간이 지나면서 바뀌는 최댓값-최솟값의 값을 살펴보면 unimodal합니다. 최댓값과 최솟값의 차이가 한 번 증가하면 그때 거리를 증가시킨 쌍은 계속해서 멀어지기 때문에 계속 최댓값과 최솟값의 차이가 증가할 수밖에 없기 때문입니다. 그러므로 삼분탐색을 적용하여 최댓값-최솟값이 최소인 지점을 찾고 그때의 최댓값-최솟값을 알아보는 식으로 구현할 수 있습니다. 모든 점이 0~X+R에 존재하게 하는 방법을 삼분탐색의 초기 lo와 hi를 이 점들이 0~X+R에 존재하는 하한과 상한으로 설정해주면 됩니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
P arr[100000];
stack<P> s;
int n;
long long getdiff(long long t) {
long long mini=4e18;
long long maxi=-4e18;
for(int i=0;i<n;i++) {
mini=min(mini,arr[i].first*t+arr[i].second);
maxi=max(maxi,arr[i].first*t+arr[i].second);
}
return maxi-mini;
}
int main() {
ll x,r;
scanf("%lld %lld",&x,&r);
scanf("%d",&n);
long long lb=0;
long long ub=3e9;
for(int i=0;i<n;i++) {
scanf("%lld %lld",&arr[i].second,&arr[i].first);
long long a=arr[i].first;
long long b=arr[i].second;
if (arr[i].first<0) {
if (x+r<b) {
lb=max(lb,(b-x-r-1)/(-a)+1);
}
if (b<0) {
printf("F");
return 0;
}
ub=min(ub,b/(-a));
}
if (arr[i].first>0) {
if (b<0) {
lb=max(lb,(-b-1)/a+1);
}
if (b>x+r) {
printf("F");
return 0;
}
ub=min(ub,(x+r-b)/a);
}
if (arr[i].first==0) {
if (b<0||b>x+r) {
printf("F");
return 0;
}
}
}
long long lo=lb;
long long hi=ub;
if (lo>hi) {
printf("F");
return 0;
}
while (lo+3<=hi) {
long long p=(lo+lo+hi)/3;
long long q=(lo+hi+hi)/3;
if (getdiff(p)<=getdiff(q)) {
hi=q;
}
else {
lo=p;
}
}
for(int i=lo;i<=hi;i++) {
if (getdiff(i)<=r) {
printf("T");
return 0;
}
}
printf("F");
}
10. 탐험 로봇
(1) 50점 풀이 (min에서의 해법)
시간복잡도 : O(NM)
?로 이루어진 컴포넌트가 있다 합시다. 이 컴포넌트가 육지와 닿아있다면, 얘를 전부 육지로 바꿔줍시다. 섬의 개수가 늘어나는 경우는 절대 없고, 오히려 다른 섬을 연결시켜 섬의 개수를 줄일 수 있기 때문입니다. 만약 이 컴포넌트가 육지와 닿아있지 않다면, 얘를 전부 바다로 바꿔줍니다. 어차피 영향을 안 미치니 굳이 섬 개수만 늘릴 필요가 없기 때문입니다.
(2) 100점 풀이 (max에서의 해법 포함)
시간복잡도 : O(N^2M^2)
max에서의 해법을 알아봅시다. 이번에도 ?로 이루어진 컴포넌트를 다룹니다. 일단 육지와 접한 지점은 모두 바다로 바꿔줍니다. 육지로 접한 지점이 육지가 되서 볼 수 있는 이득이 없습니다. 그럼 이 컴포넌트는 어느 육지와도 접하지 않게 됩니다. 여기서 Lemma 하나를 세웁니다.
Lemma1. 여기서 섬 개수를 최대로 하는 방법 중 한 개 이상은 모든 섬의 크기가 1이다.
proof1) 최대로 하는 방법 하나를 가정한 다음 거기서 각각의 섬들의 크기를 1로 줄여도 섬의 개수는 변하지 않습니다.
그러므로 우리는 이 문제를 격자그래프에서의 최대독립집합을 구하는 것으로 환원할 수 있습니다. 그런데 격자그래프는 이분그래프입니다. 이분그래프의 최대유량이 최소버텍스커버와 같음은 잘 알려져있습니다. 그리고 최대독립집합=(정점 개수)-(최소버텍스커버)이니 구할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[500];
bool visited[500];
int a[500];
int b[500];
char str[4];
char arr[1000][1000];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool v[1000][1000];
bool vis[1000][1000];
typedef pair<int,int> P;
int n,m;
int num[1000][1000];
bool dfs(int v) {
visited[v]=true;
for(int i=0;i<adj[v].size();i++) {
int next=adj[v][i];
if (b[next]==-1||(!visited[b[next]]&&dfs(b[next]))) {
a[v]=next;
b[next]=v;
return true;
}
}
return false;
}
bool valid(int x,int y) {
return x>=0&&x<n&&y>=0&&y<m;
}
void fillland(int x,int y) {
vector<P> save;
queue<P> q;
q.push(P(x,y));
v[x][y]=true;
arr[x][y]='L';
while (!q.empty()) {
P now=q.front();
q.pop();
save.push_back(now);
for(int i=0;i<4;i++) {
int nx=now.first+dx[i];
int ny=now.second+dy[i];
if (valid(nx,ny)&&arr[nx][ny]=='?'&&!v[nx][ny]) {
v[nx][ny]=true;
q.push(P(nx,ny));
arr[nx][ny]='L';
}
}
}
for(int i=0;i<save.size();i++) {
v[save[i].first][save[i].second]=false;
}
}
void fillsea(int x,int y) {
vector<P> save;
queue<P> q;
q.push(P(x,y));
v[x][y]=true;
arr[x][y]='S';
while (!q.empty()) {
P now=q.front();
q.pop();
save.push_back(now);
for(int i=0;i<4;i++) {
int nx=now.first+dx[i];
int ny=now.second+dy[i];
if (valid(nx,ny)&&arr[nx][ny]=='?'&&!v[nx][ny]) {
v[nx][ny]=true;
q.push(P(nx,ny));
arr[nx][ny]='S';
}
}
}
for(int i=0;i<save.size();i++) {
v[save[i].first][save[i].second]=false;
}
}
int countcomp() {
memset(vis,0,sizeof(vis));
int ret=0;
for(int x=0;x<n;x++) {
for(int y=0;y<m;y++) {
if (vis[x][y]||arr[x][y]=='S') {
continue;
}
queue<P> q;
ret++;
q.push(P(x,y));
vis[x][y]=true;
while (!q.empty()) {
P now=q.front();
q.pop();
for(int i=0;i<4;i++) {
int nx=now.first+dx[i];
int ny=now.second+dy[i];
if (valid(nx,ny)&&arr[nx][ny]=='L'&&!vis[nx][ny]) {
vis[nx][ny]=true;
q.push(P(nx,ny));
}
}
}
}
}
return ret;
}
int main() {
scanf("%d %d\n",&n,&m);
scanf("%s\n",str);
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
scanf("%c",&arr[i][j]);
}
scanf("\n");
}
if (strcmp(str,"min")==0) {
for(int x=0;x<n;x++) {
for(int y=0;y<m;y++) {
if (vis[x][y]||arr[x][y]!='?') {
continue;
}
queue<P> q;
vector<P> save;
q.push(P(x,y));
vis[x][y]=true;
while (!q.empty()) {
P now=q.front();
q.pop();
save.push_back(now);
for(int i=0;i<4;i++) {
int nx=now.first+dx[i];
int ny=now.second+dy[i];
if (valid(nx,ny)&&arr[nx][ny]=='?'&&!vis[nx][ny]) {
vis[nx][ny]=true;
q.push(P(nx,ny));
}
}
}
bool flag=false;
for(int i=0;i<save.size();i++) {
for(int j=0;j<4;j++) {
if (valid(save[i].first+dx[j],save[i].second+dy[j])&&arr[save[i].first+dx[j]][save[i].second+dy[j]]=='L') {
flag=true;
}
}
}
if (flag) {
fillland(x,y);
}
else {
fillsea(x,y);
}
}
}
printf("%d",countcomp());
return 0;
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if (arr[i][j]=='L') {
for(int k=0;k<4;k++) {
int x=i+dx[k];
int y=j+dy[k];
if (valid(x,y)&&arr[x][y]=='?') {
arr[x][y]='S';
}
}
}
}
}
int asz=0;
int bsz=0;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if (arr[i][j]=='?') {
if ((i+j)%2==0) {
num[i][j]=asz;
asz++;
}
else {
num[i][j]=bsz;
bsz++;
}
}
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if (arr[i][j]=='?'&&(i+j)%2==0) {
for(int k=0;k<4;k++) {
int x=i+dx[k];
int y=j+dy[k];
if (valid(x,y)&&arr[x][y]=='?') {
adj[num[i][j]].push_back(num[x][y]);
}
}
}
}
}
memset(a,-1,sizeof(a));
memset(b,-1,sizeof(b));
int ret=0;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if (arr[i][j]=='?')
arr[i][j]='S';
}
}
ret=countcomp();
ret+=asz+bsz;
for(int i=0;i<asz;i++) {
if (a[i]==-1) {
memset(visited,0,sizeof(visited));
if (dfs(i)) {
ret--;
}
}
}
printf("%d",ret);
}
11. 격자 게임
(1) 100점 풀이
시간복잡도 : O(N^4)
게임위에서 dp를 돌려줍니다. dp[i][j][k]:맵의 형태가 (i,j,k)일 때 선공이 이길 수 있는가? 로 해주고 움직일 수 있는 가능한 경우들에 대해서 선공이 지는 경우가 단 하나라도 있다면 dp[i][j][k]는 true가 됩니다. 계속 선공을 지게 만드는 쪽으로 움직여주면 됩니다. 저는 뇌절해서 그런디 수를 박았습니다. 기본적인 건 똑같습니다.
#include <bits/stdc++.h>
using namespace std;
int dp[101][101][101];
int ans(int a,int b,int c) {
if (a==0&&b==0&&c==0) {
return 1;
}
if (dp[a][b][c]!=-1) {
return dp[a][b][c];
}
bool cnt[301];
memset(cnt,0,sizeof(cnt));
for(int i=0;i<a;i++) {
cnt[ans(i,b,c)]=true;
}
for(int i=0;i<b;i++) {
cnt[ans(min(a,i),i,c)]=true;
}
for(int i=0;i<c;i++) {
cnt[ans(min(a,i),min(b,i),i)]=true;
}
for(int i=0;;i++) {
if (!cnt[i]) {
dp[a][b][c]=i;
return i;
}
}
}
typedef pair<int,int> P;
P getpos(int a,int b,int c) {
for(int i=0;i<a;i++) {
if (ans(i,b,c)==0) {
return P(1,i+1);
}
}
for(int i=0;i<b;i++) {
if (ans(min(a,i),i,c)==0) {
return P(2,i+1);
}
}
for(int i=0;i<c;i++) {
if (ans(min(a,i),min(b,i),i)==0) {
return P(3,i+1);
}
}
}
int main() {
memset(dp,-1,sizeof(dp));
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
while (1) {
P got=getpos(a,b,c);
printf("%d %d\n",got.first,got.second);
fflush(stdout);
if (got.first==1) {
a=got.second-1;
}
if (got.first==2) {
a=min(a,got.second-1);
b=min(b,got.second-1);
}
if (got.first==3) {
a=min(a,got.second-1);
b=min(b,got.second-1);
c=min(c,got.second-1);
}
int x,y;
scanf("%d %d",&x,&y);
if (x==3&&y==1) {
break;
}
if (x==1) {
a=y-1;
}
if (x==2) {
a=min(a,y-1);
b=min(b,y-1);
}
if (x==3) {
a=min(a,y-1);
b=min(b,y-1);
c=min(c,y-1);
}
}
}
12. 사회적 거리두기
(1) 100점 풀이
시간복잡도 : O(N*(1.618)^(2N))=O(N*(F(N))^2)
뭔가 딱 봐도 비트 dp를 하고 싶게 생겼습니다. 하지만 시간이 너무 오래 걸릴 거 같습니다. 하지만 잘 살펴보면 한 줄에서 보았을 때 인접한 두 위치에 체크를 할 수는 없기에 한 줄에 가능한 비트 수는 피보나치 수로 바운드됩니다. 그러므로 마음껏 전이해도 reasonable한 시간에는 답이 나올 것을 알 수 있습니다. 실제로는 바운드되는 경우가 더 많아서 답이 훨씬 더 빨리 나옵니다.
#include <bits/stdc++.h>
using namespace std;
int dp[18][262144];
int n;
int temp[18];
vector<int> save;
int arr[19][18];
int pos[18][262144];
void makearray(int ind) {
if (ind==n) {
int val=0;
for(int i=0;i<n;i++) {
val+=temp[i]*(1<<i);
}
save.push_back(val);
return;
}
if (temp[ind]==0) {
makearray(ind+1);
}
else {
if (ind!=0&&temp[ind-1]==1) {
temp[ind]=0;
makearray(ind+1);
temp[ind]=-1;
}
else {
temp[ind]=0;
makearray(ind+1);
temp[ind]=1;
makearray(ind+1);
temp[ind]=-1;
}
}
}
int ans(int ind,int bit) {
if (ind==n) {
return 0;
}
if (dp[ind][bit]!=-1) {
return dp[ind][bit];
}
int sum=0;
int ret=0;
memset(temp,-1,sizeof(temp));
for(int i=0;i<n;i++) {
if (bit&(1<<i)) {
sum++;
if (i>0) {
temp[i-1]=0;
}
temp[i]=0;
if (i<n-1) {
temp[i+1]=0;
}
}
}
ret=sum;
for(int i=0;i<n;i++) {
if (arr[ind+1][i]==1) {
temp[i]=0;
}
}
makearray(0);
vector<int> copy;
for(int i=0;i<save.size();i++) {
copy.push_back(save[i]);
}
save.clear();
pos[ind][bit]=0;
for(int i=0;i<copy.size();i++) {
if (sum+ans(ind+1,copy[i])>ret) {
pos[ind][bit]=copy[i];
ret=sum+ans(ind+1,copy[i]);
}
}
dp[ind][bit]=ret;
return ret;
}
int main(void) {
int k;
scanf("%d %d",&n,&k);
for(int i=0;i<k;i++) {
int x,y;
scanf("%d %d",&x,&y);
x--;
y--;
arr[x][y]=1;
}
memset(temp,-1,sizeof(temp));
for(int i=0;i<n;i++) {
if (arr[0][i]==1) {
temp[i]=0;
}
}
makearray(0);
vector<int> copy;
for(int i=0;i<save.size();i++) {
copy.push_back(save[i]);
}
save.clear();
memset(dp,-1,sizeof(dp));
int ret=0;
int chk=-1;
for(int i=0;i<copy.size();i++) {
if (ans(0,copy[i])>=ret) {
chk=copy[i];
ret=ans(0,copy[i]);
}
}
printf("%d\n",ret);
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if (chk&(1<<j)) {
printf("%d %d\n",i+1,j+1);
}
}
chk=pos[i][chk];
}
}
13. 물풍선 아티스트
(1) 100점 풀이
시간복잡도 : O(NlogN)
물풍선을 쏠 수 있는 위치는 무조건 그림 내입니다. 그리고 그림을 벗어나지 않는 한 물풍선을 가장 강하게 쏘는 것이 이득입니다. 그러므로 물풍선을 가장 강하게 쏘았을 때 그림이 완성되는지를 보면 됩니다. 물풍선의 세기를 dp로 정해주고, 이것이 그림을 다 완성할 수 있는지도 다른 방향에서 날아오는 물줄기를 dp를 이용하여 고려해줄 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> Pi;
int dp[1000000][4];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
vector<P> v;
int nt[1000000][4];
vector<Pi> press;
P pos[1000000];
int ans(int ind,int type) {
if (dp[ind][type]!=-1) {
return dp[ind][type];
}
if (nt[ind][type]==-1) {
dp[ind][type]=0;
return 0;
}
dp[ind][type]=ans(nt[ind][type],type)+1;
return dp[ind][type];
}
int dp2[1000000][4];
int ans2(int ind,int type) {
if (dp2[ind][type]!=-1) {
return dp2[ind][type];
}
int ret=0;
ret=min({ans(ind,0),ans(ind,1),ans(ind,2),ans(ind,3)});
if (nt[ind][(type+2)%4]!=-1) {
ret=max(ret,ans2(nt[ind][(type+2)%4],type)-1);
}
dp2[ind][type]=ret;
return ret;
}
int main(void) {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) {
int x,y;
scanf("%d %d",&x,&y);
press.push_back(Pi(P(x,y),i));
pos[i]=P(x,y);
}
sort(press.begin(),press.end());
for(int i=0;i<n;i++) {
for(int j=0;j<4;j++) {
Pi now=*lower_bound(press.begin(),press.end(),Pi(P(pos[i].first+dx[j],pos[i].second+dy[j]),-1));
if (now.first!=P(pos[i].first+dx[j],pos[i].second+dy[j])) {
nt[i][j]=-1;
}
else {
nt[i][j]=now.second;
}
}
}
memset(dp,-1,sizeof(dp));
memset(dp2,-1,sizeof(dp2));
int ret=0;
for(int i=0;i<n;i++) {
int val=min({ans(i,0),ans(i,1),ans(i,2),ans(i,3)});
if (val>0) {
ret++;
}
bool flag=false;
if (val>0) {
flag=true;
}
for(int j=0;j<4;j++) {
if (nt[i][(j+2)%4]!=-1) {
if (ans2(nt[i][(j+2)%4],j)!=0) {
flag=true;
}
}
}
if (!flag) {
printf("-1");
return 0;
}
}
printf("%d\n",ret);
for(int i=0;i<n;i++) {
int val=min({ans(i,0),ans(i,1),ans(i,2),ans(i,3)});
if (val>0) {
printf("%d %d %d\n",pos[i].first,pos[i].second,val);
}
}
}
14. 공격 상황 시뮬레이션
(1) 100점 풀이
시간복잡도 : O(NlogN)
y좌표가 작은 순서부터 보면 선수가 있어서는 안 되는 '금지영역'이 점점 생겨남을 알 수 있습니다. 이때 좌표계를 x,y단위가 아니라 A와 B 각각과의 각도 두 개로 치환해줍시다. 그러면 '금지영역'은 이차원 직사각형 형태가 됩니다. 합집합이 계단 형태로 나오기 때문에 set으로 관리해줄 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define double __float128
typedef pair<int,int> P;
P arr[300000];
bool ycomp(P a,P b) {
return a.second<b.second;
}
typedef pair<double,double> p;
int main(void) {
int n,a,b;
scanf("%d %d %d",&n,&a,&b);
for(int i=0;i<n;i++) {
int x,y;
scanf("%d %d",&x,&y);
arr[i]=P(x,y);
}
sort(arr,arr+n,ycomp);
set<p> s;
s.insert(p(-1e10,1e10));
s.insert(p(1e10,-1e10));
int ret=0;
for(int i=0;i<n;i++) {
double x=((double)(arr[i].first-a))/arr[i].second;
double y=((double)(b-arr[i].first))/arr[i].second;
p pt=p(x,y);
auto iter=s.lower_bound(pt);
if ((*iter).second>=y) {
continue;
}
iter--;
while (iter!=s.begin()&&(*iter).second<y) {
s.erase(iter--);
}
ret++;
s.insert(pt);
}
printf("%d",ret);
}
15. 메이플 월드 라이딩 여행
(1) 54점 풀이
시간복잡도 : O(K^2logX)
답이 x 이하일 수 있는지 이분탐색을 해줍니다. 그러면 dfs를 돌리면서 거리가 x 이하가 될 정점만 방문해주면서 k개를 방문할 수 있는지 체크해주면 됩니다. 방문하는 정점 수는 k개로 바운드가 되지만, 한 점을 여러 번 방문할 수 있기 때문에 차수가 큰 정점에서 계속 간선을 확인만 하고 방문을 안 하면 시간만 걸려서 시간복잡도가 O(KMlogX)가 되어 TLE가 납니다. 간선을 가중치순으로 정렬하여 거리가 x 초과가 되는 순간 그냥 break를 해주는식으로 하면 그것을 없애줄 수 있습니다. 하지만 방문한 정점을 재확인하면서 걸리는 시간은 어쩔 수 없기 때문에 그걸로 K개의 정점에서 O(K)의 시간을 쓴다면 한 번 확인에 O(K^2)이 걸리고 O(K^2logX)가 시간복잡도가 됩니다.
(2) 100점 풀이
시간복잡도 : O(Ksqrt(M)logX)
앞의 풀이가 오래 걸리는 근본적인 이유는 차수가 큰 정점에서 방문한 정점에 대해서도 간선을 계속 확인하는 걸 반복하기 때문입니다. 그렇다면 차수가 큰 정점에서는 이미 방문된 정점에 대한 간선을 일시적으로 지워버린다면 어떨까요? 시간을 꽤 절약할 수 있을 것입니다.
물론 이걸 어떻게 하나 싶습니다. 이걸 구현하는 방법은 인접 리스트를 정말로 리스트를 이용하여 구현해주면 됩니다. 어떤 점을 방문할 때 '차수가 큰' 정점에서 그 정점으로 가는 간선을 리스트에서의 삭제를 이용해 지워줄 수 있습니다. 각 정점마다 자신으로 들어오는 간선이 어느 위치에 있는지는 저장해둬야 될 것입니다. 그리고 스택에 간선을 지우는 변화를 쌓아뒀다가 그 정점의 방문이 끝났을 때 다시 복구시켜주면 됩니다.
그렇다면 '차수가 큰'을 어떻게 정의해야 문제를 풀 수 있을까요? 'sqrt(M) 이상' 정도로 정의해주면 적절합니다. 차수가 sqrt(M) 이상인 정점은 sqrt(M)개 이하이고 한 번 점을 방문했을 때 무의미한 간선을 보는 횟수도 sqrt(M) 이하로 제한되기 때문에 점을 한 번 방문했을 때 걸리는 시간이 O(sqrt(M))이 됩니다! 그럼 시간복잡도가 O(Ksqrt(M)logX)가 됩니다.
물론 이 숫자도 꽤 큰 숫자입니다. 약 14억 정도 됩니다. 하지만 시간제한은 4초이기때문에 프라그마를 박고 '차수가 큰'의 정의를 sqrt(M) 근처에서 계속 바꿔주면 AC를 받을 수 있습니다. 저는 그 정의를 100,200,300,400,500,1000,2000,3000,5000으로 하여 9번 동시에 제출했고 오직 2000에서만 AC를 받았습니다.
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long,int> P;
typedef pair<P,P> PP;
int n,m,k,s;
bool visited[100000];
int deg[100000];
const int buck=2000;
vector<P> er[100000];
long long lim;
int cnt=0;
struct Node {
int pr; //in linked list
int nt;
int next_node; //in graph
int dist;
};
stack<PP> st; //PP(P(pr,nt),P(point,index))
vector<Node> adj[100000];
void dfs(int v,long long d) {
visited[v]=true;
cnt++;
if (cnt>=k) {
visited[v]=false;
return;
}
PP tag=st.top();
for(int i=0;i<er[v].size();i++) {
if (!visited[er[v][i].first]) {
int nt=er[v][i].first;
int ind=er[v][i].second;
if (adj[nt][ind].pr!=-1) {
int now=adj[nt][ind].pr;
st.push(PP(P(adj[nt][now].pr,adj[nt][now].nt),P(nt,now)));
adj[nt][now].nt=adj[nt][ind].nt;
}
if (adj[nt][ind].nt!=-1) {
int now=adj[nt][ind].nt;
st.push(PP(P(adj[nt][now].pr,adj[nt][now].nt),P(nt,now)));
adj[nt][now].pr=adj[nt][ind].pr;
}
}
}
int now=adj[v][0].nt;
while (now!=-1) {
int nt=adj[v][now].next_node;
if (d+adj[v][now].dist>lim) {
break;
}
if (!visited[nt]) {
dfs(nt,d+adj[v][now].dist);
if (cnt>=k) {
break;
}
}
now=adj[v][now].nt;
}
while (st.top()!=tag) {
adj[st.top().second.first][st.top().second.second].pr=st.top().first.first;
adj[st.top().second.first][st.top().second.second].nt=st.top().first.second;
st.pop();
}
visited[v]=false;
}
bool ycomp(P a,P b) {
return a.second<b.second;
}
bool comp(Node a,Node b) {
return a.dist<b.dist;
}
bool isp(long long d) {
memset(visited,0,sizeof(visited));
lim=d;
cnt=0;
dfs(s,0);
return cnt>=k;
}
int main(void) {
st.push(PP(P(-1,-1),P(-1,-1)));
scanf("%d %d %d %d",&n,&m,&k,&s);
s--;
for(int i=0;i<n;i++) {
adj[i].push_back({-1,-1,-1,-1});
}
for(int i=0;i<m;i++) {
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
u--;
v--;
adj[u].push_back({-1,-1,v,w});
deg[u]++;
}
for(int i=0;i<n;i++) {
sort(adj[i].begin(),adj[i].end(),comp);
for(int j=0;j<adj[i].size();j++) {
adj[i][j]={(j==0?-1:j-1),(j+1==adj[i].size()?-1:j+1),adj[i][j].next_node,adj[i][j].dist};
}
}
for(int i=0;i<n;i++) {
if (deg[i]>=buck) {
for(int j=1;j<adj[i].size();j++) {
er[adj[i][j].next_node].push_back(P(i,j));
}
}
}
if (k==1) {
printf("0");
return 0;
}
long long lo=0; //impossible
long long hi=1e14; //possible
if (!isp(hi)) {
printf("-1");
return 0;
}
while (lo+1<hi) {
long long mid=(lo+hi)/2;
if (isp(mid)) {
hi=mid;
}
else {
lo=mid;
}
}
printf("%lld",hi);
}
16. 덕분에 챌린지
X의 시간이 걸리는 사람을 type0,Y의 시간이 걸리는 사람을 type1이라 하겠습니다.
(1) 49점 풀이
시간복잡도 : O(N^2M^2)
이 문제는 가중치가 X인 정점 N개와 가중치가 Y인 정점 M개를 잘 써서 트리를 만들어 높이의 최댓값을 최소화하는 문제입니다.
dp[i][j]:type0와 type1의 사람이 각각 i명,j명일 때 최소한 걸리는 시간 으로 정의해주고 가능한 모든 O(ij)의 경우에 대해 dp를 전이시켜주면 풀 수 있습니다.
(2) 100점 풀이
시간복잡도 : O(N^3logX)
49점 풀이와 상이합니다. 일반성을 잃지 않고 X<=Y라 합니다. Lemma 하나를 세웁니다.
Lemma1. 최소 하나의 최적해에서는 type1의 사람이 type0의 사람의 조상이 아니다.
Proof1. type1의 type0의 조상일 경우 둘을 swap하면 답이 커지지 않습니다.
그러므로 우리는 이분탐색을 할 수 있습니다. 답을 x 이하라고 할 때 사용할 수 있는 type1의 개수를 dp를 이용해 구할 수 있습니다. dp식은 dp[i][j]:현재 i개의 type0가 있고 j번 X만큼 내려왔을 때 사용할 수 있는 type1의 최대 개수. 로 정의해줍시다. 자식으로 모두 type0인 경우, type0가 한 쪽으로 가고 type1이 한 쪽인 경우, 둘 다 type1이 되는 경우(type0가 한 개밖에 없을 때만 가능)을 각각 전이시켜줍시다. 시간복잡도가 O(N^3logX)가 나오는데 /12가 기본적으로 붙어서 시간 안에 들어옵니다.
#include <bits/stdc++.h>
using namespace std;
int dp[501][501];
int n,m,x,y;
int lim;
const int INF=1e7;
const int nn=-1e9;
int ans(int num,int h) {
if (h*x>lim) {
return -INF;
}
if (num==0) {
return 0;
}
if (dp[num][h]!=nn) {
return dp[num][h];
}
if (num==1) {
int left=lim-h*x;
int ret=0;
int nh=left/y;
if (left>=0) {
ret+=(nh>20?m:((2<<nh)-2));
}
ret=min(ret,m);
dp[num][h]=ret;
return ret;
}
int ret=ans(num-1,h+1);
int left=lim-h*x;
if (left>=0) {
int nh=left/y;
nh=max(nh,0);
ret+=(nh>20?m:((1<<nh)-1));
ret=min(ret,m);
}
for(int i=1;i<num-1;i++) {
ret=max(ret,ans(i,h+1)+ans(num-1-i,h+1));
}
ret=min(ret,m);
dp[num][h]=ret;
return ret;
}
int main(void) {
scanf("%d %d %d %d",&n,&m,&x,&y);
if (x>y) {
swap(n,m);
swap(x,y);
}
if (n==0) {
swap(n,m);
swap(x,y);
}
int lo=0; //impossible
int hi=1e7; //possible
while (lo+1<hi) {
int mid=(lo+hi)/2;
for(int i=0;i<=500;i++) {
for(int j=0;j<=500;j++) {
dp[i][j]=nn;
}
}
lim=mid;
if (ans(n,1)>=m) {
hi=mid;
}
else {
lo=mid;
}
}
printf("%d",hi);
}
17. 좋은 카트 만들기
(1) 100점 풀이
시간복잡도 : O((N+M)log(N+M))
답이 x 이상일 수 있는 조건을 따져봅시다. (Ai+Cj)/(Bi+Dj)>=x를 정리하면 Ai+Cj>=x*Bi+x*Dj로 -Bi*x+Ai>=-Dj*x+Cj가 됩니다. -Dj*x+Cj가 최소가 되는 걸 택하는 게 좋으므로 -Dj*x+Cj의 최솟값으로 이루어진 컨벡스헐과 -Bi*x+Ai의 교점을 구하는 것을 잘 해주면 됩니다. 실수오차가 있을 수 있어서 실수를 전혀 사용하지 않았고, 최솟값을 구하는 부분도 까다롭습니다. 스파스테이블을 적극활용했습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
#define double Fraction
struct Fraction {
__int128 up,down;
void print() {
//printf("%.5lf",(ld)up/(ld)down);
long long u=up;
long long d=down;
printf("%lld/%lld ",u,d);
}
};
bool operator <(const Fraction& P, const Fraction& Q){
return P.up*Q.down<P.down*Q.up;
}
bool operator >(const Fraction& P, const Fraction& Q){
return P.up*Q.down>P.down*Q.up;
}
bool operator >=(const Fraction& P, const Fraction& Q){
return P.up*Q.down>=P.down*Q.up;
}
bool operator <=(const Fraction& P, const Fraction& Q){
return P.up*Q.down<=P.down*Q.up;
}
struct Node {
long long a;
long long b;
int ind;
};
struct Inter {
double l;
double r;
long long a,b;
int ind;
};
Inter inter[300000];
int table[300000][19];
int mint[300000][19];
Fraction cross(Node a,Node b) {
Fraction mid={b.b-a.b,a.a-b.a};
if (a.a-b.a<0) {
mid.up=-mid.up;
mid.down=-mid.down;
}
return mid;
}
Node line[300000];
int sz=0;
Node st[300000];
bool comp(Node a,Node b) {
if (a.a==b.a) {
if (a.b==b.b) {
return a.ind>b.ind;
}
return a.b>b.b;
}
return a.a>b.a;
}
int n,m;
typedef pair<double,int> p;
vector<p> save;
vector<p> lb;
Fraction minf={-2000000000,1};
Fraction inf={2000000000,1};
void init() {
sort(line,line+m,comp);
for(int i=0;i<m;i++) {
while ((sz>1&&(st[sz-1].a==line[i].a||cross(st[sz-2],st[sz-1])>cross(st[sz-1],line[i])))||(sz==1&&st[0].a==line[i].a)) {
sz--;
}
st[sz++]=line[i];
}
for(int i=0;i<sz;i++) {
inter[i].l=(i==0?minf:cross(st[i-1],st[i]));
inter[i].r=(i==sz-1?inf:cross(st[i],st[i+1]));
inter[i].a=st[i].a;
inter[i].b=st[i].b;
inter[i].ind=st[i].ind;
}
for(int i=0;i<sz-1;i++) {
table[i][0]=i+1;
}
for(int i=0;i<sz;i++) {
mint[i][0]=st[i].ind;
}
}
typedef pair<int,int> P;
P arr[300000];
P sav[300000];
int main(void) {
minf.up=-2000000000;
minf.down=1;
memset(table,-1,sizeof(table));
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++) {
scanf("%d %d",&arr[i].first,&arr[i].second);
}
for(int i=0;i<m;i++) {
scanf("%d %d",&line[i].b,&line[i].a);
sav[i].first=line[i].b;
sav[i].second=line[i].a;
line[i].b=-line[i].b;
line[i].ind=i+1;
}
init();
for(int j=1;j<19;j++) {
for(int i=0;i<sz;i++) {
if (table[i][j-1]!=-1) {
table[i][j]=table[table[i][j-1]][j-1];
}
mint[i][j]=min(mint[i][j-1],mint[min(sz-1,i+(1<<(j-1)))][j-1]);
}
}
for(int i=0;i<n;i++) {
int now=0;
double pt=cross({-arr[i].second,arr[i].first,-1},st[0]);
if (pt>inter[0].r) {
for(int j=18;j>=0;j--) {
if (table[now][j]==-1) {
continue;
}
int nt=table[now][j];
double pt=cross({-arr[i].second,arr[i].first,-1},st[nt]);
if (pt>inter[nt].r) {
now=table[now][j];
}
}
now++;
}
int ret=1e6;
for(int j=18;j>=0;j--) {
int nt=now+(1<<j)-1;
if (nt>=sz) {
continue;
}
double pt=cross({-arr[i].second,arr[i].first,-1},st[nt]);
if (pt>=inter[nt].l) {
ret=min(ret,mint[now][j]);
now=now+(1<<j);
}
}
printf("%d\n",ret);
}
}
18. 유저 그룹 나누기
(1) 31점 풀이
시간복잡도 : O(N^4K)
최솟값/최댓값이 되는 구간을 고정해줍시다. 그리고 O(N^2K)짜리 dp로 최댓값/최솟값을 최소화/최대화시켜주면 됩니다. 물론 구간들의 값은 지정된 최솟값/최댓값의 이상/이하여야 합니다. dp[i][j]:i번째 인덱스까지를 j개의 구간으로 나누었을 때의 최솟값의 최댓값/최댓값의 최솟값으로 정의하고 O(N)에 전이시켜주면 됩니다.
(2) 100점 풀이
시간복잡도 : O(N^3)
일단 O(N^2K)에 dp 한 번을 하는 건 너무 느린 거 같습니다. 시간을 줄여줍시다. dp[i][j]:i번째 인덱스까지를 j개의 구간으로 나누었을 때 최댓값의 최솟값이라 합시다. 현재 고정되어있는 최솟값을 MIN이라 했을 때 dp[i][j]=psum[i]-psum[k]>=MIN인 범위에서 min(max(dp[k][j-1],psum[i]-psum[k]))입니다. k는 당연히 원래 입력의 k랑 별개입니다. 알파벳을 뭘 쓸지 모르겠어서 썼습니다. i가 점점 증가되면서 답을 구할텐데, dp[k][j-1]보다 psum[i]-psum[k]가 어느 시점에서 더 커질 것입니다. 만약 psum[i]-psum[k]가 더 클 때는 k가 큰 쪽이 무조건적으로 더 작을 수밖에 없습니다. 여기서 덱 dp를 적용합시다. a와 b (a<b)에 대해 dp[a][j-1]>=dp[b][j-1]이라면 a에서 비롯되는 값은 무조건 b에서 비롯되는 값 이상입니다. 그러므로 b를 넣으려 할 때 dp[a][j-1]>=dp[b][j-1]이라면 a를 pop해주면 됩니다. 덱의 앞쪽에서는 이런 식으로 원소의 dp값이 앞으로 갈수록 증가되도록 관리해주고, 덱의 뒤쪽에서는 이제 psum[i]-psum[k]가 dp[k][j-1]보다 커진 원소를 pop해주면서 psum[i]-psum[k]를 계산할 때 사용할 k를 갱신시켜주면 됩니다. 그러면 이제 O(NK)에 dp를 할 수 있습니다.
그런데 그래도 O(N^3K)의 시간이 걸려 100점을 받기는 무리입니다. 여기서 X<=arr[i]<=2X의 조건을 잘 사용해봅시다. 모든 원소의 합이 total이라 합시다. 구간이 최솟값이 될 수 있으려면 적어도 total/K 이하여야 할 것입니다. 그리고 X<=arr[i]<=2X 이기 대문에 합이 total/K 이하인 구간의 길이는 O(N/K)입니다. 구간의 길이가 O(N/K) 이하인 구간의 개수는 O(N^2/K)입니다. 이 경우에 대해서만 dp를 돌려주면 시간복잡도가 O(NK)*O(N^2/K)=O(N^3)이 되어 문제를 풀 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
int n,k,x;
long long arr[401];
long long psum[401];
long long dp[401][401];
const long long INF=1e13;
int maxi[401];
long long to;
void solve(int l,int r) {
for(int i=0;i<=n;i++) {
for(int j=0;j<=k-1;j++) {
dp[i][j]=INF;
}
}
for(int i=l;i<=r;i++) {
dp[i][1]=(psum[i]-psum[l-1]>=to?psum[i]-psum[l-1]:INF);
}
for(int j=2;j<=k-1;j++) {
int now=l+j-2;
int ind=-1;
deque<int> dq;
for(int i=l+j-1;i<=r;i++) {
while (now<=maxi[i]) {
while (!dq.empty()&&dp[dq.front()][j-1]>=dp[now][j-1]) {
dq.pop_front();
}
dq.push_front(now);
now++;
}
while (!dq.empty()&&psum[i]>dp[dq.back()][j-1]+psum[dq.back()]) {
ind=dq.back();
dq.pop_back();
}
dp[i][j]=min((ind==-1?INF:psum[i]-psum[ind]),(dq.empty()?INF:dp[dq.back()][j-1]));
}
}
}
void generate() {
printf("10 5 5\n");
for(int i=1;i<=10;i++) {
printf("%d ",rand()%6+5);
}
}
long long save[401];
int main(void) {
//generate();
scanf("%d %d %d",&n,&k,&x);
if (k==1) {
printf("0");
return 0;
}
for(int i=1;i<=n;i++) {
scanf("%lld",&arr[i]);
psum[i]=psum[i-1]+arr[i];
}
long long ret=INF;
for(int one=0;one<n;one++) {
for(int two=one+1;two<=n;two++) { //interval (one,two]
long long total=psum[two]-psum[one];
to=total;
if (total*k>psum[n]) {
break;
}
for(int i=1;i<=n;i++) {
maxi[i]=upper_bound(psum,psum+n+1,psum[i]-total)-psum-1;
}
if (one==0) {
solve(two+1,n);
ret=min(ret,dp[n][k-1]-total);
}
else if (two==n) {
solve(1,one);
ret=min(ret,dp[one][k-1]-total);
}
else {
solve(1,one);
for(int i=1;i<k-1;i++) {
save[i]=dp[one][i];
//printf("%lld\n",save[i]);
}
//return 0;
solve(two+1,n);
for(int i=1;i<k-1;i++) {
ret=min(ret,max(save[i],dp[n][k-1-i])-total);
}
}
//return 0;
}
}
printf("%lld",ret);
}
19. 서비스 센터
(1) 100점 풀이
시간복잡도 : O((N+M)log(N+M)logX)
일단 qj의 부호는 의미가 없으니 qj에 절댓값을 취해줍시다. 그러고 나면 이제 좌표계를 돌릴 수 있게 됩니다. 좌표계를 45도 회전시키면 서비스 센터 하나가 갈 수 있는 사무실의 범위는 축에 평행한 직사각형 형태가 됩니다. 이제부터 서비스센터가 갈 수 있는 범위의 꼭짓점 (x,y)를 이제 그 서비스 센터의 좌표라 하겠습니다. 서비스센터와 사무실을 x좌표 순으로 정렬합시다. 그리고 답이 X 이하일 수 있는지 이분탐색을 하겠습니다. x좌표가 작은 서비스센터부터 봤을 때 자기가 갈 수 있는 사무실들 중 가장 y좌표가 큰 사무실을 가는 것이 이득이 됩니다. 이렇게 그리디하게 O(NlogN)에 결정문제를 set등을 이용해 풀 수 있고 전체 시간복잡도는 O(NlogNlogX)가 됩니다.
#include <bits/stdc++.h>
using namespace std;
int n,m;
typedef pair<long long,long long> P;
typedef pair<P,long long> Pi;
P arr[100000];
Pi query[100000];
long long sum=0;
bool isp(long long k) {
int ind=0;
multiset<P> s;
for(int i=0;i<n;i++) {
while (ind<m&&query[ind].first.first<=arr[i].first) {
s.insert(P(query[ind].first.second,query[ind].second));
ind++;
}
long long now=k;
while (now>0&&!s.empty()) {
auto iter=s.upper_bound(P(arr[i].second+1,-1));
if (iter==s.begin()) {
break;
}
iter--;
P got=(*iter);
if (got.second>now) {
s.erase(iter);
s.insert(P(got.first,got.second-now));
now=0;
break;
}
else {
now-=got.second;
s.erase(iter);
}
}
}
return s.empty();
}
int main(void) {
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++) {
scanf("%lld %lld",&arr[i].first,&arr[i].second);
long long x=arr[i].first;
long long y=arr[i].second;
arr[i].first=x+y;
arr[i].second=-x+y;
}
for(int i=0;i<m;i++) {
scanf("%lld %lld %lld",&query[i].first.first,&query[i].first.second,&query[i].second);
if (query[i].first.second<0) {
query[i].first.second=-query[i].first.second;
}
long long x=query[i].first.first;
long long y=query[i].first.second;
query[i].first.first=x+y;
query[i].first.second=-x+y;
sum+=query[i].second;
}
sort(arr,arr+n);
sort(query,query+m);
long long lo=0; //impossible
long long hi=1e14; //possible;
while (lo+1<hi) {
long long mid=(lo+hi)/2;
if (isp(mid)) {
hi=mid;
}
else {
lo=mid;
}
}
printf("%lld",hi);
}
20. 물풍선 테러리스트
(1) 21점 풀이
N<=2500이기 때문에 (이게 터지면 저게 터지는 관계)를 그래프로 직접 나타낼 수 있습니다. 그래프에서 SCC를 추출합시다. SCC 내에 있는 물풍선들은 무조건 동시에 터질 수밖에 없습니다. 그러니까 그냥 SCC를 하나의 정점으로 한 DAG를 봅시다. max일 때는 위상정렬 역순으로 선택하면 매번 자기자신만 터지니 SCC의 개수가 답이 됩니다. min일 때는 degree가 0인 정점을 다 터트리는 시간은 필요하고 degree가 0인 정점을 다 터트리면 끝나므로 degree가 0인 SCC의 개수가 답입니다.
(2) 100점 풀이
이제 N이 커져서 직접 그래프를 만들 수는 없습니다. 하지만 간접적으로 그래프를 만들 수는 있습니다. justicehui.github.io/tutorial/2020/09/05/graph-with-segment-tree/ 를 이용하면 됩니다. 그럼 정점 O(N)개 간선 O(NlogN)개의 그래프에서 SCC를 구하고, 거기서 답을 구하면 됩니다. max 부분은 '진짜' 정점이 속한 SCC의 개수를 세면 되고, degree가 0인 정점을 세는 것은 SCC의 DAG를 그리고 '진짜' 정점이 속한 SCC들을 큐에 넣어서 BFS를 하며 방문되지 않은 "'진짜' 정점이 속한 SCC"의 개수를 구해주면 됩니다. 물론 이를 위해서는 처음 큐에 넣을 때는 방문 체크를 하지 말아야 합니다.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> adj[2000001];
vector<int> rev[2000001];
char str[4];
vector<int> yp[500000]; //yp[x][i]=y;
vector<int> xp[500000]; //xp[y][i]=x;
typedef pair<int,int> P;
typedef pair<P,int> Pi;
Pi arr[500000];
vector<int> xpr;
vector<int> ypr;
int sz;
vector<int> xpos[500000];
vector<int> ypos[500000];
vector<Pi> tofind;
int maketree_x(int yind,int l,int r,int node) {
if (l==r) {
xpos[yind][node]=(*lower_bound(tofind.begin(),tofind.end(),Pi(P(xp[yind][l],ypr[yind]),-1))).second;
return xpos[yind][node];
}
xpos[yind][node]=sz++;
int mid=(l+r)/2;
adj[xpos[yind][node]].push_back(maketree_x(yind,l,mid,node*2));
adj[xpos[yind][node]].push_back(maketree_x(yind,mid+1,r,node*2+1));
return xpos[yind][node];
}
int maketree_y(int xind,int l,int r,int node) {
if (l==r) {
ypos[xind][node]=(*lower_bound(tofind.begin(),tofind.end(),Pi(P(xpr[xind],yp[xind][l]),-1))).second;
return ypos[xind][node];
}
ypos[xind][node]=sz++;
int mid=(l+r)/2;
adj[ypos[xind][node]].push_back(maketree_y(xind,l,mid,node*2));
adj[ypos[xind][node]].push_back(maketree_y(xind,mid+1,r,node*2+1));
return ypos[xind][node];
}
void connect_x(int yind,int st,int l,int r,int node,int nodel,int noder) {
if (r<nodel||l>noder) {
return;
}
if (l<=nodel&&noder<=r) {
adj[st].push_back(xpos[yind][node]);
return;
}
int mid=(nodel+noder)/2;
connect_x(yind,st,l,r,node*2,nodel,mid);
connect_x(yind,st,l,r,node*2+1,mid+1,noder);
}
void connect_y(int xind,int st,int l,int r,int node,int nodel,int noder) {
if (r<nodel||l>noder) {
return;
}
if (l<=nodel&&noder<=r) {
adj[st].push_back(ypos[xind][node]);
return;
}
int mid=(nodel+noder)/2;
connect_y(xind,st,l,r,node*2,nodel,mid);
connect_y(xind,st,l,r,node*2+1,mid+1,noder);
}
stack<int> s;
bool visited[2000001];
int scc[2000001];
bool used[2000001];
int deg[2000001];
bool isokay[2000001];
void dfs(int u) {
if (visited[u])
return;
visited[u]=true;
for(int i=0;i<adj[u].size();i++) {
dfs(adj[u][i]);
}
s.push(u);
}
void revdfs(int u,int num) {
if (visited[u])
return;
visited[u]=true;
scc[u]=num;
for(int i=0;i<rev[u].size();i++) {
revdfs(rev[u][i],num);
}
}
int main(void) {
scanf("%d\n",&n);
sz=n;
scanf("%s\n",str);
for(int i=0;i<n;i++) {
int x,y,p;
scanf("%d %d %d",&x,&y,&p);
arr[i]=Pi(P(x,y),p);
xpr.push_back(x);
ypr.push_back(y);
tofind.push_back(Pi(P(x,y),i));
}
sort(tofind.begin(),tofind.end());
sort(xpr.begin(),xpr.end());
xpr.erase(unique(xpr.begin(),xpr.end()),xpr.end());
sort(ypr.begin(),ypr.end());
ypr.erase(unique(ypr.begin(),ypr.end()),ypr.end());
for(int i=0;i<n;i++) {
arr[i].first.first=lower_bound(xpr.begin(),xpr.end(),arr[i].first.first)-xpr.begin();
arr[i].first.second=lower_bound(ypr.begin(),ypr.end(),arr[i].first.second)-ypr.begin();
xp[arr[i].first.second].push_back(xpr[arr[i].first.first]);
yp[arr[i].first.first].push_back(ypr[arr[i].first.second]);
}
for(int i=0;i<ypr.size();i++) {
sort(xp[i].begin(),xp[i].end());
}
for(int i=0;i<xpr.size();i++) {
sort(yp[i].begin(),yp[i].end());
}
for(int i=0;i<ypr.size();i++) {
xpos[i].resize(xp[i].size()*4);
maketree_x(i,0,xp[i].size()-1,1);
}
for(int i=0;i<xpr.size();i++) {
ypos[i].resize(yp[i].size()*4);
maketree_y(i,0,yp[i].size()-1,1);
}
for(int i=0;i<n;i++) {
int lind=lower_bound(xp[arr[i].first.second].begin(),xp[arr[i].first.second].end(),xpr[arr[i].first.first]-arr[i].second)-xp[arr[i].first.second].begin();
int rind=upper_bound(xp[arr[i].first.second].begin(),xp[arr[i].first.second].end(),xpr[arr[i].first.first]+arr[i].second)-xp[arr[i].first.second].begin()-1;
connect_x(arr[i].first.second,i,lind,rind,1,0,xp[arr[i].first.second].size()-1);
lind=lower_bound(yp[arr[i].first.first].begin(),yp[arr[i].first.first].end(),ypr[arr[i].first.second]-arr[i].second)-yp[arr[i].first.first].begin();
rind=upper_bound(yp[arr[i].first.first].begin(),yp[arr[i].first.first].end(),ypr[arr[i].first.second]+arr[i].second)-yp[arr[i].first.first].begin()-1;
connect_y(arr[i].first.first,i,lind,rind,1,0,yp[arr[i].first.first].size()-1);
}
for(int i=0;i<sz;i++) {
for(int j=0;j<adj[i].size();j++) {
rev[adj[i][j]].push_back(i);
}
}
for(int i=0;i<sz;i++) {
if (!visited[i]) {
dfs(i);
}
}
memset(visited,0,sizeof(visited));
int num=0;
while (!s.empty()) {
int st=s.top();
s.pop();
if (!visited[st]) {
revdfs(st,num);
num++;
}
}
for(int i=0;i<n;i++) {
isokay[scc[i]]=true;
}
queue<int> q;
for(int i=0;i<num;i++) {
if (isokay[i]) {
q.push(i);
}
}
memset(visited,0,sizeof(visited));
for(int i=0;i<sz;i++) {
rev[i].clear();
}
for(int i=0;i<sz;i++) {
for(int j=0;j<adj[i].size();j++) {
int nt=adj[i][j];
if (scc[i]!=scc[nt]) {
rev[scc[i]].push_back(scc[nt]);
}
}
}
while (!q.empty()) {
int now=q.front();
q.pop();
for(int i=0;i<rev[now].size();i++) {
int nt=rev[now][i];
if (!visited[nt]) {
visited[nt]=true;
if (!isokay[nt])
q.push(nt);
}
}
}
int ret=0;
for(int i=0;i<n;i++) {
if (!used[scc[i]]) {
used[scc[i]]=true;
if (strcmp(str,"max")==0) {
ret++;
}
if (strcmp(str,"min")==0) {
if (!visited[scc[i]]) {
ret++;
}
}
}
}
printf("%d",ret);
}
'PS' 카테고리의 다른 글
| KOI 2020 본선 후기 (2) | 2020.12.05 |
|---|---|
| NYPC 2020 본선 후기 (2) | 2020.11.22 |
| 2020.06.28 Problem Solving (2) | 2020.06.28 |
| Codeforces Round #642 (Div. 3) (0) | 2020.05.15 |
| BAPC 2019 (0) | 2020.05.11 |
