코드포스 - 나는 바보다

에듀 라운드 131 업솔빙

Educational Codeforces Round 131 개요

이쯤 되면 컨디션 문제도 아닌것같다.
내가 그린은 어케 갔었는지도 의문이다.ㅋㅋㅋㅋㅋ
코포는 시간이 생명인데 영어에서 자꾸 절어서 시간이 오래걸리고 여전히 3솔을 못한다.ㅠㅠ
이제부턴 진짜 버추얼이라도 돌아봐야겠다.

A. Grass Field

너무 쉬웠는데 한번 틀렸다.
영어를 잘못 이해했다. 자신을 포함해서 총 3개의 칸이 지워지는건데 왜 2개라고 읽었는지 모르겠다.
바보 같은 실수로 절고 7분 걸렸다.

int cnt=0;
for(int i=0;i<2;i++){
    for(int j=0;j<2;j++){
        cin >> board[i][j];
        if(board[i][j]) cnt++;
    } 
}
if(cnt==4) cout << 2 << '\n';
else if(cnt==0) cout << 0 << '\n';
else cout << 1 << '\n';

B. Permutation

이거는 해석을 오히려 잘해서 헷갈렸다.
해석한 걸로 따지면 d가 2일 때가 최적이고 그냥 그걸 출력하면 된다.
그러면 d가 의미가 있나 싶어서 말도 안되는 증명하다가 시간 다 보냈다.
그래서 2틀하고 에라이 그냥 d가 2인걸로 하자 했더니 AC나옴..ㅡㅡ


cout << 2 << '\n';  //d는 무조건 2가 최적
for(int i=1;i<=n;i++){
    if(visited[i]) continue;
    for(int j=i;j<=n;j*=2){
        if(visited[j]) continue;
        cout << j << ' ';
        visited[j] = true;
    }
}

C. Schedule Management

솔직히 많이 배운 문제이다.
처음에는 dp인가 하다가 아닌것같아서 다시 생각해보니
[이중 우선순위 큐] https://www.acmicpc.net/problem/7662 .
가 생각났다. 그래서 우선순위 큐 2개로 다뤄봤는데 디버깅하다가 우선순위큐가 중복을 허용하지 않는다는 걸 알았다.
그래서 멘붕왔는데 내 풀이를 버리질 못하고 서성대다가 끝나버렸다.
다른분들중에 나랑 같은 생각하신 분은 multiset을 이용하여 풀었더라…
멀티셋을 활용하는걸 잘 알아둬야겠다.
에디토리얼에는 이분탐색으로 푸는 방법이 나와있고 내가 이분탐색을 매우 못한다는 것을 깨달았다.


bool check(int t){
    ll fr =0, need = 0;
    for(int i=1;i<=n;i++){
        if(t>=nums[i]) fr += (t-nums[i])/2; //자기 일 끝내고 남는 시간
        else need += nums[i] -t;    // 자기 일을 못끝내서 남는 시간
    }
    return need<=fr;    //시간이 여유로우면 참을 리턴
}

int l = 0, r = 2*m; // 모든일을 2시간이 걸려서 하면이 최대고
        int res = -1;
        while (l<=r){   //이분탐색으로 제일 여유로운 시간중 최솟값을 찾는다
            int mid = (l+r)>>1;
            if(check(mid)){
                res = mid;
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        cout << res << '\n';

D. Permutation Restoration

나에겐 넘 어려웠다 어떤 상황인지는 알겠는데 아이디어가 진짜 안 떠올랐다.
그래서 10분보고 그냥 버렸던 것 같다.
핵심은 수학적으로 처음 배열과 수정된 배열의 관계를 알아내는 것이다.
그러면 범위가 나오고 그 범위의 시작점이 작으면서 끝점도 작은 것 부터 해결한다.
에디토리얼을 보고도 굉장히 까다로웠던 문제였다.

original = vector<int> (n+1);
modify = vector<int> (n+1);
seg = vector<pii> (n+1, make_pair(-1, -1));
for(int i=1;i<=n;i++) cin >> modify[i];
for(int i=1;i<=n;i++){
    seg[i] = make_pair(i/(modify[i]+1)+1,i);   //i번째 idx의 수는 i/modift[i]+1 이상이다
}
sort(seg.begin(), seg.end());
int j =1;
set<pii> s;
for(int i=1;i<=n;i++){
    while (j<=n&&seg[j].first==i){
        int idx = seg[j++].second;
        s.insert(make_pair(modify[idx]?idx/modify[idx]:n, idx));    //idx번째 수는 first이하이다.
    }
    original[s.begin()->second] = i;
    s.erase(s.begin());
            
}
for(int i=1;i<=n;i++) cout << original[i] << ' ';
cout << '\n';

Leave a comment

2024

D&C Optimization

3 minute read

분할정복을 이용한 다이나믹 프로그래밍 최적화

Back to top ↑

2023

Back to top ↑

2022

Greedy

2 minute read

백준 18186번 라면사기(large) 문제풀이

SCC

1 minute read

백준 4196번 도미노 문제풀이

LCA

2 minute read

백준 3176번 도로 네트워크 문제풀이

2-SAT

1 minute read

백준 16367번 TV Show Game 문제풀이

Hashing

2 minute read

백준 21162번 뒤집기 K 문제풀이

Tree DP

1 minute read

백준 1949번 우수 마을 문제풀이

Trie

1 minute read

Trie 자료구조 이해하기

Merge Sort

1 minute read

merge sort를 이용하여 inversion 개수세기

Segment Tree

2 minute read

백준 11505 구간 곱 구하기 문제풀이

BFS

1 minute read

백준 2206 벽 부수고 이동하기 문제풀이

기하

1 minute read

백준 2166 다각형의 면적 문제풀이

이분탐색

1 minute read

백준 12015 가장 긴 증가하는 부분 수열2 문제풀이

누적 합

1 minute read

백준 10986 나머지합 문제풀이

Stack

1 minute read

스택 구현하기 ========== 자료구조의 기본이라고 하면 스택 과 큐가 있다 백준 10828번에서 마주친 스택

정렬1

1 minute read

매우매우 많은 정렬이 있지만 그중 가장 안 어려운 3가지를 공부해보았다.

Back to top ↑