これは★2.5でもいい気がする。
https://yukicoder.me/problems/no/910
問題
奇数の数字だけで構成された整数が与えられる。
ここから、素数を成す連続部分文字列を選び削除することを繰り返す。
最大何回削除ができるか。
解法
極力短い文字を削除したいので、以下の順で削除する。
- 3,5,7は単独で削除
- その後、19の並びを削除
- 残りは99...9911....11のような形となる。ここから991をできるだけ削除し、その後11を削除しよう。
int N; string S; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>S; int L1=0,L9=0,ret=0; FORR(c,S) { if(c=='3' || c=='5' || c=='7') ret++; else if(c=='1') { L1++; } else if(c=='9') { if(L1) { L1--; ret++; } else { L9++; } } } x=min(L9/2,L1); ret+=x+(L1-x)/2; cout<<ret<<endl; }
まとめ
入力に偶数も入ってたらどのぐらい難しくなるかな。