ひっくり返す系の問題(ABC124D - Handstand)
まず、列を0(直立)の領域と1(逆立ち)の領域に分けます。
この領域は必ず交互に並んでいるので、ある状態にしたい場合に0の部分を選択してひっくり返した時が回数が最小です。(これって自明でいいのかな…?)
のでK個の直立グループをひっくり返したら繋がる部分、すなわち直立グループからK*2または逆立ちグループからK*2+1個のグループについて、総人数を数えて最大のものを答えとすれば良い。まあここら辺の実装は適当なんでしゃくとりとかもっといいのあると思います。というかまず両端は逆立ちのグループでいいよね。でも計算量変わらないから
コード
簡単だったのに、イテレータの-1らへんのごちゃごちゃを忘れていて一回WAってしまい、悲しい
#include<cstdio> #include<math.h> #include<algorithm> #include<vector> #include<queue> #include<string> #include<set> #include<cstring> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define INF 1001001001 #define LLINF 1001001001001001001 #define mp make_pair #define pb push_back #define LLIandI pair<long long int , int> #define ll long long int main(void){ int N,K; scanf("%d %d",&N,&K); char S[100002]; scanf("%s",S); int ans=0; int start=S[0]-'0'; int mae=0; vector<int> lens; vector<int> lenssum;lenssum.pb(0); rep(i,N){ if(i>0&&S[i]!=S[i-1]){lens.pb(i-mae);lenssum.pb(lenssum[lenssum.size()-1]+i-mae);mae=i;} if(i==N-1){lens.pb(i-mae+1);lenssum.pb(lenssum[lenssum.size()-1]+i-mae+1);} } rep(i,lens.size()){ int siz=K*2+( (i+start)%2 ); if(i+siz>=lenssum.size()){siz=lenssum.size()-i-1;} ans=max(ans,lenssum[i+siz]-lenssum[i]); } printf("%d\n",ans); }