| 
本番では全然できなかったが、他の方の解説やヒントを参考に後から書いてみた。(system test pass)
S[i] = sum(A[0]..A[i]) とすると、sum(A[i-k]..A[i]) > 0 <==> S[i]-S[i-k-1] > 0 と、(i, i-k-1) の間に制約ができる。
これを有向グラフとして表し、閉路がなければ無矛盾なので解ありとする。
これを 0 ～充分大きな長さの範囲で二分探索すると答えが出るという流れ。
閉路検出に帰着するのか！こんな発想ができるようになりたいものである...
あと max_element 知らなかった。STL の勉強になるので人のソース読むのはいいなぁ。
今回は使わなかったけど累積を計算する partial_sum もあるんすね。
閉路検出のルーチンで帰りがけにノードを記録するようにして最後に逆順にすると、トポロジカルソートになるようである。
#include <cassert> #include <iostream> #include <vector> #include <cstdlib> using namespace std; #define REP(i,n) for(int i=0;i<(int)n;++i) #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define ALL(c) (c).begin(), (c).end() typedef vector<int> Edge; typedef vector<Edge> Graph; bool tsort(Graph& g, int i, vector<int>& status, vector<int>& topo) { //cout<<"visit "<<i<<endl; status[i]=1; for(int j=0;j<g[i].size();j++) { if(status[g[i][j]]==1) return false; if(!status[g[i][j]] && !tsort(g, g[i][j], status, topo)) return false; } topo.push_back(i); status[i]=2; return true; } bool tsort(Graph& g) { int vn = g.size(); vector<int> status(vn, 0), topo; for(int i=0;i<vn;i++) { if(!status[i] && !tsort(g, i, status, topo)) return false; } //reverse(topo.begin(), topo.end()); //for(int i=0;i<topo.size();i++) { // cout<<topo[i]<<" "; //} //cout<<endl; return true; } int solve(vector<int>& cst) { int cn = cst.size(); if(*max_element(ALL(cst))<0 || *min_element(ALL(cst))>0) { return -1; } // S[i] = sum(A[0]..A[i]) // sum(A[i-k+1]..A[i]) > 0 <==> S[i]-S[i-k] > 0 // make edge i->j | S[i]>S[j] int low=0, high=10000; while(high-low>1) { int mid = (high+low)/2; Graph g(mid+1); // graph node 0..mid (mid+1) FOR(c, cst) { REP(i, mid+1-abs(*c)) { if(*c>0) g[i+abs(*c)].push_back(i); else g[i].push_back(i+abs(*c)); } } bool ret = tsort(g); //cout<<mid<<" "<<ret<<endl; if(ret) low=mid; else high=mid; } return low; } #define CHECK(cst, ref) check((cst), sizeof(cst)/sizeof(cst[0]), ref) int check(int cst[], int n, int ref) { vector<int> tmp(cst, &cst[n]); int ret = solve(tmp); if(ret!=ref) { FOR(v, tmp) cout<<*v<<endl; cout<<ref<<" but ret "<<ret<<endl; } return 0; } int main() { CHECK(((int[]){-2, 3}), 3 ); CHECK(((int[]){524}), -1 ); CHECK(((int[]){1, -1}), 0 ); CHECK(((int[]){11, -7}), 16 ); CHECK(((int[]){-227, 690, 590, -524}), 713 ); CHECK(((int[]){514, -514}), 513 ); CHECK(((int[]){524, -524}), 523 ); CHECK(((int[]){1}), -1 ); CHECK(((int[]){-1}), -1 ); CHECK(((int[]){1, 2, 3, -1, -2, -3}), 0 ); CHECK(((int[]){1000, -1000}), 999 ); CHECK(((int[]){1000, -999}), 1997 ); CHECK(((int[]){999, -1000}), 1997 ); : :
