SRM 238 DIV1 Hard SquareLanguage

問題 Editorial

問題

let s = map (concatMap (uncurry replicate). flip zip "abcd").
  mapM (\[l, u]-> [l..u])$ [abounds, bbounds, cbounds, dbounds]
  in length. nub $(++) <$> s <*> s

を求めよ

解答

まず左と右の全ての文字が0文字かどうかを全探索し、そこで2つくっついてるのはまとめて、それの重複を省く。
それらに対して各文字の範囲を掛け算する

コメント

Editorial解わかってない。
この問題、もっと速くきちんと解けていいと思う

コード

#include <vector>
#include <set>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define pb(x) push_back(x)
using namespace std;
typedef vector<int> vi; typedef long long ll;
struct SquareLanguage {
	long long howMany(vector <int> ab, vector <int> bb, vector <int> cb, vector <int> db) {
		vi b[8] = {ab, bb, cb, db};
		rep(i, 4)
			if(b[i][0] == 0) b[4+i].pb(b[i][1]+1), b[4+i].pb(b[i][1]*2);
			else b[4+i].pb(b[i][0]*2), b[4+i].pb(b[i][1]*2);
		ll r = 0;
		set<vi> s;
		rep(i, 1<<8) {
			vi v, w;
			rep(j, 8) {
				if((i >> j) & 1) v.pb(j%4);
				else if(b[j%4][0] > 0) goto bad;
			}
			if(0) { bad: continue; }
			rep(j, v.size()) {
				if(j+1 < v.size() && v[j] == v[j+1]) w.pb(4 + v[j]), ++j;
				else w.pb(v[j]);
			}
			s.insert(w);
		}
		each(i, s) {
			ll x = 1;
			each(j, *i) x *= b[*j][1] - max(1, b[*j][0]) + 1;
			r += x;
		}
		return r;
	}
};