第15回日本情報オリンピック 本選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#B - スタンプラリー 2 (Collecting Stamps 2)
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #B - スタンプラリー 2 (Collecting Stamps 2) https://atcoder.jp/contests/joi2016ho/tasks/joi2016ho_b 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; string s; cin>>s; s=" "+s; ll J[100001],I[100001],a[100001],b[100001]; ll ans1=0,ans2=0; for(ll i=1,j=0;i<=n;i++){ J[i]=J[i-1]+(s[i]=='J'); if(s[i]=='O'){ j+=J[i]; } a[i]=j; } for(ll i=n,j=0;i;i--){ I[i]=I[i+1]+(s[i]=='I'); if(s[i]=='O'){ j+=I[i]; } b[i]=j; } for(ll i=1;i<=n;i++){ if(s[i]=='O'){ ans1+=(J[i]*I[i]); } ans2=max(ans2,J[i]*I[i+1]); ans2=max(ans2,a[i]); ans2=max(ans2,b[i]); } cout<<ans1+ans2<<endl; return 0; }