第18回ABC C問題「菱型カウント」
C: 菱型カウント - AtCoder Beginner Contest #018 | AtCoder
解法：３０点解法を枝刈りする
O(RCN)(Nはxの数)ぐらいになるので、Nが300以下ぐらいのケースに対して枝刈りを適用すると時間内に解くことができる。
枝刈りは
・確実に範囲外になってしまう座標(計算が結構めんどくさい)
・近くにxが無い座標
どちらかの条件を満たす場合に行う。
#include <iostream> #include <cstdio> #include <cstdlib> #include <math.h> #include <vector> #include <queue> #include <algorithm> #include <sstream> #include <string> using namespace std; #define FOR(I,N) for(int I = 0; I < (int)(N); I++) #define FIN(V) cout<<V<<endl #define pb push_back #define INF (1 << 30) typedef pair<int, int> P; string sValueOf(int v){stringstream ss;ss<<v;return ss.str();} int parseInt(string v){int i;stringstream ss(v);ss>>i;return i;} void fast_io() {cin.tie(0); ios::sync_with_stdio(false);} int map[504][504]; int h,w,k; vector<P> black; int main(){ int i,j,m,l; cin>>h>>w>>k; fill_n(*map,504*504,1); string in; FOR(i,h){ cin>>in; FOR(j,w){ char c = in[j]; if(c=='o'){ map[j+1][i+1] = 0; }else{ map[j+1][i+1] = 1; black.pb(P(j+1,i+1)); } } } int ans = 0; int dis = 2*k-1; int size = black.size(); FOR(i,h)FOR(j,w){ int x = j+1; int y = i+1; if(j<k-1)continue; if(w-j<=k-1)continue; if(h-i<=dis-1)continue; if(size<=300){ int cy = y+k-1; double mini = INF; FOR(m,size){ mini = min(mini,sqrt(pow(black[m].first-x,2.0)+pow(black[m].second-cy,2.0))); } if(mini>k){ans++;continue;} } int width = 1; bool able = true; FOR(m,dis){ if(map[x][y+m]){able = false;break;} } if(!able)continue; FOR(m,dis){ FOR(l,width){ if(map[x+l][y]){able = false;break;} } if(!able)break; y++; if(m>=k-1){///後半 x++; width-=2; }else{ x--; width+=2; } } if(able){ ans++; } } cout<<ans<<endl; return 0; }
PCK2012本選「イヅア辞書」
AOJ0271
想定解よりも良い解が見つかったので
O(RNlogN)
このlogNはかなり小さいのでほぼ無視してよい。
探索により解を見つける場合、可能性はN!通りあるので現実的ではない。
が、同じ文字が複数出現しないことを利用すると計算により位置を求めることができる。
具体的にはN分岐の木構造をイメージすると分かりやすい。
深さDがD文字目の分岐に相当すると考える事で1文字目から順番に計算することで解を導くことが出来る。
また、想定解はBITを用いてO(NlogN)だがBITの代わりにstd:vectorを使うことでO(N^2logN)が達成できる。
vector.erase()のオーダーが重くTLEになってしまうこの解法ですが、RがNに比べ極端に小さい事を利用した座標圧縮を行うことができます。
値が連続する部分をD文字分一まとめに処理(計算)することでこれが実現できる。
最悪のケースを考えてもRは50、つまり圧縮すれば本来のNの部分が１つRに置き換わるのでO(RNlogN)が達成出来る。
実際にこの解法はAOJにおいて最大ケースでも0.11msとかなりの高スコアが出せるのでstd:vectorの応用性の高さに感動できる良い問題だと思いました。
#include <iostream> #include <cstdio> #include <cstdlib> #include <math.h> #include <vector> #include <queue> #include <algorithm> #include <sstream> #include <string> #include <map> using namespace std; #define FOR(I,N) for(int I = 0; I < (int)(N); I++) #define FIN(V) cout<<V<<endl #define pb push_back #define INF (1 << 30) #define MOD (1000000007) #define ll long long int d,n; vector<int> sorted; ll rui[100001]; int array[100001]; int main(){ int i,j; int r,a,b; rui[0] = 1; FOR(i,100001){ if(i!=0){ rui[i] = (rui[i-1]*i)%MOD; } } while(cin>>n,n){ cin>>r; sorted.clear(); FOR(i,n){ array[i] = i; sorted.pb(i); } sort(sorted.begin(),sorted.end()); FOR(i,r){ cin>>a>>b;a--;b--; swap(array[a], array[b]); } ll ans = 0; FOR(i,n-1){ vector<int>::iterator index = lower_bound(sorted.begin(),sorted.end(),array[i]); vector<int>::iterator aft = index; ans+= (index-sorted.begin())*rui[n-i-1]; ans%=MOD; int count = 0; for(j = i+1;j<n-1;j++){///いくつ連続してるか if(array[j]!=array[j-1]+1)break; count++; ans+= (index-sorted.begin())*rui[n-i-1-count]; ans%=MOD; } i = j-1; aft+=count+1; sorted.erase(index,aft+1); } cout<<ans<<endl; } return 0; }
PCK2014予選「バトンリレーゲーム」
Nが非常に大きいこと、クエリ操作が必要なことから高度なデータ構造の問題のように思えるが、交換回数が非常に小さい事に着目すれば実際は尺取法であることに気付く。
M (5 ≤ M < 200000)
ai (1 ≤ ai ≤ 100)
文中の操作とまったく同じ操作を行えるデータ構造を用意すれば
O(M*ai)により余裕をもって間に合う。
またこのような操作を実現するデータ構造を双方向連結リストというらしい(別名Deque)
#include <iostream> #include <algorithm> using namespace std; #define FOR(I,N) for(int I = 0; I < (int)(N); I++) #define FIN(V) cout<<V<<endl #define pb push_back #define INF 1 << 30 #define SIZE 1000000 typedef pair<int, int> P; int deque[SIZE]; int bi,ai; void clearDeque(){ fill_n(deque,SIZE,-1); bi = SIZE/3; ai = bi-1; } void addDeque(int value){ ai++; deque[ai] = value; } void query1(){ ai++; if(ai==SIZE)ai = 0; deque[ai] = deque[bi]; deque[bi] = -1; bi++; if(bi==SIZE)bi = 0; } void query2(){ bi--; if(bi==-1)bi = SIZE-1; deque[bi] = deque[ai]; deque[ai] = -1; ai--; if(ai==-1)ai = SIZE-1; } bool flag[200001]; int main(){ int i,j; int n,m,q,a; cin>>n>>m>>q; clearDeque(); FOR(i,n){ addDeque(i); } fill_n(flag,200001,1); FOR(i,m){ cin>>a; FOR(j,a){ if(a%2==0)query1(); else query2(); } ///cout<<deque[bi]<<endl; flag[deque[bi]] = 0; deque[bi] = -1; bi++; } FOR(i,q){ cin>>a; cout<<flag[a]<<endl; } return 0; }
単純に配列を使ってこのデータ構造を実現しようとすると、操作回数はM*ai=20000000にも及ぶのでメモリオーバーを起こしてしまう。
なので、先頭が-1(index)に到達したら
ai--; if(ai==-1)ai = SIZE-1;
このように先頭を配列の一番後ろに飛ばしてしまうとよい。
SRM649
レート 0→1300
明日JOIの参加記を書く予定
JOI2014本選 「フクロモモンガ」
ダイクストラ法なのですが、コストの持ち方を工夫する必要があります。
memo[N] = 累計コスト+(木の高さ-現在位置)
このように持つと、正しくダイクストラ法により解を求めることが出来ます。
木の上下移動は最小限に抑える必要がありますが、木の距離から上下移動が必要かは簡単に調べることが出来るので、pushする前に上下移動が必要かどうかをその都度計算により調べます。
#include <bits/stdc++.h> using namespace std; #define ll long long #define FOR(I,N) for(int I = 0;I<(int)(N);I++) #define P pair<ll,ll> #define pb push_back #define INF 9223372036854775807 struct Node{ vector<P> edges; int at; ll height; Node(int at_,ll height_){ at = at_; height = height_; } Node(){} }; vector<Node> ns; int main(){ int i,j; ll n,m,x,h,a,b,c; cin>>n>>m>>x; FOR(i,n){ cin>>h; ns.pb(Node(i,h)); } FOR(i,m){ cin>>a>>b>>c;a--;b--; ns[a].edges.pb(P(b,c)); ns[b].edges.pb(P(a,c)); } ll memo[100001]; fill_n(memo,100001,INF); priority_queue<P> que; vector<P> alp; alp.pb(P(0,x)); que.push(P(-(ns[0].height-x),alp.size()-1)); ll ans = INF; while(que.size()){ P data = que.top();que.pop(); P data2 = alp[data.second]; ll cost = -data.first; int index = data2.first; ll tx = data2.second; if(memo[index]<=cost)continue; memo[index] = cost; if(index==n-1){ ll tcost = cost-(ns[index].height-tx); ans = min(ans,tcost+ns[index].height-tx); ///break; } FOR(i,ns[index].edges.size()){ int nind = ns[index].edges[i].first; ll distance = ns[index].edges[i].second; ll tcost = cost-(ns[index].height-tx);///本来のコスト ll ncost; ll nx; if(tx-distance<0){///移動後の位置がマイナスになる if(ns[index].height<tx+distance-tx)///高さ足りない continue; ncost = tcost+distance-tx+distance+ns[nind].height-0; nx = 0; }else if(ns[nind].height<tx-distance){///移動後の位置が木の高さ超える ncost = tcost+(tx-distance)-ns[nind].height+distance+0; nx = ns[nind].height; }else{ ncost = tcost+distance+ns[nind].height-(tx-distance); nx = tx-distance; } alp.pb(P(nind,nx)); que.push(P(-ncost,alp.size()-1)); } } if(ans==INF)ans=-1; cout<<ans<<endl; return 0; }
PCK2014予選 「天体観測」
AOJに問題が登録されたので解いてみました。
AOJ0302
予め星の輝きをソートしておきます。
ある星Aを決めると、(Aの輝き)以上かつ(Aの輝き+d)に最も近い星までが星座を作る星になるので、
その様に選んだ時の長方形の面積Sの大きさは
S = (星座内で最も大きいX座標-最も小さいX座標)(最も大きいY座標-最も小さいY座標)
となり、これを高速に求めるためにRMQを用います。
全ての星に対してこの操作を行った時の最も大きい長方形の面積が解となります。
#include<bits/stdc++.h> using namespace std; #define ll long long #define FOR(I,N) for(int I = 0;I<(int)(N);I++) #define P pair<ll,ll> #define pb push_back #define INF 10000000000 vector<P> datas; P sorted[200001]; ll sortedV[200001]; ll BSEG[1<<19][2];///x,y ll MSEG[1<<19][2];///x,y void updataB(int index,int t){ if(index==0)return; int l = index*2,r = index*2+1; ll tmp = BSEG[index][t]; if(BSEG[l][t]<BSEG[r][t]){ BSEG[index][t] = BSEG[r][t]; }else{ BSEG[index][t] = BSEG[l][t]; } if(BSEG[index][t]==tmp)return; updataB(index/2,t); } void updataM(int index,int t){ if(index==0)return; int l = index*2,r = index*2+1; ll tmp = MSEG[index][t]; if(MSEG[l][t]>MSEG[r][t]){ MSEG[index][t] = MSEG[r][t]; }else{ MSEG[index][t] = MSEG[l][t]; } if(MSEG[index][t]==tmp)return; updataM(index/2,t); } ll getMin(int a,int b,int k,int l,int r,int t){ if(b<l||r<a)return INF; if(a<=l&&r<=b)return MSEG[k][t]; ll lm = getMin(a,b,k*2,l,(r-l)/2+l,t); ll rm = getMin(a,b,k*2+1,(r-l)/2+l+1,r,t); return min(lm,rm); } ll getMax(int a,int b,int k,int l,int r,int t){ if(b<l||r<a)return 0; if(a<=l&&r<=b)return BSEG[k][t]; ll lm = getMax(a,b,k*2,l,(r-l)/2+l,t); ll rm = getMax(a,b,k*2+1,(r-l)/2+l+1,r,t); return max(lm,rm); } int main(){ int i,j; ll n,d,x,y,c; cin>>n>>d; FOR(i,n){ cin>>x>>y>>c; P data = P(x,y); datas.pb(data); sorted[i] = P(c,datas.size()-1); sortedV[i] = c; } sort(sorted,sorted+n); sort(sortedV,sortedV+n); int index = 1; while(index<n)index*=2; fill_n(*BSEG,(1<<19)*2,0); fill_n(*MSEG,(1<<19)*2,INF); FOR(i,n){ P data = datas[sorted[i].second]; x = data.first; y = data.second; BSEG[index+i][0] = x; MSEG[index+i][0] = x; BSEG[index+i][1] = y; MSEG[index+i][1] = y; updataB((index+i)/2,0); updataB((index+i)/2,1); updataM((index+i)/2,0); updataM((index+i)/2,1); } ll ans = 0; FOR(i,n){ ll source = sorted[i].first; ll r = source+d; int li = i; int ri = upper_bound(sortedV,sortedV+n,r)-sortedV-1; if(li==ri)continue; ll sum = (getMax(li,ri,1,0,index-1,0)-getMin(li,ri,1,0,index-1,0)) *(getMax(li,ri,1,0,index-1,1)-getMin(li,ri,1,0,index-1,1)); ans = max(ans,sum); } cout<<ans<<endl; return 0; }
セグメントツリーメモ
更新は再帰的に処理します。各操作O(logN)
///RMQ #define SIZE (1<<18) #define ll long long #define INF (1<<30)///必要に応じて増やす ll int MSEG[SIZE]; void update(int index){ if(index==0)return; int l = index*2,r = index*2+1,tmp = MSEG[index]; if(MSEG[l]<MSEG[r]){ MSEG[index] = MSEG[l]; }else{ MSEG[index] = MSEG[r]; } if(tmp==MSEG[index])return;///更新が無ければ終了 update(index/2); } ll getMin(int a,int b,int k,int l,int r){ if(b<l||a>r)return INF;///含まない if(a<=l&&r<=b)return MSEG[k];///[a,b]が[l,r]を完全に含む ll ml = getMin(a,b,k*2,l,(r-l)/2+l);///左側 ll mr = getMin(a,b,k*2+1,(r-l)/2+l+1,r);///右側 return min(ml,mr); }
