Codeforces Good Bye 2014 A問題 - New Year Transportation

Source

Codeforces Good Bye 2014 A問題 (500pt)
Problem description

問題概要

$1$ から $N$ までの $N$ 個のノードが有る．
要素数 $N-1$ の整数列 $\{A_k\}_{k=1}^{N-1}$ が与えられ，ノード $k$ からノード $k+A_k$ に移動できることを意味する．（逆向きには移動できない）
ノード $1$ からスタートして，ノード $T$ に辿り着けるかどうかを判定する問題．

解法

移動の仕方は一意なのでシミュレーションすれば良い．
以下のコードではDPっぽく処理をした．
時間計算量は $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 READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

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);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

int N, D, A[1000000], ok[1000000];

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

  reader(&N,&D); D--;
  rep(i,N-1) reader(A+i);
  ok[0] = 1;
  rep(i,N-1) ok[i+A[i]] |= ok[i];

  writerLn(ok[D]?"YES":"NO");

  myed;
  return 0;
}

Current time: 2024年04月19日09時15分23秒
Last modified: 2015年01月11日08時27分35秒 (by laycrs)
Tags: Competitive_Programming Codeforces Codeforces_Good_Bye_2014
トップページに戻る

Logged in as: unknown user (not login)

ログイン：