티스토리 뷰
Contest #1
이 문제는 문제 이름에도 적혀있듯이 정렬 문제이다. 문제를 잘 읽어보면 두 가지 문제가 합쳐졌음을 알 수 있다.
첫번째는 맨 처음 과정이다. 초기 배열을 v에 저장하고 투 포인터를 활용해서 각 부분 내리차순을 reverse시킨다.
최종적으로 v는 여러개의 부분 오름차순으로 정렬된 상태이다. vector stl을 활용하여 reverse(l,r)을 사용하면 구현이 가능하다.
그 다음은 정렬 과정은 인접한 숫자 쌍 하나씩 변한다. 앞에서 만든 부분 오름차순의 경계에서는 무조건 감소하는 숫자 쌍이 존재한다. 그 숫자쌍을 reverse 해주는 횟수를 세면 된다. 하지만 이는 삽입 정렬 시 움직이는 횟수와 일치한다. 이 문제는 펜윅 트리를 이용해서 O(log N)의 시간복잡도로 해결 가능하다.
6. SKAKAC
해설집을 봤지만 못 풀겠음
Contest #2
A를 이루는 각 숫자 배열을 x[1000]
B를 이루는 각 숫자 배열을 y[1000] 이라 하자.
이때 x[0]와 y[0]~y[N-1]까지 차례대로 최대공약수를 구하는데 만약 gcd를 구했으면 답에 gcd를 곱해주고 x[0]는 gcd로 나눠주고 계속해서 최대공약수를 구해준다.
위의 과정이 끝나면 x[1]와 y[0]~y[N-1]까지 같은 연산을 수행하고. ..x[N-1]까지 수행하면 된다.
문제에서 답이 9자리보다 길때만 앞에 00...0을 붙여야 함을 주의하자.
두 수를 이루는 숫자가 하나면 겹쳐도 친구이다. 해시 문제이다. 자릿수를 이루는 숫자는 0~9까지 이므로 각 수를 이진수로 다음과 같이 대응시킬 수 있다.
359-->1000101000
12 --> 0000000110
이렇게 하면 각 수가 최대 2^10=1024를 벗어나지 않는 선에서 대응을 시킬 수 있다.
또한 각 수의 숫자가 겹치는 것을 확인하는 것도 각 수가 대응된 이진수를 i,j라 했을 때 i&j와 같이 비트연산으로 쉽게 구할 수 있다. 시간 복잡도는 2^20이다.
해설집 봐도 모르겠다.
엄청난 세그먼트 트리 문제이다. 사실 문제를 이해만 한다면 간단한 세그먼트 트리지만 구현이 까다로웠다.
문제를 수학적으로 표현을 한다면 다음의 문제로 바꿀 수 있음을 쉽게 알 수 있다.
Ti를 오름차순 정렬시킨 후, ∑(i∗Ti) 값을 구해주면 된다.
예를 들어
Ti 가 1 2 4 4 5 5
에서 1 2 3 4 4 5
로 5가 3으로 변했다고 생각하자. 그럼 답은 5*5가 줄고 3*3이 늘고 3과 5사이 있던 숫자의 합(4+4=8)이 늘 것이다.
따라서 숫자 배열 Ti가 있을 때 x보다 작은 숫자 개수를 구해주는 세그먼트 트리와 1~x까지의 숫자 합을 구해주는 세그먼트 트리가 필요하다.(여기까지 적어놓고 나니 펜윅트리로 구현하는 것이 더 쉬워보인다. 어차피 합을 구하는것이 목표라면 펜윅이 더 간단하다) 이 때 각 숫자가 몇개 있는지 따로 카운트해주는 cnt배열을 만들면 구현이 더 쉬워진다.
많은 시행착오 끝에 결국 구현을 했지만 다시는 풀고 싶지 않다.
코드는 밑에 첨부한다.
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define MAX 100000
int cnt[MAX+1];
int L[2*MAX+1];
int T[2*MAX+1];
long long sort_t[2*MAX+1];
long long sum_l;
long long sum_t;
long long seg[MAX*4][2];
int N,C;
long long ans;
void update(int node,int nodel,int noder,long long val,int pos,int ch){
if(pos>noder||pos<nodel) return;
if(nodel<=pos && pos<=noder){
seg[node][ch]+=val;
if(nodel==noder) return;
int mid=(nodel+noder)/2;
update(node*2,nodel,mid,val,pos,ch);
update(node*2+1,mid+1,noder,val,pos,ch);
}
}
long long query(int node,int nodel,int noder,int l,int r,int ch){
/*개수*/
if(ch==0){
if(noder<l||nodel>r) return 0;
if(l<=nodel&&noder<=r) return seg[node][0];
int mid=(nodel+noder)/2;
return query(node*2,nodel,mid,l,r,0)+query(node*2+1,mid+1,noder,l,r,0);
}
//sum
else{
if(noder<l||nodel>r) return 0;
if(l<=nodel&&noder<=r) return seg[node][1];
int mid=(nodel+noder)/2;
return query(node*2,nodel,mid,l,r,1)+query(node*2+1,mid+1,noder,l,r,1);
}
}
int main(){
cin>>N>>C;
for(int i=1;i<=N;i++){
long long l,t;
scanf("%lld %lld",&l,&t);
L[i]=l;
sort_t[i]=T[i]=t;
cnt[t]++;
sum_l+=l;
sum_t+=t;
update(1,1,MAX,1,t,0);
update(1,1,MAX,t,t,1);
}
ans+=sum_l;
ans-=sum_t*(N+1);
sort(sort_t+1,sort_t+N+1);
for(long long i=1;i<=N;i++)
ans+=i*sort_t[i];
printf("%lld\n",ans);
for(int i=0;i<C;i++){
long long n,r,t;
scanf("%lld %lld %lld",&n,&r,&t);
ans+=(r-L[n]);
L[n]=r;
ans-=(t-T[n])*(N+1);
if(t>T[n]){
ans-=T[n]*(query(1,1,MAX,1,T[n],0));
ans+=t*(query(1,1,MAX,1,t,0)-cnt[t]);
ans-=query(1,1,MAX,T[n]+1,t-1,1);
}else if(t<T[n]){
ans-=T[n]*(query(1,1,MAX,1,T[n],0)-cnt[T[n]]+1);
ans+=t*(query(1,1,MAX,1,t,0)+1);
ans+=query(1,1,MAX,t+1,T[n]-1,1);
}
cnt[T[n]]--;
cnt[t]++;
update(1,1,MAX,1,t,0);
update(1,1,MAX,-1,T[n],0);
update(1,1,MAX,t,t,1);
update(1,1,MAX,-T[n],T[n],1);
T[n]=t;
printf("%lld\n",ans);
}
}
Contest #3
dfs트리 문제로 재밌는 문제이다.
1번 사람부터 차례대로 dfs과정을 통해 각 사람의 방문 순서를 저장하자.
void dfs(int i){
dtn[i]=cnt;
st[i]=cnt;
cnt++;
for(int ele:ch[i]){
dfs(ele);
}
en[i]=cnt;
}이런식으로 각 사람 i의 st[i]에 그 사람의 방문순서가 저장되고 en[i]에 i의 부하들을 dfs해서 다 방문 하고 그 다음 방문 순서가 저장된다. 이렇게 배열에 값을 저장해 놓으면 i의 부하들의 월급을 모두 x만큼 더해준다고 할 때
st[i]+1부터 n까지 노드에 x를 더하고 en[i]부터 n까지의 노드에 x를 빼면 된다. 당연히 각 사람의 방문 순서를 각 사람의 번호로 변환해주는 배열이 필요하다.
6. TRAKA
못풂
Contest #4
잘 생각해보면 지그재그 모양의 울타리에서 local max인 지점과 local min인 부분에 최댓값과 최솟값을 넣어주면 된다.
먼저 가지고 있는 울타리를 길이 순으로 정렬한다.(vector v)
그 다음 구현의 편의를 위해서 정렬된 울타리의 작은쪽에서 큰쪽으로 증가하는 포인터 v[f]
와 큰 쪽에서 작은쪽으로 내려가는 포인터 v[e]를 생각하자.
각각의 울타리를 사용하고 나면 f++, e--로 다음 울타리로 접근 가능하다.
먼저 위의 그림처럼 생겼다고 하면 파란색 점의 두번째, 세번째 점의 위치에 가장 긴 울타리 두 개를 저장한다. 그리고 다음으로 긴 울타리를 첫번째 파란점 위치에 저장한다. 마찬가지로 가장 작은 두 울타리를 첫 번째, 두번째 빨간색 점에 저장하고 그다음으로 작은 울타리를 세번째 빨간점에 저장한다.
이제 나머지 점들에 해당하는 울타리를 넣어줘야 하는데 맨 왼쪽에서부터 시작해서
초록색 부분처럼 오름차순에 해당하는 경우에는 v[f++] 로 하나씩 채워주고
보라색 부분처럼 내림차순에 해당하는 경우에는 v[e--]로 하나씩 채워주면 끝난다.
Contest #5
DP문제이다.
가장 왼쪽 K개의 분자를 A로 바꾸는데 필요한 최소 돌연변이 개수를 dp1[k]
가장 왼쪽 K개의 분자를 B로 바꾸는데 필요한 최소 돌연변이 개수를 dp2[k]
로 설정하자.
case1. k번째 분자가 A
dp1[k]=dp1[k-1]
//k-1번째까지 다 A로 바꾸고 k개를 한번에 B로 바꾸거나, k번째를 B로 바꾸고 나머지 k-1번째까지를 B로 바꾸기
dp2[k]=min(1+dp1[k-1],1+dp2[k-1])
case2. k번째 분자가 B
dp2[k]=dp2[k-1]
dp1[k]=min(1+dp1[k-1],1+dp2[k-1])
Contest #6
스택을 이용해서 두 괄호가 쌍이 맞으면 (쌍이맞는 괄호의 발견 순서를 k라 하자) 그 괄호 쌍을 이진수 a=1<<k로 저장하자.
그러면 만약 괄호쌍이 5개 발견된다면 a=11111(2)로 저장될 것이다.
a를 1씩 줄여가면서 다음의 과정을 통해 괄호가 제거된 string을 만들자
string 원문을 하나씩 비교해가면서 괄호가 나타나면 그 괄호에 해당하는 a 상의 위치를 보고 0이면 그 괄호를 제거해야하는 것이다. 그렇게 string이 만들어지면 set<string>ans에 저장하자. 알아서 사전순으로 정렬된다.
코드를 첨부한다
|
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<utility>
#include<string.h>
#include<set>
#include<stdlib.h>
#include<string>
#include<utility>
#include<stack>
using namespace std;
stack<int>st;
set<string>v;
int k=0;
int p[300];
int brac=0;
int main(){
string s;
cin>>s;
int len=s.size();
for(int i=0;i<len;i++){
if(s[i]==')'){
p[i]=k;
p[st.top()]=k;
st.pop();
brac+=1<<k;
k++;
}
}
brac--;
while(brac!=-1){
string s1="";
for(int i=0;i<len;i++){
if(s[i]=='(' || s[i]==')'){
if(brac&(1<<p[i])) s1+=s[i];
}
else s1+=s[i];
}
v.insert(s1);
brac--;
}
for(set<string>::iterator it=v.begin();it!=v.end();it++){
cout<<*it<<'\n';
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'알고리즘' 카테고리의 다른 글
| Codeforces Round #610 (Div. 2) (0) | 2020.01.03 |
|---|---|
| coci 2012/2013 (0) | 2019.11.03 |
| KOI 2016 중등부 해설 (0) | 2019.10.12 |
| KOI 2016 초등부 해설 (0) | 2019.10.10 |
| KOI 2018 중등부 풀이 (0) | 2019.10.10 |