保存されている過去のバージョンの一覧

2014年09月22日23時26分33秒
2014年05月10日02時35分05秒
2014年05月10日02時30分20秒

HackerRank Weekly Challenges - Week 2 4問目 - Travel around the world

Source

HackerRank Weekly Challenges - Week 2 4問目
problem statement（コンテストページ）
problem statement

問題概要

$N$ 個の街があって，街 $k$ から街 $k+1\ {\rm mod}\ N$ に移動することができる（$k=0,1,\ldots,N-1$）．
街 $k$ では $A_k$ ガロンの燃料を（$1$ 回だけ）補給でき，街 $k$ から街 $k+1\ {\rm mod}\ N$ に移動するには $B_k$ ガロンの燃料が必要となる．
燃料タンクは最初は空で，最大で $C$ ガロンまで燃料を入れることができる．
すべての街を通って最初に街に戻ってきたい．
そのようなことが達成できる最初の街は何通りあるかを求める問題．

解法

まず，サイクルを崩して，街 $N$ を街 $0$ と同じと考え，$A_k = A_{k-N},\ B_k = B_{k-N}$ として，街の数を $2N$ より大きくしておく．
街 $k$ から街 $k+N$ に辿り着ける街 $k$ の数（$0 \leq k < N$）を数える問題になる．
次に，最初の街になれる候補を考える．
最初，十分たくさんの燃料を積んでいて，かつ，燃料タンクも無制限に積めると思うと，街を移動するたびに燃料は $A_k-B_k$ だけ増える．
そこで，
　　$\displaystyle \verb|arr[|k\verb|]| = \sum_{i=0}^{k-1} (A_i - B_i)$
を計算しておくと，街 $a$ から街 $b$ に移動した時の燃料の増え方は $\verb|arr[|b\verb|]| - \verb|arr[|a\verb|]|$ で計算できることになる．
すべての移動区間で燃料が負になってはいけないので，街 $k$ に対して，$\verb|arr[|k\verb|]|,\verb|arr[|k+1\verb|]|,\ldots,\verb|arr[|k+N\verb|]|$ のどれかが $\verb|arr[|k\verb|]|$ を下回るようであれば街 $k$ を出発点とすることはできない．
これらが下回るかどうかは，スライド最小値を用いて計算すると，$O(N)$ で全ての街 $k$ に対して出発点となりうるかどうかを判定することができる．
さて，以上の観点から見て出発点の候補となったが，実際は $1$ 周回ることができないというのは，途中で燃料タンクがいっぱいとなって十分な燃料を詰めなかったときのみである．
逆に，燃料タンクがいっぱいで $1$ 周できなったことを考えると，どこを始点としても $1$ 周できないことになることがわかる．
なぜなら，燃料タンクが満タンの状態から燃料が足りないとなる区間が存在するので，どうしてもその区間を越えられないし，その区間の途中から始めてもダメだから．
ということは，$1$ 個でも実際に $1$ 周回って帰ってくることができるルートが存在すれば，全てのルートで燃料タンクの容量制限は何も問題にならないことがわかる．
そこで，始点の候補のうちの $1$ 個を用いて実際にシミュレーションしてみて $1$ 周回って帰ってこれるかどうかを調べる．
帰ってこれるなら，候補の数がそのまま答えで，帰ってこれないなら，答えは $0$．
合計で時間計算量は $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 reader(ll *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(int x, char c){int i,sz=0,m=0;char buf[10];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);}

template<class T>
void slideMin(int n, int k, T in[], T res[], void *mem){
  int i, s = 0;
  T *q = (T*) mem;
  int q_st = 0, q_size = 0;

  rep(i,n){
    while(q_size && q[q_st+q_size-1] > in[i]) q_size--;
    q[q_st+q_size++] = in[i];
    if(i>=k && in[i-k]==q[q_st]) q_st++, q_size--;
    if(i>=k-1) res[s++] = q[q_st];
  }
}

int N; ll C;
int a[200100], b[200100];
ll sum[200100], mn[200100];

int main(){
  int i, j, k;
  int A, B, D;
  int res = 0, ok = 0;
  ll now;
  void *mem = malloc(10000000);

  reader(&N);
  reader(&C);
  rep(i,N) reader(a+i);
  rep(i,N) reader(b+i);

  rep(i,N+20) a[i+N] = a[i];
  rep(i,N+20) b[i+N] = b[i];
  sum[0] = 0;
  rep(i,2*N+20) sum[i+1] = sum[i] + a[i] - b[i];

  slideMin(2*N+20, N+1, sum, mn, mem);
  rep(i,N) if(sum[i]==mn[i]){
    if(!ok){
      now = 0;
      rep(j,N){
        now = min(now+a[i+j], C) - b[i+j];
        if(now < 0) break;
      }
      if(j==N) ok=1; else break;
    }
    res++;
  }

  writer(res, '\n');

  return 0;
}

Current time: 2024年04月20日13時52分03秒
Last modified: 2014年09月22日23時26分33秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_w2
トップページに戻る

Logged in as: unknown user (not login)

ログイン：