ICPC2013国内予選F
F問題が良問だったので解説記事を書くことにしました。
The 2013 ACM-ICPC Asia Aizu Regional Contest :: Domestic contest problem set
解法は
この問題を解くには最初にCYK法で全ての部分区間についてある文字に変えられるかを調べる必要があります。
標準的なCYK法では書き換えルールは xy→z のように2文字から1文字に変えるルールしかないので、CYK内部で部分区間[i,j]をxy→zで書き換えられるかは Any(dp[i][k][x] And dp[k+1][j][y]) (k=i,i+1..,j-1)
で判定できますが、この問題では書き換え前の列の長さが2より大きいものがルールに含まれるので上記の方法ではできません。
ですがCYK法は区間DPなのである区間について考えるときその部分区間がある文字に書き換えられるかは全て求まっています。
なのでCYK内部で、ある区間をあるルールで書き換えられるかという問題は「文字列についてそれぞれの区間がある文字に変換できるという条件下で、与えられた文字列をある文字列に変換できるか」という問題として表せます。
これなら普通にコンテストの問題として出そうだしそれほど難しくもないDPで解けます。
つまりCYK内部である区間をあるルールで書き換え可能かの判定のためにさらにDPするわけです。
次にこの問題の厄介そうなルールに「回転」がありますがこれはあまり考えなくていいです。
というのも循環させて見れば回転しても並びの順番は変わらないからです。
ただし典型区間DPでは[a,b] (a<=b) というような区間しか考えないのですが(a>b)のような場合でも回転することによって(a
区間DPではある区間はそれより短い区間に依存するので区間の長さが短い順に確定させていけば何も考えなくてもトポロジカル順序を満たすので、区間DPを[a,b] (a>b)にも対応できるように拡張するのは簡単にできます。
あとはnm通りの回転の仕方について2つの列を最長一致させるDPすればいいだけですね。
実装面では数列に現れる数値の範囲は1〜30なので変換できる値はビットフラグで持っています。
これによって最後の2つの列を一致させる部分にビット毎の論理積を使えるので高速化できます。
計算量は O((n^4+m^4)rk + n^3m^3)
コメントなしの読みにくいコードですが見たい人はどうぞ
#include<iostream> #include<cstring> #include<vector> #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; struct Rule{ vector<int> x; int y; }; void CYK(int trans[25][25],vector<Rule> &rule,vector<int> s){ memset(trans,0,sizeof(int)*25*25); rep(i,s.size()){ trans[i][i] |= 1<<s[i]; } bool dp[26][11]; rep(j,s.size()){ rep(i,s.size()){ rep(k,rule.size()){ if(j+1<rule[k].x.size())continue; memset(dp,false,sizeof(dp)); dp[0][0]=true; rep(g,j+1){ rep(h,rule[k].x.size()){ if(!dp[g][h])continue; rep(f,j+1-g){ if(trans[(i+g)%s.size()][(i+g+f)%s.size()]>>rule[k].x[h]&1) dp[g+f+1][h+1]=true; } } } if(dp[j+1][rule[k].x.size()]) trans[i][(i+j)%s.size()] |= 1<<rule[k].y; } } } } int main(){ int n,m,r; vector<int> a,b; vector<Rule> rule; int transa[25][25],transb[25][25]; int dp[26][26]; while(cin>>n>>m>>r,n|m|r){ a.resize(n); b.resize(m); rep(i,n)cin>>a[i]; rep(i,m)cin>>b[i]; rule.resize(r); rep(i,r){ int k,v; cin>>k; rule[i].x.resize(k); rep(j,k){ cin>>v; rule[i].x[j]=v; } cin>>rule[i].y; } CYK(transa,rule,a); CYK(transb,rule,b); int ans=-1; int sa=a.size(),sb=b.size(); rep(i,n){ rep(j,m){ memset(dp,-1,sizeof(dp)); dp[0][0]=0; rep(k,n){ rep(f,m){ if(dp[k][f]==-1)continue; rep(g,n-k){ rep(h,m-f){ if(transa[(i+k)%sa][(i+k+g)%sa] & transb[(j+f)%sb][(j+f+h)%sb]) dp[k+g+1][f+h+1]=max(dp[k+g+1][f+h+1],dp[k][f]+1); } } } } ans=max(ans,dp[n][m]); } } cout<<ans<<endl; } return 0; }
TCO2013 Round1B
TCO2013 Round1B
250
ソートして両端から取るだけ
500
縦の選び方を決めると横の選び方はgreedyに求まるのでビット全探索
int getMoves(vector <string> board, int R, int C) { int h=board.size(),w=board[0].size(); int ans=INF; vector<int> b(h); rep(i,h){ int m=0; rep(j,w)if(board[i][j]=='X')m|=1<<j; b[i]=m; } rep(i,1<<h){ int m=0; for(int j=0;j<h;){ if(i&1<<j){ j+=R; }else { m|=b[j]; j++; } } int s=0; rep(j,h)if(i&1<<j)s++; for(int j=0;j<w;){ if(m&1<<j){ s++; j+=C; }else j++; } ans=min(ans,s); } return ans; }
1000
反転の操作は可逆だから例えばredotopcとodcpoterを同じ文字列にできる場合はそれぞれを操作して取り得る文字列の集合は等しくなる。また、可逆であることから異なる集合は必ず互いに素となる。よって集合毎の個数をカウントし奇数個となっている集合の個数が答えとなる。また、文字列は２文字ごとに見れば末尾からgreedyに当てはめて任意の順にソートでき、各集合は互いに素だから適当に正規化しておけば効率的にカウントできる。
int getMin(vector <string> words) { map<vector<pair<char,char> > ,int> mp; map<vector<pair<char,char> > ,int>::iterator it; rep(i,words.size()){ string &s=words[i]; vector<pair<char,char> > v; rep(j,s.size()/2){ v.push_back(make_pair(min(s[j*2],s[j*2+1]),max(s[j*2],s[j*2+1]))); } sort(v.begin(),v.end()); if(s.size()&1){ v.push_back(make_pair(s[s.size()-1],'\0')); } ++mp[v]; } int ans=0; for(it=mp.begin();it!=mp.end();++it){ if(it->second&1)ans++; } return ans; }
ウェーブレット行列を実装した
元のデータに対して十分小さいサイズでありながら各種操作を高速に処理でき、文字列のみならず2次元データやグラフデータまで表現できるというウェーブレット行列を実装してみた。「高速文字列解析の世界」とかブログとか読んでやっとのことで実装した。
ウェーブレット行列の各操作のオーダーの表記では、文字集合のサイズをσ、文字列長をnとしている。
2014/8/25:プログラム修正
inline int popCount(unsigned int x){ x = (x>>1 & 0x55555555)+(x & 0x55555555); x = (x>>2 & 0x33333333)+(x & 0x33333333); x = (x>>4 & 0x0f0f0f0f)+(x & 0x0f0f0f0f); x = (x>>8 & 0x00ff00ff)+(x & 0x00ff00ff); return (x>>16)+(x & 0x0000ffff); } inline int kthRightmostPop(unsigned int pop1,int k){ unsigned int pop2,pop4,pop8,pop16; int pos=0; pop2 = (pop1>>1 & 0x55555555)+(pop1 & 0x55555555); pop4 = (pop2>>2 & 0x33333333)+(pop2 & 0x33333333); pop8 = (pop4>>4 & 0x0f0f0f0f)+(pop4 & 0x0f0f0f0f); pop16= (pop8>>8 & 0x00ff00ff)+(pop8 & 0x00ff00ff); if((pop16 &0x0000ffff) <= k){ k -= (pop16 &0x0000ffff); pos |= 16; } if((pop8>>pos&0x000000ff) <= k){ k -= (pop8>>pos&0x000000ff); pos |= 8; } if((pop4>>pos&0x0000000f) <= k){ k -= (pop4>>pos&0x0000000f); pos |= 4; } if((pop2>>pos&0x00000003) <= k){ k -= (pop2>>pos&0x00000003); pos |= 2; } if((pop1>>pos&0x00000001) <= k)pos |= 1; return pos; } //簡潔ビットベクトル //メモリ使用量:2nビット class BitVector{ int n; int blocks; vector<unsigned int> B; vector<int> r; public: BitVector(){} BitVector(int size){ init(size); } void init(int size){ n = size; blocks = (n>>5)+1; B.assign(blocks ,0); r.assign(blocks ,0); } void set(int k){ B[k>>5] |= 1<<(k&31); } void build(){ r[0]=0; for(int i=1;i<blocks;i++){ r[i] = popCount(B[i-1]) + r[i-1]; } } bool access(int k)const{ return B[k>>5] & 1<<(k&31); } //[0,k)の1の個数 int rank(int k)const{ return r[k>>5] + popCount(B[k>>5] & ((1<<(k&31))-1)); } //k+1番目の１の場所 //O(log n) int select1(int k)const{ int lb=0,ub=blocks; if(k==-1)return -1; while(ub-lb>1){ int m = (lb+ub)/2; if(k<r[m])ub=m; else lb=m; } k -= r[lb]; return lb<<5 | kthRightmostPop(B[lb],k); } //O(log n) int select0(int k)const{ int lb=0,ub=blocks; if(k==-1)return -1; while(ub-lb>1){ int m = (lb+ub)/2; if(k<(m<<5)-r[m])ub=m; else lb=m; } k -= (lb<<5)-r[lb]; return lb<<5 | kthRightmostPop(~B[lb],k); } }; //ウェーブレット行列 //Σ=[A-Za-z] class WaveletMatrix{ static const int BITLEN = 6;//文字のビット長 int len; BitVector bv[BITLEN]; int encode(char c)const{//6bit if('A'<=c&&c<='Z')return c-'A'; return c-'a'+('Z'-'A'+1); } char decode(int n)const{ if(0<=n&&n<26)return n+'A'; return n-26+'a'; } struct Node{ int height,s,e,code; Node(){} Node(int a,int b,int c,int d):height(a),s(b),e(c),code(d){}; bool operator <(Node a)const{return e-s<a.e-a.s;} }; public: int length()const{ return len; } WaveletMatrix(const string &str){ init(str); } //O(n logσ) void init(const string &str){ len = str.size(); for(int i=0;i<BITLEN;i++){ bv[i].init(str.size()); } int *bucket; bucket = new int[2*len]; int *cur,*next; cur = bucket; next = bucket+len; int rank0[BITLEN]={0}; for(int i=0;i<len;i++){ int n = encode(str[i]); cur[i] = n; for(int j=BITLEN-1;j>=0;j--){ if((n&1<<j)==0)rank0[j]++; } } for(int i=BITLEN-1;;i--){ for(int j=0;j<len;j++){ if(cur[j]&1<<i)bv[i].set(j); } bv[i].build(); if(i==0)break; int idx0=0,idx1=rank0[i]; for(int j=0;j<len;j++){ if(cur[j]&1<<i)next[idx1++]=cur[j]; else next[idx0++]=cur[j]; } swap(cur,next); } delete[] bucket; } //O(logσ) char access(int k)const{ int code=0; for(int i=BITLEN-1;i>0;i--){ if(bv[i].access(k)){ code |= 1<<i; k = len-bv[i].rank(len)+bv[i].rank(k); }else{ k = k-bv[i].rank(k); } } if(bv[0].access(k))code |= 1; return decode(code); } //[s,e)中のcの個数 //O(logσ) int rank(char c,int s,int e)const{ int n = encode(c); for(int i=BITLEN-1;i>=0;i--){ int ssum = bv[i].rank(s); int esum = bv[i].rank(e); if(n&1<<i){ s = len-bv[i].rank(len) + ssum; e = s + esum-ssum; }else{ s = s-ssum; e = e-esum; } } return e-s; } //k+1番目のcの位置 //O(log n logσ) int select(char c,int k)const{ int n = encode(c); int s=0,e=len; for(int i=BITLEN-1;i>=0;i--){ int ssum = bv[i].rank(s); int esum = bv[i].rank(e); if(n&1<<i){ s = len-bv[i].rank(len) + ssum; e = s + esum-ssum; }else{ s = s-ssum; e = e-esum; } } int p = s+k; if(e<=p)return -1; for(int i=0;i<BITLEN;i++){ if(n&1<<i)p = bv[i].select1(p-(len-bv[i].rank(len))); else p = bv[i].select0(p); } return p; } //[s,e)中で出現頻度が多い順にk個返す //O(min(e-s,σ)logσ) ,頻度が偏っていればO(klogσ) vector<pair<char,int> > topk(int s,int e,int k)const{ vector<pair<char,int> > res; priority_queue<Node> pq; pq.push(Node(BITLEN-1,s,e,0)); while(!pq.empty() && 0<=k){ Node a = pq.top(); pq.pop(); if(a.height==-1){ res.push_back(make_pair(decode(a.code),a.e-a.s)); k--; continue; } int ssum = bv[a.height].rank(a.s); int esum = bv[a.height].rank(a.e); int num1 = esum-ssum; int num0 = a.e-a.s-num1; int s = a.s-ssum; pq.push(Node(a.height-1,s,s+num0,a.code)); s = len-bv[a.height].rank(len) + ssum; pq.push(Node(a.height-1,s,s+num1,a.code|1<<a.height)); } return res; } //[s,e)中のr+1番目に大きい文字 //O(logσ) char quantile(int s,int e,int r)const{ int code=0; for(int i=BITLEN-1;i>=0;i--){ int ssum = bv[i].rank(s); int esum = bv[i].rank(e); int num1 = esum-ssum; if(num1<=r){ r -= num1; s = s-ssum; e = e-esum; }else{ code |= 1<<i; s = len-bv[i].rank(len) + ssum; e = s + num1; } if(s==e)return '\0'; } return decode(code); } //[s,e)中のx未満の文字の個数 int rank_lt(int s,int e,char x)const{ int n = encode(x); int res=0; for(int i=BITLEN-1;i>=0;i--){ int ssum = bv[i].rank(s); int esum = bv[i].rank(e); if(n&1<<i){ res += e-s-(esum-ssum); s = len-bv[i].rank(len) + ssum; e = s + esum-ssum; }else{ s = s-ssum; e = e-esum; } if(s==e)return res; } return res; } //[s,e)中の x<=c<y となる文字の個数 //O(logσ) int rangefreq(int s,int e,char x,char y)const{ return rank_lt(s,e,y)-rank_lt(s,e,x); } //[s,e)中に出現する文字を大きい順に頻度と共にk個返す //O(k logσ) vector<pair<char,int> > rangemaxk(int s,int e,int k)const{ Node sta[BITLEN+1]; int sp=0; vector<pair<char,int> > res; sta[sp++] = Node(BITLEN-1,s,e,0); while(sp && 0<=k){ Node a = sta[--sp]; if(a.height==-1){ res.push_back(make_pair(decode(a.code),a.e-a.s)); k--; continue; } int ssum = bv[a.height].rank(a.s); int esum = bv[a.height].rank(a.e); int num1 = esum-ssum; int num0 = a.e-a.s-num1; int s = a.s-ssum; if(num0)sta[sp++] = Node(a.height-1,s,s+num0,a.code); s = len-bv[a.height].rank(len) + ssum; if(num1)sta[sp++] = Node(a.height-1,s,s+num1,a.code|1<<a.height); } return res; } //[s,e)中に出現する文字を小さい順に頻度と共にk個返す //O(k logσ) vector<pair<char,int> > rangemink(int s,int e,int k)const{ Node sta[BITLEN+1]; int sp=0; vector<pair<char,int> > res; sta[sp++] = Node(BITLEN-1,s,e,0); while(sp && 0<=k){ Node a = sta[--sp]; if(a.height==-1){ res.push_back(make_pair(decode(a.code),a.e-a.s)); k--; continue; } int ssum = bv[a.height].rank(a.s); int esum = bv[a.height].rank(a.e); int num1 = esum-ssum; int num0 = a.e-a.s-num1; int s = len-bv[a.height].rank(len) + ssum; if(num1)sta[sp++] = Node(a.height-1,s,s+num1,a.code|1<<a.height); s = a.s-ssum; if(num0)sta[sp++] = Node(a.height-1,s,s+num0,a.code); } return res; } //[s,e)中のx<=c<yとなる文字cを頻度と共に列挙する //返す文字種類をkとすると O(k logσ) vector<pair<char,int> > rangelist(int s,int e,char x,char y)const{ int ub = encode(y); int lb = encode(x); Node sta[BITLEN+1]; int sp=0; vector<pair<char,int> > res; sta[sp++] = Node(BITLEN-1,0,len,0); while(sp){ Node a = sta[--sp]; if(a.height==-1){ res.push_back(make_pair(decode(a.code),a.e-a.s)); continue; } int ssum = bv[a.height].rank(a.s); int esum = bv[a.height].rank(a.e); int num1 = esum-ssum; int num0 = a.e-a.s-num1; int s = len-bv[a.height].rank(len) + ssum; if((a.code|1<<a.height)<ub && num1)sta[sp++] = Node(a.height-1,s,s+num1,a.code|1<<a.height); s = a.s-ssum; if(lb<=(a.code) && num0)sta[sp++] = Node(a.height-1,s,s+num0,a.code); } return res; } };
ハル研究所プログラミングコンテスト2012
ハル研究所プログラミングコンテスト2012の参加記
結果は学生部門5位、総合6位でした。
工夫したこととか書いていきます。
・乱数の種を変えたりして実験したら最適解はトゲを踏んだり待機しないっぽいのでdist[x][y][トゲの周期][アイテム]で探索
・最初BFSしてたけどA*の方が速いのでそっちに切り替え
・ヒューリスティックはトゲを無視した最短路
・よく考えると行動した後の推定値の変動は+0,+1,+2のいずれかなのでヒープを使わず、バケットを4個用意して循環させて使い優先度付きDFSする
その他高速化の工夫
・とりあえずループ展開して条件判定を減らす
・距離テーブルのサイズが大きいので最初に全て初期化した後は更新箇所を記録しておきそこだけ初期化する
・配列が大きくなるならintではなくcharで宣言してキャッシュに載りやすくする（2倍ほど速くなって驚愕）
・hoge[24][24]とかはhoge[24][32]とするとコンパイラがシフトで最適化してくれる
・距離テーブルは一次元配列として宣言する
こんな感じでマクロを使ってアクセスしメモリを詰めて使用する
uchar dist[Constant::FIELD_WIDTH_MAX*Constant::FIELD_HEIGHT_MAX*Constant::SPINE_TURN_CYCLE*(Constant::SPINE_TURN_PAUSE+1)]; #define DIST(x,y,c,p) (dist[(((((x)*height+(y))*Constant::SPINE_TURN_CYCLE)+(c))*(Constant::SPINE_TURN_PAUSE+1))+(p)])
上下左右に移動する場合その中心座標のアドレスを計算しておくと移動先のアドレスは定数オフセットでアクセスできるので演算命令を減らせる。
オフセットは探索前に計算
const int down = Constant::SPINE_TURN_CYCLE*(Constant::SPINE_TURN_PAUSE+1); const int right = height*Constant::SPINE_TURN_CYCLE*(Constant::SPINE_TURN_PAUSE+1);
中心座標のアドレスを計算したら上下左右のアドレスはオフセットで計算できる
p[-down] p[-right] p[right] p[down]
Facebook Hacker Cup 2013 Qualification Round
Beautiful strings
やるだけ
void lower(string &s){ REP(i,s.size()){ if('A'<=s[i]&&s[i]<='Z')s[i] += 'a'-'A'; } } int main(){ int m; cin>>m; cin.ignore(); REP(i,m){ string s; getline(cin,s); lower(s); map<char,int> c; map<char,int>::reverse_iterator it; REP(j,s.size()){ if(s[j]<'a'||'z'<s[j])continue; ++c[s[j]]; } vector<int> v; for(it=c.rbegin();it!=c.rend();++it){ v.push_back(it->second); } sort(v.begin(),v.end(),greater<int>()); int ans=0,b=26; REP(j,v.size()){ ans += b*v[j]; b--; } cout<<"Case #"<<i+1<<": "<<ans<<endl; } return 0; }
Balanced Smileys
DPするだけ
bool dp[101][101]; int main(){ int m; cin>>m; cin.ignore(); REP(i,m){ memset(dp,false,sizeof(dp)); dp[0][0]=true; string s; bool colon=false; getline(cin,s); REP(j,s.size()){ if(s[j]=='('){//+1 for(int k=0;k<100;k++){ dp[j+1][k+1] = dp[j][k]; } }else if(s[j]==')'){//-1 for(int k=1;k<=100;k++){ dp[j+1][k-1] = dp[j][k]; } } if(s[j]!='('&&s[j]!=')'||colon){//0 for(int k=0;k<=100;k++){ dp[j+1][k] |= dp[j][k]; } } colon = s[j]==':'; } char *ans = dp[s.size()][0]?"YES":"NO"; cout<<"Case #"<<i+1<<": "<<ans<<endl; } return 0; }
Find the Min
最初のk個の後はk+1周期で同じのが続くのでそれらを計算。
setだと最初のk個で重複があると死ねるからk個前までに使われてるやつをmapで持っといた。
基本は0,1,2,・・・ってな風に小さい値から割り当てていくけど
添え字が進むことによって今見ている値よりも小さい値が使用可能になったらそっちを使う。
int main(){ int T; cin>>T; REP(i,T){ map<ull,int> m; vector<ull> v; vector<ull> cycle; ull n,k; ull a,b,c,r; cin>>n>>k; cin>>a>>b>>c>>r; ull val=a; REP(j,k){ v.push_back(val); ++m[val]; val =(b*val+c)%r; } ull cur=0; while(m.find(cur)!=m.end())cur++; REP(j,k+1){ if(0<j && --m[v[j-1]]==0){ m.erase(v[j-1]); if(v[j-1]<cur){ cycle.push_back(v[j-1]); }else{ cycle.push_back(cur); while(m.find(++cur)!=m.end()); } }else{ cycle.push_back(cur); while(m.find(++cur)!=m.end()); } } cout<<"Case #"<<i+1<<": "<<cycle[(n-k-1)%(k+1)]<<endl; } return 0; }
ブログ作ったー
気が向いたら更新していきます。
