SRM 316 Div1 Easy InboxCleanup

問題概要

各メールが必要かどうかが文字列messagesによって与えられるとき、不要なメールを全て削除するのに必要な最低クリック回数を求めよ。

メーラが1ページに表示するメールの数は、最初にlow以上high以下から選ぶ。
メーラはクリック1回で以下のような操作が可能である。

• ページに表示されているメール1通を「選択しているメールに加える」
• 選択されているメール1通を選択しているメールから外す
• 選択されているメールを全て削除する
• 全てのメールを選択する
• 次のページを表示する

解法

1ページに表示するメールの数をlow以上high以下で全て試す。
各ページでそれぞれ、全てを選択してからメールをいくつか外す方式と、削除するメールだけを選択していく方式の効率の良いほうを選べばよい。

ソースコード

	int fewestClicks(string messages, int low, int high) 
	{
		int ans=inf,n=messages.size();
		for(int a=low;a<=high;a++)
		{
			int c=n/a+(n%a!=0)-1;
			rep(i,n/a+(n%a!=0))
			{
				string s=messages.substr(i*a,a);
				int t=count(all(s),'D');
				if(t==0)continue;
				
				c+=min(t,(int)s.size()-t+1)+1;
			}
			ans=min(ans,c);
		}
		return ans;
	}

System Test

Passed.
しかし遅すぎる……orz