TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

文字列が与えられるので，その中に含まれているDを消したい．pageの単位を$low \sim high$文字にすることが出来る．出来る操作として

今見ているページの中にあるメッセージを1つ選択する
今見ているページの中にある選択しているものを1つ解除する
今見ているページを全て選択する
今見てるページで選択されているもの全てを削除する
次のページに行く

最小何回で全てのDを消すことが出来るか．

全て選択して，選択しているものを削除すれば全てのページは少なくとも2回でいけると勘違いしていたが，D以外を選択している状態で全ての削除をすることはできない．ページを何文字単位にするかは$low \sim high$全て試して，それぞれのページ事に1つ1つ消した方が良いのか，全てのを選択してD以外を解除して全て消すかのどちらが最小となるかをチェックした．

Code

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<28
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

class InboxCleanup {

    public:

    int fewestClicks(string messages, int low, int high) {
      int n = messages.size();
      int ans = INF;
      REP(t, low, high + 1) {
          int D = 0, len = 0, res = n / t - (n % t == 0);

          rep(i, n) {
              if(messages[i] == 'D') D++;
              len++;

              if(len % t == 0) {
                  len = 0;
                  if(D != 0) {
                      res += min(t - D + 1 + 1, D + 1);
                      D = 0;
                  }
              }
          }

          if(len != 0 && D != 0) {
              res += min(len - D + 1 + 1, D + 1);
          }

          ans = min(ans, res);
      }
      return ans;
    }
};

ry0u_ydのblog

SRM316 D1E-D2M InboxCleanup

TopCoder Statistics - Problem Statement

Code