kmjp's blog

競技プログラミング参加記です

yukicoder : No.910 素数部分列

これは★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;
}

まとめ

入力に偶数も入ってたらどのぐらい難しくなるかな。