HackerRank 101 Hack May 4問目 - Almost sorted interval

Source

HackerRank 101 Hack May 4問目
problem statement(コンテストページ)
problem statement

問題概要

$1$ から $N$ の置換 $A_1,A_2,\ldots,A_N$ が与えられる.
区間 $[i,j], \;\; 1 \leq i \leq j \leq N$ で次の条件を満たす物の数を求める問題:
$A_i,A_{i+1},\ldots,A_{j}$ の中で,最小値は $A_i$ で最大値は $A_j$.

解法

色々解き方はあるが,自分が解いた方法を紹介する.
まず,真ん中の要素 $A_k, \;\; k=\lfloor N/2 \rfloor$ を含む条件を満たす区間の数を求める.
それが $O(N)$ で求められれば,$A_1,A_2,\ldots,A_{k-1}$ および $A_{k+1},A_{k+2},\ldots,A_N$ に対する問題を再帰的に解けば良いので,全体としても $O(N)$ で解ける.
$A_k$ から左に向かってなぞっていき,$A_k$ とその左の各要素間の最小の値,最大の値を計算する.
同様に,右に向かってもなぞっていき,$A_k$ との間の最小の値,最大の値を計算しておく.
条件を満たす可能性のある左端の候補は $A_k$ と自分との間の最小値が自分自身のところで,右端の候補は,最大値が自分と一致するところで,以降はそれらの場所のみを考える.
左端の候補を $1$ つずつ順番に調べて行った時,右端としてありうる範囲は,今まで計算してきた最大値最小値などを用いて調べることができる.
これを尺取法で調べることで,(おそらく)$O(N)$ の計算量で全ての左端について,条件を満たす右端の範囲を求めることができる.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(ll x, char c){int i,sz=0,m=0;char buf[20];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

int N, A[2000000];

int left_val[2000000], left_mx[2000000], lef;
int righ_val[2000000], righ_mn[2000000], rig;

ll solve(int a, int b){
  int i, j, k, mn, mx;
  int c;
  ll res = 0;

  if(b<a) return 0;
  if(a==b) return 1;
  if(a+1==b){
    res += 2;
    if(A[a]<A[b]) res++;
    return res;
  }

  c = (a+b)/2;
  lef = rig = 0;
  mn = mx = A[c];
  for(i=c;i>=a;i--){
    if(A[i] <= mn){
      mn = A[i];
      left_val[lef] = mn;
      left_mx[lef] = mx;
      lef++;
    }
    if(A[i] >= mx){
      mx = A[i];
    }
  }

  mn = mx = A[c];
  for(i=c;i<=b;i++){
    if(A[i] >= mx){
      mx = A[i];
      righ_val[rig] = mx;
      righ_mn[rig] = mn;
      rig++;
    }
    if(A[i] <= mn){
      mn = A[i];
    }
  }

  j = rig - 1;
  k = 0;
  rep(i,lef){
    while(j>=0 && righ_mn[j] < left_val[i]) j--;
    while(j+1<rig && righ_mn[j+1] > left_val[i]) j++;
    if(j<0) continue;

    while(k < rig && righ_val[k] < left_mx[i]) k++;
    while(k-1 >= 0 && righ_val[k-1] > left_mx[i]) k--;
    if(k >= rig) continue;
    if(j < k) continue;

    res += j-k+1;
  }

  res += solve(a,c-1);
  res += solve(c+1,b);
  return res;
}

int main(){
  int i, j, k;
  ll res;

  reader(&N);
  rep(i,N) reader(A+i);

  res = solve(0, N-1);
  writer(res, '\n');

  return 0;
}

Current time: 2017年07月23日17時42分54秒
Last modified: 2014年06月27日16時08分33秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_101may14
トップページに戻る

Logged in as: unknown user (not login)

ログイン: