AOJ 2232 Ennichi
#include<bits/stdc++.h> #define fi first #define se second #define show(x) cerr<<#x<<"="<<x<<"\n" typedef long long ll; using namespace std; int n,m,h,w; char a[50][50]; bool check(){ bool b[50][50]; char c[50][50]; for(int i=0;i<h;i++)for(int j=0;j<w;j++)c[i][j]=a[i][j]; while(1){ bool up=0; for(int i=0;i<h-1;i++){ for(int j=0;j<w;j++){ if(c[i][j]!='.' && c[i+1][j]=='.'){ swap(c[i][j],c[i+1][j]); up=1; } } } if(!up)break; } while(1){ bool update=0; for(int i=0;i<h;i++)for(int j=0;j<w;j++)b[i][j]=0; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ if(j+n>w)continue; if(c[i][j]=='.')continue; int nowcolor; bool flag=1; for(int k=0;k<n;k++){ if(k==0){ nowcolor=c[i][j+k]-'a'; continue; } if(c[i][j+k]!=(char)('a'+nowcolor))flag=0; } if(flag){ for(int k=0;k<n;k++){ b[i][j+k]=1; } } } } for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ if(i+n>h)continue; if(c[i][j]=='.')continue; int nowcolor; bool flag=1; for(int k=0;k<n;k++){ if(k==0){ nowcolor=c[i+k][j]-'a'; continue; } if(c[i+k][j]!=(char)('a'+nowcolor))flag=0; } if(flag){ for(int k=0;k<n;k++){ b[i+k][j]=1; } } } } for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ if(b[i][j]==1){ c[i][j]='.'; update=1; } } } if(!update)break; while(1){ bool up=0; for(int i=0;i<h-1;i++){ for(int j=0;j<w;j++){ if(c[i][j]!='.' && c[i+1][j]=='.'){ swap(c[i][j],c[i+1][j]); up=1; } } } if(!up)break; } } bool ok=1; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ if(c[i][j]!='.')ok=0; } } return ok; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; #ifdef LOCAL_DEFINE FILE *stream1; //FILE *stream2; stream1=freopen("in","r",stdin); //stream2=freopen("out","w",stdout); if(stream1==NULL)return 0; //if(stream2==NULL)return 0; #endif cin>>h>>w>>n; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ cin>>a[i][j]; } } for(int i=0;i<h;i++){ for(int j=0;j<w-1;j++){ //if(a[i][j]!='.' && a[i][j+1]!='.'){ swap(a[i][j],a[i][j+1]); if(check()){ //cout<<i<<" "<<j<<endl; cout<<"YES"<<endl; exit(0); } swap(a[i][j],a[i][j+1]); //} } } cout<<"NO"<<endl; #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- 賢い方法とか簡潔に書く方法とか全く思いつかなかったから、とにかくゴリゴリ書いた。
- 誰かスマートな方法教えてくりー
AOJ 2583 JAG-channel
#include<bits/stdc++.h> #define fi first #define se second #define show(x) cerr<<#x<<"="<<x<<"\n" typedef long long ll; using namespace std; //const ll MOD=(ll)1e9+7; //const ll inf=(ll)1e14; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; int n,m,h,w; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; #ifdef LOCAL_DEFINE FILE *stream1; //FILE *stream2; stream1=freopen("in","r",stdin); //stream2=freopen("out","w",stdout); if(stream1==NULL)return 0; //if(stream2==NULL)return 0; #endif while(cin>>n,n){ vector<string> s(n); for(int i=0;i<n;i++){ cin>>s[i]; if(i==0)continue; int j; for(j=0;s[i][j+1]=='.';j++); s[i][j]='+'; for(int k=i-1;k>0;k--){ if(s[k][j]=='.')s[k][j]='|'; else break; } } for(int i=0;i<n;i++){ for(int j=0;j<(int)s[i].size();j++){ if(s[i][j]=='.')s[i][j]=' '; } cout<<s[i]<<endl; } } #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- 日本語や読めてなくてかなり時間がかかってしまった。。。
AOJ 2600 Koto Distance
#include<bits/stdc++.h> #define fi first #define se second #define show(x) cerr<<#x<<"="<<x<<"\n" typedef long long ll; using namespace std; //const ll MOD=(ll)1e9+7; //const ll inf=(ll)1e14; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; int n,m,h,w; string s; int a[200011],b[200011]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; #ifdef LOCAL_DEFINE FILE *stream1; //FILE *stream2; stream1=freopen("in","r",stdin); //stream2=freopen("out","w",stdout); if(stream1==NULL)return 0; //if(stream2==NULL)return 0; #endif cin>>n>>w>>h; vector<pair<int,int> > okx,oky; for(int i=0;i<n;i++){ int x,y,z;cin>>x>>y>>z; okx.push_back({x-z,x+z}); oky.push_back({y-z,y+z}); } for(int i=0;i<n;i++){ if(okx[i].fi<0)okx[i].fi=0; if(okx[i].se>w)okx[i].se=w; a[2*okx[i].fi]++; a[2*okx[i].se+1]--; } for(int i=0;i<n;i++){ if(oky[i].fi<0)oky[i].fi=0; if(oky[i].se>h)oky[i].se=h; b[2*oky[i].fi]++; b[2*oky[i].se+1]--; } for(int i=1;i<=2*w;i++){ a[i]=a[i-1]+a[i]; } for(int j=1;j<=2*h;j++){ b[j]=b[j-1]+b[j]; } bool flag1=1,flag2=1; for(int i=0;i<=2*w;i++){ if(a[i]<=0)flag1=0; } for(int i=0;i<=2*h;i++){ if(b[i]<=0)flag2=0; } if(flag1 || flag2)cout<<"Yes"<<endl; else cout<<"No"<<endl; #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- 0からwまでの範囲を全て網羅されているかもしくは、0からhまでの範囲を全て網羅していたらYes
- 反省することは、点と点の間の空間も配列として持っておくこと(点空間点空間点空間…みたいに)
AOJ 1167 ポロック予想
#include<bits/stdc++.h> #define fi first #define se second #define show(x) cerr<<#x<<"="<<x<<"\n" typedef long long ll; using namespace std; const int inf=100000000; int n,m,h,w; vector<int> a,b; int dp[1000001],dp2[1000001]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; #ifdef LOCAL_DEFINE FILE *stream1; //FILE *stream2; stream1=freopen("in","r",stdin); //stream2=freopen("out","w",stdout); if(stream1==NULL)return 0; //if(stream2==NULL)return 0; #endif for(int i=1;i<200;i++){ a.push_back(i*(i+1)*(i+2)/6); int temp=i*(i+1)*(i+2)/6; if(temp&1)b.push_back(temp); } for(int i=0;i<=1000000;i++)dp[i]=inf; dp[0]=0; for(int i=0;i<=1000000;i++){ for(int j=0;j<(int)a.size();j++){ if(i+a[j]<=1000000){ dp[i+a[j]]=min(dp[i+a[j]],dp[i]+1); } } } for(int i=0;i<=1000000;i++)dp2[i]=inf; dp2[0]=0; for(int i=0;i<=1000000;i++){ for(int j=0;j<(int)b.size();j++){ if(i+b[j]<=1000000){ dp2[i+b[j]]=min(dp2[i+b[j]],dp2[i]+1); } } } while(cin>>n,n){ cout<<dp[n]<<" "<<dp2[n]<<endl; } #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
個数制限なしナップザック問題とおんなじ感じになった。
ABC038-D プレゼント
#include<bits/stdc++.h> #define fi first #define se second #define show(x) cerr<<#x<<"="<<x<<"\n" typedef long long ll; using namespace std; class Bit{ public: //tbl[1]...tbl[n] explicit Bit(int n):size(static_cast<unsigned int>(n)){//1-indexed tbl.resize(size+10,0); } //一点のみの更新 void add(int a,ll w){//tbl[a]+=w , 1-indexed , 1-indexed!!!!!!!!!!!!!!! for(int i=a;i<=size;i+=i&-i)tbl[i]=max(tbl[i],w); } ll sum(int a){//v[1]+...+v[a] , 1-indexed ,1-indexed!!!!!!!!!!!!! ll ret=0; if(a==0)return 0; for(int i=a;i>0;i-=i&-i){ ret=max(ret,tbl[i]); } return ret; } int lower_bound(ll w){ if(w<=0)return 0; int x=0; int k=1; while(true){ if(k*2>size){ break; } k*=2; } for(k;k>0;k/=2){ if(x+k<=size && tbl[x+k]<w){ w-=tbl[x+k]; x+=k; } } return x+1;//1-indexed , 1-indexed!!!!!!!!!!!! } private: unsigned int size; vector<ll> tbl; }; int n,m,h,w; vector<pair<int,int> > v; int dp[100001]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; #ifdef LOCAL_DEFINE FILE *stream1; //FILE *stream2; stream1=freopen("in","r",stdin); //stream2=freopen("out","w",stdout); if(stream1==NULL)return 0; //if(stream2==NULL)return 0; #endif cin>>n; for(int i=0;i<n;i++){ int h,w;cin>>h>>w; v.push_back({h,-w}); } sort(v.begin(),v.end()); Bit bit(100001); for(int i=0;i<n;i++){ dp[i]=bit.sum(-v[i].se-1)+1; bit.add(-v[i].se,dp[i]); } int ans=0; for(int i=0;i<n;i++){ ans=max(ans,dp[i]); } cout<<ans<<endl; #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- ソートするは良いけど、そこから思いつかなかった。
- hが同じ時wを降順にするの、おぉ!ってなった
- bitのライブラリ作ってあったから、その場で作り変えて実装させることができた。
- ライブラリがあると本当に便利よねー
- w[i]より小さい最大のdpの大きさ、、、、そんな考え方は出来なかった。
- 未来の自分に向けて言いますが、あなたはおそらくこの問題をいつか復習する際また同じようなところで引っかかってこのブログのページに帰ってくるでしょう。
ABC041-D 徒競走
#include<bits/stdc++.h> typedef long long ll; using namespace std; int n,m,h,w; ll dp[(1<<20)]; vector<int> v[20]; int main(){ cin>>n>>m; for(int i=0;i<m;i++){ int x,y;cin>>x>>y;x--;y--; v[y].push_back(x); } dp[0]=1; for(int i=0;i<(1<<(n+1));i++){ if(dp[i]==0)continue; for(int bit=0;bit<n;bit++){ if(i&(1<<bit))continue; else{ bool flag=1; for(int j=0;j<(int)v[bit].size();j++){ if(i&(1<<v[bit][j]))continue; else flag=0; } if(flag)dp[i|(1<<bit)]+=dp[i]; } } } cout<<dp[(1<<n)-1]<<endl; return 0; }
- どうやってやるのかなーって考えてる時に bitdpするっていう選択肢を考えなかったのが辛い。
- 一瞬解説をみて bitdpだとわかったので、それからは自分で考えてやった。
- k- bit目が0なら k+1番のウサギはまだゴールしてない、1ならゴールしてると考えてやる。
- 先にゴールしていてほしいウサギが全部ゴールしているなら、着目しているウサギもゴールさせて良い。
- そんな感じで最後は全員ゴールした状態の通り数なので、全ての bitが1のdp配列を見れば良い。
- 制約に16があったら bitdpを疑おうね自分!!!!
ABC045 D すぬけ君の塗り絵
//const ll MOD=(ll)1e9+7; //const ll inf=(ll)1e14; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; ll n,m,h,w; string s; map<pair<int,int>,ll> mp; int x[100001],y[100001]; ll ans[10]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; #ifdef LOCAL_DEFINE FILE *stream1; //FILE *stream2; stream1=freopen("in","r",stdin); //stream2=freopen("out","w",stdout); if(stream1==NULL)return 0; //if(stream2==NULL)return 0; #endif cin>>h>>w>>n; for(int i=0;i<n;i++){ cin>>y[i]>>x[i]; x[i]--;y[i]--; for(int j=-2;j<=0;j++){ for(int k=-2;k<=0;k++){ if(y[i]+j<0 || y[i]+j+2>=h)continue; if(x[i]+k<0 || x[i]+k+2>=w)continue; mp[make_pair(y[i]+j,x[i]+k)]++; } } } for(auto ite=mp.begin();ite!=mp.end();ite++){ //auto temp=ite->fi; //int temp2=ite->se; //print((temp.fi),(temp.se),temp2); ans[ite->se]++; } ans[0]=(w-2)*(h-2)-(int)mp.size(); println__(ans,ans+10); #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- 塗られた付近のデータだけ保存しとけば、残りは0個なのでね。