[Codeforces 1159B] Expansion coefficient of the array

[Codeforces 1159B] Expansion coefficient of the array - 1300

문제 설명 : 

문제에 나와있듯이 모든 i,j pair에 대해서 k*(abs(i-j) <= min(a_i,a_j) 를 만족시키는 k의 최대값을 구하는 문제이다. 

풀이 : 

콘테스트중에는 1시간 넘게 고민했는데 못 풀었다. 1300짜리 문제인데 왜 못 풀었을까...

이 문제는 O(N)풀이가 있고 O(NlogN) 풀이가 있다. O(N)풀이는 매우 간단하지만 콘테스트 시간에 생각해내기는 버거웠다. 그 풀이는 1~n까지의 모든 a_i를 보면서 a_i를 1과 n까지의 거리 중에서 더 큰 값으로 나눠주기만 하면 된다. 그래서 n개의 수 중에서 가장 작은 값을 찾으면 된다. 처음에 이 풀이를 봤을 때는 어떻게 가능하지에 대해서 의문이 들었다. 왜냐하면 1이나 n중에서 가장 큰 거리를 취한다는 말은 현재의 a_i가 양 끝 값보다 반드시 작아야한다는 보장이 있어야 하기 때문이다. 만약 반대로 현재 a_i값이 양 끝 값보다 크다면, 양 끝 값은 더 작다는 의미이고 거리는 현재 거리보다 더 클 것이므로 이 풀이가 성립하는 것이다.

O(NlogN)풀이는 이보다는 쉽게 납득할 수 있는 풀이이다. 결국 이 문제의 핵심은 현재 a_i값보다 큰 수 중에서 가장 멀리 떨어진 거리가 얼마인가? 를 빨리 구하는 것이 핵심이다. 그 방법은 a_i와 인덱스 번호 i를 pair로 저장한 뒤 a_i를 기준으로 오름차순 정렬한다. 그런 다음 뒤에서부터 보면서 저장되었던 인덱스 최대값, 최소값을 배열에 저장한다. 이 배열은 위에서 말했듯이 현재 a_i값보다 큰 수 중 가장 멀리 떨어진 거리를 저장하는 배열이다다. 즉 가장 멀리 떨어진 거리를 O(1)만에 구할 수 있게 해준다. 

주의할 점 : 

-

배울 점 : 

정렬해놓고 뒤에서부터 살피면서 O(1)만에 가장 멀리 떨어진 거리를 구할 수 있었다. 배열을 이용하면 바로 현재 값은 바로 뒤의 배열만 참조해서 값을 비교하면 되기 때문에 시간을 줄일 수 있는 것이다.

코드 : 

O(N)풀이

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b){
        a=_a;
        b=_b;
    }
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 300009;
 
 
int main(){
    int n;    scanf("%d",&n);
 
    int ans=1<<30;
    for(int i=1 ; i<=n ; i++){
        int inp;    scanf("%d",&inp);
 
        ans=min(ans,inp/max(i-1,n-i));
    }
    printf("%d\n",ans);
 
    return 0;
}

O(NlogN) 풀이

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b){
        a=_a;
        b=_b;
    }
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 300009;
 
pii arr[SIZE];
int suf_max[SIZE],suf_min[SIZE];
 
int main(){
    int n;    scanf("%d",&n);
 
    for(int i=1 ; i<=n ; i++){
        int inp;    scanf("%d",&inp);
        arr[i]={inp,i};
    }
 
    sort(arr+1,arr+1+n);
 
    suf_max[n+1]=0,suf_min[n+1]=SIZE;
 
    for(int i=n ; i ; i--){
        suf_max[i]=max(suf_max[i+1],arr[i].second);
        suf_min[i]=min(suf_min[i+1],arr[i].second);
    }
 
    int ans=1<<30;
    for(int i=1 ; i<=n-1 ; i++){
        int cur_idx=arr[i].second;
        int mx=max(abs(suf_max[i]-cur_idx),abs(suf_min[i]-cur_idx));
        ans=min(ans,arr[i].first/mx);
    }
    printf("%d\n",ans);
 
    return 0;
}