寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #B - JJOOII 2 (JJOOII 2)

JOI 2019/2020 本選 過去問から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#B - JJOOII 2 (JJOOII 2)

atcoder.jp

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#B - JJOOII 2 (JJOOII 2)
https://atcoder.jp/contests/joi2020ho/tasks/joi2020ho_b
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
  ll n,k;
  cin>>n>>k;
  string s;
  cin>>s;
  vector<ll> a(n+1),b(n+1),c(n+1);
  for(ll i=0;i<n;i++){
    a[i+1]=a[i]+(s[i]=='J');
    b[i+1]=b[i]+(s[i]=='O');
    c[i+1]=c[i]+(s[i]=='I');
  }
  ll ia=0,ib=0,ic=0;
  const ll inf=1e+9;
  ll ans=inf;
  for(ll i=0;i<n;i++){
    for(;ia<=n;ia++){
      if(a[ia]-a[i]>=k){
        break;
      }
    }
    if(ia>n){
      break;
    }
    for(;ib<=n;ib++){
      if(b[ib]-b[ia]>=k){
        break;
      }
    }
    if(ib>n){
      break;
    }
    for(;ic<=n;ic++){
      if(c[ic]-c[ib]>=k){
        break;
      }
    }
    if(ic>n){
      break;
    }
    ans=min(ans,ic-i);
  }
  if(ans>=inf){
    cout<<-1<<endl;
  }else{
    cout<<ans-3*k<<endl;
  }
  return 0;
}