yukicoder No.333〜335
RMQのセグメントツリー実装でバグが合ったらしく、かなりの時間悩んだ。
まだ336解いてませんが、取り敢えずここでコード載せておきます。
No.333 門松列を数え上げ
問題概要
左端、真ん中の門松の長さが与えられるので、右の門松で門松列を満たす長さの数を答えよ。
解法
門松列は「真ん中が最大、もしくは最小」であればよい。右端は、
- 右端<真ん中の時、真ん中>左端より「真ん中-2(真ん中と右端の数値とダブってはいけない)」
- 右端>真ん中の時、真ん中<左端より「20億-真ん中-1(右端にダブる)」
とすればよい。
#include <bits/stdc++.h> using namespace std; int main(){ int a,b; cin>>a>>b; if(a>b) cout<<2000000000-1-b<<endl; else cout<<b-2<<endl; return 0; }
No.334 門松ゲーム
問題概要
数列から門松列を満たす数字3つを2人交互に取り除いていき、門松列が作れなくなったら負け。先行が勝つために取る最初の1手は？
解法
DFS。ゲームで「最善策を取る」とあった場合、考えられるパターンとして
- DFS
- Nim、Grundy数
- その他特殊な性質
があったと思います（AtCoderで有ったんだけどうろ覚え）。気になったら調べてください。
今回はN≦12ということで最大4手、よって最大ケースでも通り数は12C3×9C3×6C3×3C3≒40万通りとなり、全部試しても余裕で間に合います。今回は答えが複数ある場合辞書順最小のものを答えることになっているので、DFSが最適でしょう。
#include <bits/stdc++.h> using namespace std; bool ok(int a,int b,int c){ if(a==b||b==c||c==a) return false; int m=max(a,max(b,c)),M=min(a,min(b,c)); if(b==m||b==M) return true; return false; } bool dfs(vector<int> l){ int n=l.size(); for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ for(int k=j+1;k<n;k++){ if(ok(l[i],l[j],l[k])){ vector<int> next=l; next.erase(next.begin()+k); next.erase(next.begin()+j); next.erase(next.begin()+i); if(!dfs(next)) return true; } } } } return false; } int main(){ int n; cin>>n; vector<int> l(n); for(int i=0;i<n;i++) cin>>l[i]; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ for(int k=j+1;k<n;k++){ if(ok(l[i],l[j],l[k])){ vector<int> next=l; next.erase(next.begin()+k); next.erase(next.begin()+j); next.erase(next.begin()+i); if(!dfs(next)){ cout<<i<<" "<<j<<" "<<k<<endl; return 0; } } } } } cout<<-1<<endl; return 0; }
普通に実装が面倒…
自分が出来たのはここまででした。
No.335 門松宝くじ
問題概要
宝くじの券には1〜Nの数字が1つずつ書いてあり、2つの数字が発表されるので、その2つの数字＋1つの数字が門松列になっていれば当選。当選する期待値の最も高いものを答えよ。
解法
まず、期待値と言っているが、分母は常にNC2であるから無視。何通り宝くじが当たるか数えればよい。
自分は「O(N^3)でも通りそうだな…」とやって失敗しました。細かい解法は
http://yukicoder.me/problems/936/editorial
に載っていますが、要は最大値と最小値をそれぞれ求めるRMQです。ということでセグメントツリーを取り敢えず実装しました。
#include <bits/stdc++.h> using namespace std; bool isKadomatsu(int a,int b,int c){ if(a==b||b==c||c==a) return false; int m=max(a,max(b,c)),M=min(a,min(b,c)); if(b==m||b==M) return true; return false; } struct segtree{ vector<int> big,sml; int n; segtree(int x){ n=1; while(n<x) n<<=1; } void assign(vector<int> a){ big.clear(); big.assign(2*n-1,INT_MIN); sml.clear(); sml.assign(2*n-1,INT_MAX); for(int i=0;i<(int)a.size();i++){ int t=n-1+i; big[t]=sml[t]=a[i]; } for(int i=n-2;i>=0;i--){ big[i]=max(big[2*i+1],big[2*i+2]); sml[i]=min(sml[2*i+1],sml[2*i+2]); } } int maximum(int l,int r,int a,int b,int k){ if(r<=a||b<=l) return INT_MIN; if(a<=l&&r<=b) return big[k]; int vr=maximum(l,(l+r)/2,a,b,2*k+1); int vl=maximum((l+r)/2,r,a,b,2*k+2); return max(vr,vl); } int minimum(int l,int r,int a,int b,int k){ if(r<=a||b<=l) return INT_MAX; if(a<=l&&r<=b) return sml[k]; int vl=minimum(l,(l+r)/2,a,b,2*k+1); int vr=minimum((l+r)/2,r,a,b,2*k+2); return min(vl,vr); } }; int main(){ int n,m; cin>>n>>m; int ans=0,score=0; segtree seg(n); for(int i=0;i<m;i++){ vector<int> a(n); for(int j=0;j<n;j++) cin>>a[j]; seg.assign(a); int tmp=0; for(int j=0;j<n;j++){ for(int k=j+1;k<n;k++){ int add=0; int p; if(0<j){ p=seg.maximum(0,seg.n,0,j,0); if(isKadomatsu(p,a[j],a[k])){ add=max(max(a[j],a[k]),max(add,p)); } p=seg.minimum(0,seg.n,0,j,0); if(isKadomatsu(p,a[j],a[k])){ add=max(add,max(a[j],a[k])); } } if(j+1<k){ p=seg.maximum(0,seg.n,j+1,k,0); if(isKadomatsu(a[j],p,a[k])){ add=max(max(a[j],a[k]),max(add,p)); } p=seg.minimum(0,seg.n,j+1,k,0); if(isKadomatsu(a[j],p,a[k])){ add=max(add,max(a[j],a[k])); } }#include <bits/stdc++.h> using namespace std; bool isKadomatsu(int a,int b,int c){ if(a==b||b==c||c==a) return false; int m=max(a,max(b,c)),M=min(a,min(b,c)); if(b==m||b==M) return true; return false; } struct segtree{ vector<int> big,sml; int n; segtree(int x){ n=1; while(n<x) n<<=1; } void assign(vector<int> a){ big.clear(); big.assign(2*n-1,INT_MIN); sml.clear(); sml.assign(2*n-1,INT_MAX); for(int i=0;i<(int)a.size();i++){ int t=n-1+i; big[t]=sml[t]=a[i]; } for(int i=n-2;i>=0;i--){ big[i]=max(big[2*i+1],big[2*i+2]); sml[i]=min(sml[2*i+1],sml[2*i+2]); } } int maximum(int l,int r,int a,int b,int k){ if(r<=a||b<=l) return INT_MIN; if(a<=l&&r<=b) return big[k]; int vr=maximum(l,(l+r)/2,a,b,2*k+1); int vl=maximum((l+r)/2,r,a,b,2*k+2); return max(vr,vl); } int minimum(int l,int r,int a,int b,int k){ if(r<=a||b<=l) return INT_MAX; if(a<=l&&r<=b) return sml[k]; int vl=minimum(l,(l+r)/2,a,b,2*k+1); int vr=minimum((l+r)/2,r,a,b,2*k+2); return min(vl,vr); } }; int main(){ int n,m; cin>>n>>m; int ans=0,score=0; segtree seg(n); for(int i=0;i<m;i++){ vector<int> a(n); for(int j=0;j<n;j++) cin>>a[j]; seg.assign(a); int tmp=0; for(int j=0;j<n;j++){ for(int k=j+1;k<n;k++){ int add=0; int p; if(0<j){ p=seg.maximum(0,seg.n,0,j,0); if(isKadomatsu(p,a[j],a[k])){ add=max(max(a[j],a[k]),max(add,p)); } p=seg.minimum(0,seg.n,0,j,0); if(isKadomatsu(p,a[j],a[k])){ add=max(add,max(a[j],a[k])); } } if(j+1<k){ p=seg.maximum(0,seg.n,j+1,k,0); if(isKadomatsu(a[j],p,a[k])){ add=max(max(a[j],a[k]),max(add,p)); } p=seg.minimum(0,seg.n,j+1,k,0); if(isKadomatsu(a[j],p,a[k])){ add=max(add,max(a[j],a[k])); } } if(k+1<n){ p=seg.maximum(0,seg.n,k+1,n,0); if(isKadomatsu(a[j],a[k],p)){ add=max(max(a[j],a[k]),max(add,p)); } p=seg.minimum(0,seg.n,k+1,n,0); if(isKadomatsu(a[j],a[k],p)){ add=max(add,max(a[j],a[k])); } } tmp+=add; } } if(score<tmp){ ans=i; score=tmp; } } cout<<ans<<endl; return 0; } if(k+1<n){ p=seg.maximum(0,seg.n,k+1,n,0); if(isKadomatsu(a[j],a[k],p)){ add=max(max(a[j],a[k]),max(add,p)); } p=seg.minimum(0,seg.n,k+1,n,0); if(isKadomatsu(a[j],a[k],p)){ add=max(add,max(a[j],a[k])); } } tmp+=add; } } if(score<tmp){ ans=i; score=tmp; } } cout<<ans<<endl; return 0; }
RMQは色々あるので、一段落着いたら取り敢えず平方分割からこの問題で解いてみたい。
そういえばSRMは1完ですが1085->1149。1完なので解説はまだ出来ません（問題が貯まる一方）。
あと1回で青に上げておきたいです。
