2021 NYPC 후기/풀이

 

 

보이는 거 그대로 망했다 1214라면 사실상 본선 확정이지만 이번 연도부턴 1519라 이 정도 점수론 절대 갈 수 없다.

일단 풀이는 전부터 작성하고 있었으니 이어서 작성했다.

 

 

1. 계단

 

 nypc의 첫 문제다 처음에 잡았을 때 뇌절이 좀 있어서 나중에 풀었는데 예제 설명에 쓰여있는 방법이 최적해다.(사실 그냥 준 문제)

현재 위치에서 내려간다음 끝까지 올라갔다 내려갔다 하면서 마지막에는 현재 위치로 다시 돌아와야 하니 1층에서 지금 층으로 오는 횟수를 빼주고 뺀값들로 왔다 갔다 해주면 되는데 이때 현재 위치가 1일 때는 올라가는 거부터 해도 되지만 아닐 경우 한번 내려가 줘야 되는데 이때 위로 올라가서 횟수를 줄일 수 있을 경우 올라가 줘서 줄인 다음 내려오면 더 짧은 횟수를 구할 수 있다.

시복은 O(1)이다.

import sys
input=sys.stdin.readline
a,b,c=map(int,input().split())
d=c-(b-1)
if b==1:s=0
else:s=1;d-=min(d%(a-1),(a-b))
#s+=d//(a-1)
if d//(a-1)==0:
    if d%(a-1)!=0:
        s+=1
else:
    s+=d//(a-1)
    if d%(a-1)!=0:
        s+=1
print(s)

 

2. 레이스 기록 검증

 

작년 문제랑 비슷한 감이 없잖아 있었다.

개인적으로 모든 문제 중 가장 쉽지 않을까 싶은 문제이다.

지문 그대로 올바르지 않은 방법만 찾아서 NO를 출력해주면 된다. 

시간 복잡도는 O(M)이다.

import sys
input=sys.stdin.readline
a,b=map(int,input().split())
st=[[0,0]]*(a+1)
for i in range(b):
    c,d,e=map(int,input().split())
    if e==0:
        if st[d][1]==1:
            print("NO")
            sys.exit()
        st[d]=[c,1]
    else:
        if st[d][1]==0:
            print("NO")
            sys.exit()
        elif c-st[d][0]<60:
            print("NO")
            sys.exit()
        else:
            st[d]=[0,0]
for i in range(1,a+1):
    if st[i][1]==1:print("NO");sys.exit()
print("YES")

 

3. 근무표 짜기

 

처음에 감이 안 잡힌 문제였는데 단순하게 입력 순대로 추가하다 보면 같은 날에 같은 사람이 겹치게 되는 일이 있다. 그래서 계속해서 정렬을 하면서 가장 많은 공간이 남은 곳에다가 사람을 추가하는 방식을 사용해서 풀었다.

시간 복잡도는 O(N^2 logN)이다.

import sys
import math
inf=math.inf
input=sys.stdin.readline
a,b=map(int,input().split())
l=list(map(int,input().split()))
l=[[l[i],i+1]for i in range(a)]
t=list(map(int,input().split()))
t=[[t[i],i+1]for i in range(b)]
l.sort(reverse=True)
t.sort()
st=[[]for i in range(b+1)]
for i in range(a):
    t.sort(reverse=True)
    for g in range(l[i][0]):
        t[g][0]-=1
        st[t[g][1]].append(l[i][1])
        #print(t)
        #print(st)
for i in range(1,b+1):
    zz=len(st[i])
    print(zz,end=" ")
    for g in range(zz):
        print(st[i][g],end=" ")
    print()

 

4. 파티

 

말이 좀 많긴 한데 간단히 하면 n개 수들을 적절히 맞춰서 가장 큰 수와 가장 작은 수의 차가 최대 1이 되도록 할 때 맞출 때 쓰는 값의 최솟값을 출력하는 문제이다. 

일단 적절히 맞출 때도 합은 유지해야 되므로 평균값을 잡아주고 거기서 나머지 값들을 적절히 조정을 해줘 값을 최소화하면 된다. 

나머지 값들은 가장 큰 값 순서대로 1씩 추가해준 다음 입력값이 더 작을 때만 두 수의 차를 모두 더해줘서 출력하면 된다.

시간 복잡도는 O(NlogN)이다.

import sys
import math
inf=math.inf
input=sys.stdin.readline
a=int(input())
l=list(map(int,input().split()))
s=sum(l)
z=s//a
df=s%(z*a)
ans=0
if df==0:
    for i in range(a):
        if l[i]>z:ans+=l[i]-z
    print(ans)
    sys.exit()
#print(z,df)
l.sort()
ans=0
t=[z]*(a+1)
for i in range(df):t[a-1-i]+=1
for i in range(a):
    if l[i]<t[i]:ans+=t[i]-l[i]
    else:break
print(ans)

 

5. 페인트 칠하기

 

nypc에 꼭 나오는 게임 문제다.

1번부터 5번까지는 막일을 해서 2분 만에 끝냈지만 6번부터는 저번처럼 막일했다간 너무 오래 걸릴 거 같아서 코딩으로 풀었다.

일단 딱 보이는 단순 dfs으로 7번까지 풀어줬다.

import sys
import math
sys.setrecursionlimit(10**9)
inf=math.inf
input=sys.stdin.readline
a,b=map(int,input().split())
l=[list(map(int,input().split()))for i in range(a)]
ans=[]
ch=[[0 for i in range(b)]for g in range(a)]
pr=[]
def dfs(y,x,color,last):
    global pr
    #print(y,x)
    if last==0:
        #print("V",x+1,color)
        pr.append(["V",x+1,color])
        for i in range(a):ch[i][x]=color
        for i in range(a):
            if ch[i][x]!=l[i][x]and l[i][x]!=0:
                dfs(i,x,l[i][x],1)
    else:
        #print("H",y+1,color)
        pr.append(["H",y+1,color])
        for i in range(b):ch[y][i]=color
        for i in range(b):
            if ch[y][i]!=l[y][i]and l[y][i]!=0:
                dfs(y,i,l[y][i],0)
            
for i in range(a):
    for g in range(b):
        if l[i][g]!=ch[i][g] and l[i][g]!=0:
            ycnt=0
            xcnt=0
            for ii in range(b):
                if l[i][ii]==l[i][g]:
                    xcnt+=1
            for ii in range(a):
                if l[ii][g]==l[i][g]:
                    ycnt+=1
            if ycnt>=xcnt:
                dfs(i,g,l[i][g],0)
            else:
                dfs(i,g,l[i][g],1)
ant=len(pr)
print(ant)
for i in range(ant):
    print(pr[i][0],pr[i][1],pr[i][2])

7번까지는 순조롭게 풀었는데....

8번부터는 이 방식대로 하면 10만 개 정도가 나와서 다른 방식을 찾았다.

다른 방식도 생각보다 간단하다.

방법은 가장 마지막에 눌러야 하는 위치를 계속 찾는 방법인데 처음에 가장 마지막에 눌러야 하는 위치를 찾고 그 위치를 제거했을 때 마지막에 눌러야 한 위치를 찾고 여러 개 일 경우 칠해야 되는 위치가 가장 많은 순으로 지워가며 스택에 추가한 뒤 마지막까지 다했을 때 거꾸로 해서 출력하면 할 수 있게 된다.

증명은 따로 안 하겠다

import sys
import math
sys.setrecursionlimit(10**9)
inf=math.inf
input=sys.stdin.readline
a,b=map(int,input().split())
l=[list(map(int,input().split()))for i in range(a)]
ans=[]
ch=[[0 for i in range(b)]for g in range(a)]
for i in range(a):
    for g in range(b):
        if l[i][g]==0:ch[i][g]=1
def ck():
    for i in range(a):
        for g in range(b):
            if ch[i][g]==0:return 0
    return 1
while 1:
    y=[[-inf,-inf,-inf]]
    x=[[-inf,-inf,-inf]]
    for i in range(a):
        color=-1
        z=1
        cnt=0
        for g in range(b):
            if ch[i][g]==0:
                if color==-1:color=l[i][g];cnt=1
                else:
                    if l[i][g]!=color:z=0;break
                    else:cnt+=1
        if z==1 and color!=-1:
            x.append([cnt,i,color])
    for i in range(b):
        color=-1
        z=1
        cnt=0
        for g in range(a):
            if ch[g][i]==0:
                if color==-1:color=l[g][i];cnt=1
                else:
                    if l[g][i]!=color:z=0;break
                    else:cnt+=1
        if z==1 and color!=-1:
            y.append([cnt,i,color])
    mx=max(x)
    my=max(y)
    print(mx,my)
    if mx!=[-inf,-inf,-inf]or my!=[-inf,-inf,-inf]:
        if mx[0]>my[0]:
            ans.append(["H",mx[1]+1,mx[2]])
            for i in range(b):
                ch[mx[1]][i]=1
        else:
            ans.append(["V",my[1]+1,my[2]])
            for i in range(a):
                ch[i][my[1]]=1
    if ck()==1:break
zz=len(ans)
print(zz)
for i in range(zz-1,-1,-1):
    print(ans[i][0],ans[i][1],ans[i][2])

 

6. 폭탄 터트리기

 

보자마자 작은 값부터 구간을 지워나가면서 최솟값을 구할 수 있을 거 같아서 우선순위 큐로 박았는데 이 방법은 100은 생각하지 않고 한 거였지만 100이 나와서 개꿀 하고 딴 걸 하고 있었는데 갑자기 마지막이 터졌었다 물론 예상한 거였지만 마지막을 풀고 있는데 터져서 귀찮아졌다.

import sys
from queue import PriorityQueue
input=sys.stdin.readline
a,b=map(int,input().split())
l=list(map(int,input().split()))
que=PriorityQueue()
for i in range(a):que.put([l[i],i])
st=[0]*(a+1)
ch=0
cnt=a
ans=0
while ch!=a and cnt!=0:
    s=que.get()
    cnt-=1
    if st[s[1]]==0:
        ans+=1
        left=s[1]-1
        right=s[1]+1
        st[s[1]]=1
        while left>=0 and st[left]==0 and s[0]<=l[left]<=s[0]+b:ch+=1;st[left]=1;left-=1
        while right<a and st[right]==0 and s[0]<=l[right]<=s[0]+b:ch+=1;st[right]=1;right+=1
    #print(st,ch,s)
print(ans)

 

100이었지만 47점 맞은 코드이다.

100점짜리 코드도 별 차이는 없는데 우선순위 큐가 아닌 정렬을 해두고 하는 방식으로 100을 받았다.

시간 복잡도는 O(nlogn)이다

import sys
input=sys.stdin.readline
a,b=map(int,input().split())
l=list(map(int,input().split()))
y=[[l[i],i]for i in range(a)]
y.sort()
st=[0]*(a+1)
ch=0
ans=0
i=0
while ch!=a and i<a:
    s=y[i]
    if st[s[1]]==0:
        ans+=1
        left=s[1]-1
        right=s[1]+1
        st[s[1]]=1
        ch+=1
        while left>=0 and st[left]==0 and s[0]<=l[left]<=s[0]+b:ch+=1;st[left]=1;left-=1
        while right<a and st[right]==0 and s[0]<=l[right]<=s[0]+b:ch+=1;st[right]=1;right+=1
    #print(st,ch,s)
    i+=1
print(ans)

 

7. 루트가 많은 트리?

이 문제도 생각보다 간단했는데 트리는 설명에도 있는 거처럼 부모 노드가 1개다 즉 i번째 노드에서 j번째 노드로 가는 방향 간선이 있다면 j번의 나머지 모든 간선은 다 i, j방향과 같은 방향이 여야 하며 j [i](j의 자식 노드)->j로 가는 방향 간선이 있으면 안 된다. 그러므로 모든 점에서 탐색을 해주고 한 노드로 오는 간선이 2개 이상 있을 경우 0을 출력, 아닐 경우 한 정점과 연결되어있는 간선중 하나라도 방향이 없는 간선이 있다면 그 노드는 무조건 루트 노드가 될 수 있다. 그러므로 그 정점의 개수를 세주면 된다.

시간 복잡도는 O(N)인 거 같다

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
a=int(input())
graph=[[]for i in range(a+2)]
ch=[0]*(a+1)
def f(n,w,lt):
    if w==0:
        zx=0
        for next in graph[n]:
            if lt!=next[0] and next[1]==1 and ch[next[0]]==0:
                f(next[0],1,n)
            if next[1]==0:zx=1
        if zx==0:ch[n]=1
    else:
        ch[n]=1
        i=0
        for next in graph[n]:
            if graph[n][i][1]==0:
                u=next[0]
                for g in range(len(graph[u])):
                    if graph[u][g][0]==n:graph[u][g][1]=2;break
                graph[n][i][1]=1
            if lt!=next[0]and ch[next[0]]==0:
                f(next[0],1,n)

            i+=1
                
for i in range(a-1):
    b,c,d=map(int,input().split())
    graph[b].append([c,d])
    if d==0:
        graph[c].append([b,d])
#print(graph)
for i in range(1,a+1):
    if ch[i]==0:
        f(i,0,-1)
#print(graph)
st=[0]*(a+1)
for i in range(1,a+1):
    for g in range(len(graph[i])):
        if graph[i][g][1]==1:
            st[graph[i][g][0]]+=1
            if st[graph[i][g][0]]>=2:
                print(0)
                sys.exit()
#print(st)
ans=0
for i in range(1,a+1):
    if st[i]==0:
        ans+=1
print(ans)

 

8. 영역 나누기

이문제는 방법을 우연히 찾았는데 첫 번째로 나온 점은 무시하고 두 번째 점이 나왔을 땐 첫 번째 점부터 두 번째 점까지의 구간에서 아직 선이 만들어지지 않은 점의 개수를 모두 더한 값+1만큼 영역에 더해주면 된다. 처음에는 영역 크기는 1이다.

첫 번째 그림으로 예를 들면

1 2 3 까지는 영역 크기가 1 그대로다. 다음 2부터는 2번째부터 4번째 중 2를 제외한 아직 이어지지 않은 점은 3 하나다 이제 영역 개수에 1+1을 해준다. 다음 1도 3 하나이므로 2를 더해준다 2는 이미 1이 끝나기 전에 선이 이어졌으니 세지 않는다.

다음에 4가 연속으로 있는데 그럴 때는 그냥 +1 해준다.

마지막 3에서는 남아있는 점이 없으므로 +1을 해주면 된다.

이 방식을 구현해주면 되는데 그림에 있는 거처럼 n의 범위가 50만이다. 나이브 방식으로는 불가능한데 아직 이어지지 않는 점의 개수를 세그먼트 트리 누적합을 이용해서 구했다.

시간 복잡도는 O(nlogn)이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>l(1000001),t(4001001);
ll st[1000010]={0,};
ll seg(ll n,ll s,ll e){
    if(s==e){return t[n]=0;}
    return t[n]=seg(n*2,s,(s+e)/2)+seg(n*2+1,(s+e)/2+1,e);
}
ll m(ll n,ll s,ll e,ll left,ll right){
    if(left>e||right<s){return 0;}
    if(left<=s&&e<=right){return t[n];}
    return m(n*2,s,(s+e)/2,left,right)+m(n*2+1,(s+e)/2+1,e,left,right);
}
void h(ll n,ll s,ll e,ll i,ll f){
    if(i<s||i>e){return;}
    t[n]+=f;
    if(s!=e){h(n*2,s,(s+e)/2,i,f);h(n*2+1,(s+e)/2+1,e,i,f);}
}
int main()
{
    ll a,b,c,d,q,k,i,cnt=1;
    scanf("%lld",&a);
    for(i=1;i<=2*a;i++){scanf("%lld\n",&l[i]);}
    seg(1,1,2*a);
    for(i=1;i<=2*a;i++){
        if(st[l[i]]==0){
            st[l[i]]=i;
            h(1,1,2*a,i,1);
        }else{
            ll sm=m(1,1,2*a,st[l[i]]+1,i);
            h(1,1,2*a,st[l[i]],-1);
            st[l[i]]=0;
            cnt+=sm+1;
        }
    }
    printf("%lld\n",cnt);
}

 

9.K-좀비

이문제는 딱히 설명할 게 없는데 이유는 9번까지 막일로 다 풀었기 때문이다. ㅋㅋ

작년에도 이런 문제는 막일로 올 클리어했는데 이번에는 그건 좀 아니다 싶어서 9번까지만 막일을 하고 10번은 코드로 짰다.(코드라고는 하지만 그냥 수동으로 위치 값 넣어주고 한 거지만)

import sys
a,b=map(int,input().split())
map=[list(input())for i in range(a)]
move=[]
#sp=[[1,0]]
#lnt=[8]
#move=[[0,0],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8]]
sp=[[0,1],[0,7],[0,13],[0,19],\
    [2,23],[2,18],[2,12],[2,6],\
    [4,0],[4,6],[4,12],[4,18],\
    [6,23],[6,17],[6,11],[6,5],\
    [8,0],[8,6],[8,12],[8,18],\
    [10,23],[10,17],[10,11],[10,5],\
    [12,0],[12,6],[12,12],[12,18],\
    [14,23],[14,17],[14,11],[14,5],\
    [16,0],[16,6],[16,12],[16,18],\
    [18,23],[18,17],[18,11],[18,5],\
    [20,0],[20,6],[20,12],\
    [21,24],\
    [22,17],[22,11],[22,5],\
    [24,1],[24,6],[24,12],[24,22]]
lnt=[4,4,4,3,\
     3,4,4,4,\
     4,4,4,4,\
     4,4,4,4,\
     4,4,4,4,\
     4,4,4,4,\
     4,4,4,4,\
     4,4,4,4,\
     4,4,4,4,\
     4,4,4,4,\
     4,4,4,\
     2,4,4,4,\
     3,4,4,2]
#mx=[5,9,8,7,8,5,9,7,7,9,8,5,9,5,8,\
#    8,5,9,5,8,9,7,7,9,5,8,7,8,9,5,\
#    7,8,9,5,5,7,9,8,9,8,5,7,5,8,7,9,\
#    9,7,8,5,7,5,8,9,8,9,7,5,5,9,8,7,\
#    5,7,9,8,9,8,5,7,5,8,7,9,7,5,9,8,\
#    8,9,5,7,9,7,8,5,7,5,8,9,8,9,7,5]
st=[0]*(sum(lnt)+1)
ch=0
y=0
dy=[-1,0,1,0]
dx=[0,1,0,-1]
idx={}
for i in range(13):
    if ch==0:
        for g in range(25):
            move.append([y,g])
        move.append([y+1,24])
        ch=1
    else:
        for g in range(24,-1,-1):
            move.append([y,g])
        move.append([y+1,0])
        ch=0
    y+=2
asd=[[0 for i in range(b+1)]for g in range(a+1)]
for g in range(a):
    for z in range(b):
        if map[g][z]!="."and map[g][z]!="#":
            for k in range(4):
                nx=z+dx[k]
                ny=g+dy[k]
                if 0<=nx<b and 0<=ny<a:
                    asd[ny][nx]=1
acnt=0
#print(asd)
for ix in range(1,len(move)):
    #print(move[ix])
    if asd[move[ix][0]][move[ix][1]]==1:
        #print(move[ix][0]*b+move[ix][1])
        idx[move[ix][0]*b+move[ix][1]]=acnt
        acnt+=1
#print(idx)
#print(move)
#print(len(move))
ch=0
ans=""
up=len(move)
i=0
chk=0
cnt=-1
last=-1
while i<up:
    if i==0:i+=1;continue
    if last!=i:
        if move[i-1][0]==move[i][0]:
            if move[i-1][1]+1==move[i][1]:
                ans+="R"
            else:
                ans+="L"
        elif move[i-1][0]+1==move[i][0]:
            ans+="D"
        else:
            ans+="U"
    zm=[[0 for i in range(b)]for g in range(a)]
    for g in range(a):
        for z in range(b):
            if map[g][z]!="."and map[g][z]!="#":
                for k in range(4):
                    nx=z+dx[k]
                    ny=g+dy[k]
                    if 0<=nx<b and 0<=ny<a:
                        if map[ny][nx]=="." and zm[ny][nx]==0:
                            if ny==0 and nx==0:continue
                            #print(ny*b+nx,ny,nx,b)
                            fh=idx[ny*b+nx]
                            st[fh]-=1
                            if st[fh]<0:st[fh]=int(map[g][z])-1
                            zm[ny][nx]=1
    #print(sp[ch],move[i],chk,ch)
    #if ch!=0:print(ch)
    if last!=i:print(i);last=i;print("#####")
        #if i==293:
        #    print(move[i])
        
    #print(ch,i)
    #print(chk,ch)
    ggg=0
    #for ii in range(lnt[ch]):
    #    if st[chk+ii]!=ii+1:ggg=1
    #if ggg==0:
    #    for ii in range(lnt[ch]):
    #        print(st[chk+ii],end=" ")
    #    print()
    #    print()
    #if i==293 and cnt<=90:
    #    print(cnt,lnt[ch],ch,chk)
    #    for ii in range(lnt[ch]):
    #        print(st[chk+ii],end=" ")
    #    print()
    #    print()
    if ch<len(sp) and sp[ch]==move[i]:
        #print(sp[ch])
        if cnt==-1:cnt=0
        else:cnt+=1
        #if cnt>=10000:print("#")
        if cnt%2==0 or cnt%2!=0:
            #if cnt>=2500:
            #    print(cnt,lnt[ch],ch,chk)
            #    for ii in range(lnt[ch]):
            #        print(st[chk+ii],end=" ")
            #    print()
            if cnt!=0:
                if move[i-1][0]==move[i][0]:
                    if move[i-1][1]+1==move[i][1]:
                        if cnt%2==0:ans+="R"
                        else:ans+="L"
                        #ans+="LR"
                    else:
                        if cnt%2==0:ans+="L"
                        else:ans+="R"
                        #ans+="RL"
                elif move[i-1][0]+1==move[i][0]:
                    if cnt%2==0:ans+="D"
                    else:ans+="U"
                    #ans+="UD"
                else:
                    if cnt%2==0:ans+="U"
                    else:ans+="D"
                    #ans+="DU"
            hl=1
            for ii in range(lnt[ch]):
                if st[chk+ii]!=ii+1:hl=0
            if hl==1:
                if cnt%2==0:
                    if i==324:
                        print(move[i])
                        for ii in range(lnt[ch]+2):
                            print(st[chk+ii],end=" ")
                        print()
                        print()
                    #print(move[i])
                    #print("###",i,cnt)#;sys.exit()
                    i+=1;chk+=lnt[ch];cnt=-1;ch+=1
                    #print(i,cnt)
                else:
                    print(move[i])
                    print("###",i,cnt)
    else:i+=1
#print(len(ans))
print(ans[:60000])
#print(ans)
#for i in range(10000):
#    print(ans[i],end="")

코드에다가 뇌절도 많이 하고 문제를 고치려고 많은걸 하다 보니 주석이 좀 많다

진짜 설마 길이가 10만이 되겠어했는데 진짜로 10번은 길이가 10만이라 출력도 다 안돼서 ideone과 repl.lt 에서 6만 정도로 나눠서 출력하는 작업을 진행했다 이유 모를 오류가 있었는데 마지막에 D가 추가되어있어서 그랬다..

 

10. 다양성이 힘이다.

 

 

 

간단한 머지 소트 트리 문제인데 머지 소트 트리를 슬라이딩 윈도처럼 사용해주면 된다.

K개의 노드에 대한 실력 값을 만들어 주고 오른쪽에 추가하고 왼쪽을 제거하는 방식을 하면 되는데 오른쪽에 X [i] 값을 추가한다고 했을 때 이 X [i]이랑 구간을 이루는 K-1개의 값들과 비교를 해 값을 더해주면 된다. 이것을 머지 소트 트리로 할 수 있는데 어떤 구간에 대해서 X [i]에 대한 upper_bound를 해주고 X [i] * X [i]보다 작거나 같은 구간의 개수- 작거나 같은 구간의 누적합+값이 큰 구간의 누적합-X [i] * 큰 구간의 개수 이렇게 해주고 다 합쳐준다면 X [i]에 대해서 자신이 가장 오른쪽에 있을 때 구간의 다른 값들과의 차이의 합이 된다. 이렇게 하면 X [i]가 추가될 때마다 더하는 값을 logN^2에 구할 수 있고 또 왼쪽 구간을 뺴줘야 되는데 그것도 빼야 되는 왼쪽부터 위에서 오른쪽에 추가했던 위치-1 구간의 값을 구해서 빼주면 된다. 이렇게 만들어진 값들 중 가장 큰 값을 출력하면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> tree[800010];
vector<ll> sutree[800010];
vector<ll>arr(200002);
ll asd=0;
void update(ll bucket, ll node, ll start, ll end, ll x){
	if(node<start || end<node) return;
	tree[bucket].push_back(x);
	if(start != end){
		update(bucket*2, node, start, (start+end)/2, x);
		update(bucket*2+1, node, (start+end)/2+1, end, x);
	}
}

ll get(ll node,ll start, ll end, ll left,ll right,ll x){
	if(left>end || right<start) return 0;
	if(left<=start && end<=right){
        ll jk=tree[node].end()-upper_bound(tree[node].begin(),tree[node].end(),x);
        //printf("%lld %lld %lld %lld\n",start,end,jk,sutree[node][end-start+1]);
        ll kp=end-start+1;
        ll pit=((sutree[node][kp]-sutree[node][kp-jk])-(x*jk))+((x*(kp-jk))-sutree[node][kp-jk]);
        return pit;
        //return jk;
    }
	ll mid = (start+end)/2;
	return get(node*2, start, mid, left, right, x) + get(node*2+1, mid+1, end, left, right, x);
}
void srt(ll node,ll start,ll end){
    sort(tree[node].begin(),tree[node].end());
    sutree[node].push_back(0);
    for(int io=0;io<end-start+1;io++)sutree[node].push_back(sutree[node][io]+tree[node][io]);
    if(start!=end){
        srt(node*2,start,(start+end)/2);
        srt(node*2+1,(start+end)/2+1,end);
    }
}
int main(){
	ll n, m,a,b,c,mi,cnt;
    ll ans=0;
    scanf("%lld %lld",&n,&m);
	for(int i=1; i<=n; i++){
        scanf("%lld ",&arr[i]);
		update(1, i, 1, n, arr[i]);
	}
    srt(1,1,n);
    for(int i=2;i<=m;i++)ans+=get(1,1,n,1,i,arr[i]);
    ll ma=ans;
    //printf("%lld\n",ans);
    for(int i=m+1;i<=n;i++){
        ll A=get(1,1,n,i-m+1,i-1,arr[i]);
        ll B=get(1,1,n,i-m,i-1,arr[i-m]);
        ans+=A;
        ans-=B;
        ma=max(ma,ans);
        //printf("%lld %lld %lld\n",ans,A,B);
    }
    printf("%lld\n",ma);
        
        
}

 

11. 원룸 구하기

 

이게 아마 내가 지금까지 푼 세그 문제 중 역대급으로 이상하게 한 문제가 아닐까 한다

투 포인터+이분 탐색+세그 레이지를 써서 이상한 풀이로 풀었는데

방법은 간단한데 코드가 좀 괴랄하다.

방법은 모든 원룸에 대해서 오른쪽, 왼쪽, 둘다를 포함하는 구간을 모두 만들어 주면 된다.

이것은 n+m으로 가능하다

투 포인터로 왼쪽부터 확인하면서 구간이 되면 그 구간과 가장 가까운 원룸에 구간을 이어주는 것을 모든 구간에 대해서 해주면 된다. 왼쪽 오른쪽을 모두 포함하는 즉 구간 안에서 가장자리가 아닌 위치에 원룸이 있을 때는 그냥 k개의 가게를 만족하는 구간을 추가해주면 된다. 그 구간에 원룸이 들어있다면 자연스럽게 위 조건을 포함시키는 것이 되기 때문이다. 

그렇게 코드를 짜서 모든 경우의 수를 찾아준 다음 정렬과 중복제거를 해준다. 그러고 나서 원룸을 정렬한 뒤에 순서대로 세그에 추가해준다. 그다음에 이분 탐색을 해줄 것인데 위에서 저장했던 구간들을 모두 이분 탐색으로 어떤 월룸에 해당되는지 찾아줄 것이다. 구간의 왼쪽 위치와 오른쪽 위치를 가지고 이분 탐색을 해 원룸 위치에 대한 구간을 찾아준다 그 뒤 그 구간에 i번째 구간의 크기를 더해주면 된다.

이렇게 모든 처리가 끝난 뒤 propagate에 있는 값들을 모두 내려주고 순서에 맞게 출력해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct nd{
    ll i,k;
};
vector<pair<ll,ll>>l;
vector<pair<ll,ll>>st;
vector<pair<ll,ll>>ch;
deque<ll>bu;
vector<ll>tree(2001000);
vector<ll>tree1(2001000);
ll cse=0,inf=1e12;
ll ans[500001];
ll seg(ll n,ll s,ll e){
    tree1[n]=inf;
    if(s==e){return tree[n]=inf;}
    return tree[n]=min(seg(n*2,s,(s+e)/2),seg(n*2+1,(s+e)/2+1,e));
}
void propagate(ll n,ll s,ll e){
    if(tree1[n]!=inf){
        if(s!=e){
            tree1[n*2]=min(tree1[n*2],tree1[n]);
            tree1[n*2+1]=min(tree1[n*2+1],tree1[n]);
        }
        tree[n]=min(tree[n],tree1[n]);
        tree1[n]=inf;
    }
}
ll max1(ll n,ll s,ll e,ll left,ll right){
    propagate(n,s,e);
    if(left>e||right<s){return inf;}
    if(left<=s&&e<=right){return tree[n];}
    return min(max1(n*2,s,(s+e)/2,left,right),max1(n*2+1,(s+e)/2+1,e,left,right));
}
void change(ll n,ll s,ll e,ll s1,ll e1,ll f){
    propagate(n,s,e);
    if(s1<=s&&e<=e1){tree1[n]=min(tree1[n],f);propagate(n,s,e);return;}
    if(e1<s||s1>e){return;}
    change(n*2,s,(s+e)/2,s1,e1,f);
    change(n*2+1,(s+e)/2+1,e,s1,e1,f);
    tree[n]=min(tree[n*2],tree[n*2+1]);
}
ll lb(ll x,ll s,ll k){
    ll start=s;
    ll end=k;
    while(end-start>0){
        ll mid=(start+end)/2;
        if(st[mid].first<=x)start=mid+1;
        else end=mid;
    }
    return end;//s~end-1
}
ll ld(ll x,ll k){
    ll start=0;
    ll end=k;
    while(end-start>0){
        ll mid=(start+end)/2;
        if(st[mid].first<x)start=mid+1;
        else end=mid;
    }
    return end;//s~end-1
}
int main()
{
    ll a,b,c,d,q,k,i,A,B,C;
    ll bunt=0;
    scanf("%lld %lld %lld",&a,&b,&k);
    for(int i=1;i<=a;i++){
        scanf("%lld %lld\n",&A,&B);
        l.push_back(pair<ll,ll>(A,B));
    }
    for(int i=1;i<=k;i++){
        scanf("%lld\n",&C);
        st.push_back(pair<ll,ll>(C,i));
        l.push_back(pair<ll,ll>(C,0));
    }
    sort(l.begin(),l.end());
    sort(st.begin(),st.end());
    ll left=0,right=0;
    ll cnt=0;
    ll ck[500010]={0,};
    ll inx=0,lnx=0;
    ll rnt=0;
    ll last[2]={-inf,};
    if(l[0].second!=0){ck[l[0].second]+=1;cnt++;}
    while(1){
        if(l[right].second!=0){
            if(cnt<b){
                if(right+1<a+k){
                    if(l[right+1].second!=0){
                        if(ck[l[right+1].second]==0)cnt++;
                        ck[l[right+1].second]++;
                    }
                    right++;
                }else{break;}
            }else{
                if(l[left].second!=0){   
                    ll lt=l[left].first,rt=l[right].first;
                    ch.push_back(pair<ll,ll>(lt,rt));
                    if(bunt!=0){
                        while(bunt!=0){
                            if(bu[0]>lt)break;
                            ch.push_back(pair<ll,ll>(bu[0],rt));
                            bunt--;
                            bu.pop_front();
                        }
                    }
                    last[0]=lt;
                    last[1]=rt;
                    if(inx<k){
                        if(inx-1>=0&&st[inx-1].first==l[right].first)ch.push_back(pair<ll,ll>(lt,rt));
                        else ch.push_back(pair<ll,ll>(lt,st[inx].first));
                    }
                    if(lnx-1>=0&&lnx-1<k)ch.push_back(pair<ll,ll>(st[lnx-1].first,rt));
                    if(ck[l[left].second]!=0)ck[l[left].second]--;
                    if(ck[l[left].second]==0)cnt--;
                    rnt++;
                }
                left++;
            }
        }else{
            bu.push_back(l[right].first);
            bunt++;
            if(inx<k)inx++;
            if(last[0]!=-inf)ch.push_back(pair<ll,ll>(last[0],l[right].first));
            rnt=0;
            if(right+1<a+k){
                if(l[right+1].second!=0){
                    if(ck[l[right+1].second]==0)cnt++;
                    ck[l[right+1].second]++;
                }
                right++;
            }else{break;}
        }
        if(l[left].second==0){
            if(lnx<k)lnx++;
            left++;
        }
    }
    sort(ch.begin(),ch.end());
    ch.erase(unique(ch.begin(),ch.end()),ch.end());
    cse=ch.size();
    seg(1,1,k);
    for(int i=0;i<cse;i++){
        ll jk=ld(ch[i].first,k);
        ll rd=lb(ch[i].second,jk,k);
        if(rd-1>=jk)change(1,1,k,jk+1,rd,ch[i].second-ch[i].first);
    }
    for(int i=1;i<=k;i++)ans[st[i-1].second]=max1(1,1,k,i,i);
    for(int i=1;i<=k;i++)printf("%lld\n",ans[i]);
}

 

12. 생존 신호

보이는 대로 만점은 못 받았다 시간도 없었고 100 받기도 어려웠던 문제였다(물론 막일일 경우에만)

 

13. 선물상자

 

8점은 M이 1일 때인 경우다 1일 때는 정렬하고 가장 큰 값 중 가장 오른쪽에 있는 게 마지막 위치가 된다.

import sys
input=sys.stdin.readline
a,b=map(int,input().split())
l=list(map(int,input().split()))
l=[[l[i],i]for i in range(a)]
l.sort()
print(l[a-1][1]+1)

 

이문제도 100 받을 수 있었는데 사소한 구현 실수로 100을 못 받았던 문제였다 ㅜㅜ

 

14. 파스칼 삼각형

감도 못 잡았다

 

15. 낙하 대미지

n이 작으므로 모든 선분에 대해 i에서 j로 가는 경우의 수를 모두 탐색해서 부분점수를 얻었다.

 

import sys,math
sys.setrecursionlimit(10**9)
inf=math.inf
input=sys.stdin.readline
a=int(input())
l=[list(map(int,input().split()))for i in range(a)]
for i in range(a):l[i].append(i)
l.sort(reverse=True)
l+=[[0,-inf,inf,0,0]]
#print(l)
#print(dp)
ans=[0]*(a+2)
ch=[inf]*(a+2)
def f(x,last):
    #print(x,last,i)
    if ch[x]!=inf:return ch[x]
    if x+1==a+1:return 0
    mi=inf#dp[x][a]
    if l[x][1]<=l[a][1]<=l[x][2]or l[x][1]<=l[a][2]<=l[x][2]or l[a][1]<=l[x][1]<=l[a][2]or l[a][1]<=l[x][2]<=l[a][2]:
        mi=(l[x][0]-l[a][0])**2+l[a][0]
    for ix in range(x+1,a):
        ty=inf
        io=f(ix,x)
        if l[x][1]<=l[ix][1]<=l[x][2]or l[x][1]<=l[ix][2]<=l[x][2]or l[ix][1]<=l[x][1]<=l[ix][2]or l[ix][1]<=l[x][2]<=l[ix][2]:
            ty=(l[x][0]-l[ix][0])**2+l[ix][3]
        io+=ty
        #print(io,x,ix,dp[x][ix])     
        #print(dp[last][ix],io,last,ix)
        mi=min(mi,io)
    ch[x]=mi
    ans[l[x][4]]=mi
    return mi
f(0,-1)
#print(ch)
#print(ans)
for i in range(a):
    print(ans[i])

 

 

2일 차까지는 올솔가능성이 보였는데 3회 차부터 학교+학원과 뇌절등 여러 가지 때문에 속도가 느려지고 4회 차에서 완전히 말아먹는 바람에 1204.2라는 점수를 얻게 되었다. 풀이를 들어보니 1300까지도 가능했는데 못한 게 아쉽고 또 작년보단 점수가 높아졌지만 본선을 못 간다는 게 아쉽고 내년에 더 열심히 해서 2022 본선 때는 꼭 갈 것이다.

지금까지 2021 nypc를 참가하신 모든 분들 수고하셨습니다