SRM 238 DIV1 Hard SquareLanguage
問題
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; } };