SRM 510 Div2 Medium TheLuckyGameDivTwo

問題

4と7からなる数字がlucky number.
Johnはaからbの範囲の中からjLenだけ連続する範囲を抜き出す.BrusはJohnが抜き出した範囲の中からbLenだけ連続する範囲を抜き出す.出力は最終的な範囲の中に含まれるlucky numberの数.Johnは出力を最大化したい.Brusは出力を最小化したい.両者とも最適な戦略をとった時の出力を求めよ.

解答

全てのJohnとBrusの戦略をシミュレートして,その中で最適な答えを求める.

class TheLuckyGameDivTwo {
public:
  int find(int a, int b, int jLen, int bLen) {
    vector<int> less(b+1);
    vector<int> M(b+1);
    int i, j;

    less[0] = 0;
    for(i = 1; i <= b; i++){
      bool luckyflag = true;
      j = i;
      while(j > 0){
        if (!((j%10) == 4 || (j%10) == 7)){
          luckyflag = false;
          break;
        }
        j /= 10;
      }
      less[i] = less[i-1];
      if(luckyflag) {
        less[i]++;
        // cout << i << " is lucky number less[i]" << less[i] << endl;
      }
    }
    int ret = 0;
    for(i = a; i + jLen-1 <= b; i++){
      int v = 5000;
      for(j = i; j + bLen -1 <= i + jLen-1; j++){
        v = min(v, less[j+bLen-1] - less[j-1]);
        // cout << "less[" << j+bLen-1 << "]=" << less[j+bLen-1] << " less[" << j-1 << "]=" << less[j-1] << endl;
        // cout << "v=" << v << endl;
      } 
      if (v != 5000) ret = max(ret, v);
    }
    return ret;
  }
};