USACO SILVER::2020 US Open Contest Cereal

• Link : USACO BOJ::18878
• Link : USACO contest::usaco

Cereal

• level : Gold 3
• tag : offline query, recursion, sort

Point

• n 과 m이 주어집니다.
• n 마리의 소와 m개의 시리얼을 의미합니다.
• 이후, n마리의 소가 좋아하는 시리얼 두 종류를 순서대로 주어집니다.
  • 앞에 주어지는 것을 더 좋아합니다.
• 이제, [1:n] 순서를 순회하며 다음과 같은 과정을 진행합니다.
  • 현재 시작 인덱스가 i인 경우,
  • i번째 소가 시리얼을 선택합니다.
  • 이후, i+1번째 소가 시리얼을 선택합니다.
  • … n번째 소가 시리얼을 선택합니다.
  • 시리얼을 차지한 소의 수를 출력합니다.
• 단, 다음과 같은 조건을 만족하며 시리얼을 선택해야 합니다.
  • i번째 소의 첫번째 우선순위 시리얼을 아무도 차지하고 있지 않은 경우, i번째 소가 차지합니다.
  • 그렇지 않은 경우,
    • i번째 소의 두번째 우선순위 시리얼을 아무도 차지하고 있지 않은 경우, i번째 소가 차지합니다.
  • 둘 다 차지되어있는 상태인 경우, i번째 소는 시리얼을 차지하지 못합니다.
  • 또한, 위의 시뮬레이션은 앞에있는 소부터 순서가 주어집니다.

Design(x)

• solution 을 참고하였습니다.
• 앞에서부터 순서대로 소들에게 우선순위를 주는 방법은 O(N^2)을 벗어나지 못합니다.
• 이때, 순서만 뒤에서부터로 바꾸면 TLE를 면할 수 있고, 이렇게 순서를 바꾸는 발상도 꼭 필요하다고 생각합니다.
• 방법은 다음과 같습니다.
• 뒤에있는 소부터 순서대로 순회합니다.
• 따라서, 현재 index i 번째 소의 차례가 오면 해당 소의 first가 최우선순위를 가지게 됩니다.
• case는 3가지로 분류됩니다.
  • 해당 시리얼을 차지한 소가 아무도 없는 경우
    • 이 경우, 해당 시리얼을 차지하면 됩니다.
  • 누군가 해당 시리얼을 차지했고, 현재 소보다 인덱스가 앞에 있는 소가 차지한 경우
    • 이 경우, 해당 시리얼을 포기해야 합니다.
  • 누군가 해당 시리얼을 차지했고, 현재 소보다 인덱스가 뒤에 있는 소가 차지한 경우
    • 이 경우, 해당 시리얼을 뺏습니다.
    • 이후, 원래 해당 시리얼을 차지했던 소의 시리얼 위치를 찾아줍니다. ( second 시도 )
• 위와 같은 방법으로 하면 왜 TLE가 나지 않을까요?
  • 단순한 생각으로는 최악의 경우 O(N^2)이 나올것이라고 생각됩니다.
• 하지만, 모든 소는 결국 2개의 choice밖에 없습니다.
• 따라서 최대 2번의 move만 가능합니다.
• 이를 통해, 복잡도는 O(2N)이라는 것을 알 수 있습니다.

Big O(time)

• O(2N)

Big O(memory)

Code(x)

#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define all(v) (v).begin(), (v).end()
#define f first
#define s second
#define pb push_back
#define vi vector<int>
#define vpi vector<pair<int,int> >
#define vvpi vector<vector<pair<int,int> > >
#define EMPTY 0
typedef long long ll;
const int MAXN = 100000 + 10;
using namespace std;

int n, m;
int ans[MAXN];
int cereal[MAXN]; // 해당 시리얼을 차지한 소의 인덱스
int f[MAXN], s[MAXN];

void process(){
    cin >> n >> m;
    rep(i, 0, n) cin >> f[i] >> s[i];

    int cnt = 0;
    r_rep(i, n-1, -1){
        int j = i; // who
        int pos = f[i]; // want to take position of cereal
        while(1){
            if(cereal[pos] == EMPTY){ // 비어있으면 바로 차지하고
                cnt++;
                cereal[pos] = j;
                break;
            }else if(cereal[pos] < j){ // 누가 있는데, 나보다 앞에 있는 소가 차지하고 있으면 포기!
                break;                 // 신기한건 이게 소 중심이 아니라, 시리얼 중심이라는 점. 그래서 second 비벼보지 않음
            }else{ // 누가 있는데, 나보다 뒤에 있는 소가 차지하고 있음!
                int tmp = cereal[pos];
                cereal[pos] = j;
                // 현재 시리얼을 원래 차지하고 있던 뒤에 있는 소의 second가 현재 시리얼 위치였다면 break
                // 즉, 새로 온 소가 해당 위치를 차지하고 종료.
                if(pos == s[tmp]) break;
                // 그렇지 않다면, 현재 시리얼을 차지하고 있던 뒤에 있던 소의 second 위치를 또 탐색해주기.
                j = tmp;
                pos = s[tmp];
            }
        }
        ans[i] = cnt;
    }
    rep(i, 0, n) cout << ans[i] << endl;
}

int main(){
    process();
    return 0;
}