SRM317 div2

//ふつうに、0~100000000でループしてたらおそらく間に合わない．
//なので、123  4  321みたいになるはずだから、
//m = ss.str(); reverse(m.begin(), m.end() ); と仕込みしておいて、
//	string tmp = (i != 10) ?  (ss.str() + c + m) : (ss.str() + m);みたいにすればよろしいかと．
//setLLにしているのは、99999 5 99999 //つまり、11桁にしてる(めんどくさいから)ため。
class PalindromicNumbers {
public:
  int countPalNums(int lower, int upper) {
    set<LL> validNum;
    for(int i = 1; i <= 9; i++) {
      validNum.insert(i);
    }
    for(int i = 1; i < 100000; i++) {
      stringstream ss;
      ss << i;
      string m = ss.str(); reverse(m.begin(), m.end() );
      for(int i = 0; i <= 10; i++) {
	char c = i + '0';
	string tmp = (i != 10) ?  (ss.str() + c + m) : (ss.str() + m);
	int num; sscanf(tmp.c_str(), "%d", &num);
	validNum.insert(num);
      }
    }
    set<LL>::iterator beg, end;
    beg = validNum.lower_bound(lower);
    end = validNum.lower_bound(upper);
    int flag = (*end == upper) ? 1 : 0;
//そして、単純に,beg-endはできず、こういうかたちに。境界条件についてはNo Problemだとおもう。
//beg - validNum.begin() とかもできない。
    return vector<LL>(beg, end).size() + flag;
				   
  }

//最後のとこはこうかくとcool
return (int)distance(validNum.lower_bound(lower), validNum.upper_bound(upper) );

difficult

良く分からんかったので、他人の解答見たらビット演算してた。

  000 001 011 111
          101 111
      010 110 111
          011 111
      100 110 111
          101 111
よーく見るとビットで順番を表しているのが分かる。そうか、おなじみの全探索だ！

詳しく見てみる。
{"NNNN",
 "YNNY",
 "NNNN",
 "YNNN"
0001のとき,最初に0番目の要素が配置された状態。
i = 0  //(i&(1<1としたいけど、req[1][0] = 'Y'なので、無理ですよ、ということ。

以下同様。

//一番分かりやすかったのを改変した。
  long long countOrderings(vector <string> req) {
    int sz = req.size();
    map<int, LL> work;
    work[0] = 1;
    for(int i = 0; i < (1<<sz); i++) {
      for(int j = 0; j < sz; j++) {
        if( (i&(1<<j)) == 0) {
          bool flag = true;
          for(int k = 0; k < sz; k++) {
            if((i&(1<<k)) && req[j][k] == 'Y') {
              flag = false; break;
            }
          }
          if(flag) work[i|(1<<j)] += work[i];
        }
      }
    }
    return work[(1<<sz)-1];
              
  }