코드포스 - 또 3솔의 벽
codeforce round #807(div 2) 업솔빙
Codeforces Round #807 개요
하… 진짜 미칠 것 같다 이번엔 A, B를 20분 만에 풀어서 2시간동안 한 문제만 풀어도 3솔의 벽을 깨는 건데…
그걸 못했다. 2시간동안 C,D하나 풀기를…ㅠㅠ
이쯤 되면 이번 방학 목표를 코드포스 3솔로 바꿔야 할 것 같다.(원래 블루였음ㅋㅋ)
내 생각보다 블루, 퍼플이 엄청 대단한 사람들이란걸 몸소 느낀다.
A. Mark the Photographer(0:05)
정렬하고 반 나눠서 연산하면 바로 끝이다.
근데 n이 주어지고 n/2가 주어지는게 아니라 이미 절반을 한 값을 준다는 특징이 있었다.
그래서 좀 어버버하다가 5분에 AC
1
2
3
4
5
6
7
8
9
10
int n, x; cin >> n >> x;
vector<int> height(2*n+1);
for(int i=1;i<=2*n;i++) cin >> height[i];
sort(height.begin(), height.end());
bool possible = true;
for(int i=1;i<=n;i++){
if(height[i+n]-height[i]<x) possible = false;
}
if(possible) cout << "YES\n";
else cout << "NO\n";
B. Mark the Dust Sweeper(0:18)
이 문제까진 꽤 느낌이 좋았다.
왜냐면 내가봐도 좀 잘풀었기 때문이다.
먼지를 뒤로 모는 문제고 0이 중간에 껴있는경우 턴을 좀 더 써야한다.
그래서 스위핑으로 끝점 빼고 먼지+추가적인 턴을 더해서 단 3줄로 끝냈다.
1
2
3
4
5
6
7
8
9
int n; cin >>n;
rooms = vector<ll> (n+1);
ll res = 0;
for(int i=1;i<=n;i++){
cin >> rooms[i];
if(i!=n) res += rooms[i];
if(!rooms[i]&&res&&i!=n) res++;
}
cout << res << '\n';
C. Mark and His Unfinished Essay(upsolving)
마크한테 실망했다. substr문제인가 하고 보니 쿼리의 범위가 long long형까지 갔다..
당연히 메모리 초과 날걸 알았지만 해봤고 역시 메모리 초과가 났다.
그렇다면 연산으로 역추적? 을 해야하는데 그게 생각이 1도 안났다.
string이 계속 바뀌는데 어케 역추적을 해야하지..라는 생각을 하다가 시간 다쓰고 망했다.
첫 글자랑 위치만 저장해볼까 했는데 그게 string이 바뀌니깐 너무 곤란했다. ㅠㅠ
에디토리얼 보니 비슷하다..다만 왼쪽 오른쪽 복사된 idx만 저장하는게 아니라 diff라는 이름의 배열로 왼쪽 시작점-왼쪽 쿼리시작점을 뺀것을 저장한다.
이것의 의미는 바로 이전 시작점인것이다.
왜 이걸 못했을까…?
솔직히 좀 좋은 문제였다.
1
2
3
4
5
6
7
8
9
for(int i=0;i<q;i++){
ll k; cin >> k;
k--;
for(ll j=c;j>=1;j--){
if(k<left[j]) continue;
k -= diff[j];
}
cout << str[k] << '\n';
}
D. Mark and Lightbulbs(upsolving)
C보다 이게 더 나을 것 같아서 꽤 오래 본 문제이지만 어..이건가?? 하는데 반례가 계속 나왔다 ㅠㅠ
일단 하나의 전구를 바꿀 수 있어서 그걸 바꾸면 그 양옆의 상태가 변한다는 특징이 있었다.
- 모든 상태를 변화시킬 수 없을 때
- 양 끝은 어짜피 바꿀 수 없는데 양끝이 다를 때 이 두 경우가 -1을 출력하는 경우라고 생각하고 문제를 풀었다.
핵심은 구간을 한칸씩 옮길 수 있다는 것이고 이를 계산 할 때- abs(l-l’)+abs(r-r’)
이런 식으로 계산 할 수 있다는 것이다.
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
ll n, c,q;
int main(){
fast_io;
int test; cin >> test;
while (test--) {
int n; cin >> n;
string s1, s2;
cin >> s1 >> s2;
bool ok = true;
if(s1[0]!=s2[0]||s1[n-1]!=s2[n-1]) ok = false;
vector<int> pos1, pos2;
for(int i=0;i<n-1;i++){
if(s1[i]!=s1[i+1]) pos1.push_back(i);
if(s2[i]!=s2[i+1]) pos2.push_back(i);
}
if(pos1.size()!=pos2.size()) ok = false;
if(ok){
ll res = 0;
for(int i=0;i<pos1.size();i++){
res += abs(pos1[i]-pos2[i]);
}
cout << res << '\n';
}else{
cout << -1 << '\n';
}
}
}