SRM498 Div1 Easy(250), Div2 Medium(500) FoxSequence
O(N)で書けるんだろうけど、どうせ間に合うならa,b,c,dを全探索した方が、コーディングが楽だしエンバグの可能性が減ると思う。
#include <string> #include <vector> using namespace std; class FoxSequence{public: string isValid( vector <int> seq ) { int N = (int)seq.size(); for ( int a=1; a<N-1; a++ ) for ( int b=a+1; b<N-1; b++ ) for ( int c=b; c<N-1; c++ ) for ( int d=c+1; d<N-1; d++ ) { if ( seq[ 1]-seq[0] <= 0 || seq[a+1]-seq[a] >= 0 || seq[c+1]-seq[c] <= 0 || seq[d+1]-seq[d] >= 0 ) goto fail; for (int i=0; i<=a-1; i++) if(seq[i+1]-seq[i]!=seq[1 ]-seq[0]) goto fail; for (int i=a; i<=b-1; i++) if(seq[i+1]-seq[i]!=seq[a+1]-seq[a]) goto fail; for (int i=b; i<=c; i++) if(seq[i]!=seq[b]) goto fail; for (int i=c; i<=d-1; i++) if(seq[i+1]-seq[i]!=seq[c+1]-seq[c]) goto fail; for (int i=d; i<=N-1-1;i++) if(seq[i+1]-seq[i]!=seq[d+1]-seq[d]) goto fail; return "YES"; fail:; } return "NO"; }};