AOJ 2200 Mr.Rito Post Office
#include<bits/stdc++.h> typedef long long ll; using namespace std; const ll inf=(ll)1e14; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; int n,m; while(cin>>n>>m,n){ ll land[201][201],sea[201][201]; int a[1001]; for(int i=0;i<201;i++){ for(int j=0;j<201;j++){ land[i][j]=inf; sea[i][j]=inf; } } for(int i=0;i<201;i++){ land[i][i]=0; sea[i][i]=0; } for(int i=0;i<m;i++){ int x,y;ll t; char sl; cin>>x>>y>>t>>sl; x--;y--; if(sl=='S'){ sea[x][y]=t; sea[y][x]=t; }else{ land[x][y]=t; land[y][x]=t; } } int r;cin>>r; for(int i=0;i<r;i++){ cin>>a[i];a[i]--; } for(int k=0;k<n;k++){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ sea[i][j]=min(sea[i][j],sea[i][k]+sea[k][j]); land[i][j]=min(land[i][j],land[i][k]+land[k][j]); } } } ll dp[1001][201]; for(int i=0;i<r;i++)for(int j=0;j<n;j++)dp[i][j]=inf; dp[0][a[0]]=0; for(int i=0;i<r-1;i++){ for(int j=0;j<n;j++){ if(dp[i][j]==inf)continue; for(int k=0;k<n;k++){ dp[i+1][k]=min(dp[i+1][k],dp[i][j]+land[a[i]][j]+sea[j][k]+land[k][a[i+1]]); if(j==k){ dp[i+1][k]=min(dp[i+1][k],dp[i][j]+land[a[i]][a[i+1]]); } } } } /*for(int i=0;i<r;i++){ for(int j=0;j<n;j++){ cout<<dp[i][j]<<" "; } cout<<endl; } cout<<endl;*/ ll ans=inf; for(int i=0;i<n;i++){ ans=min(ans,dp[r-1][i]); } cout<<ans<<endl; } return 0; }
- 解いたの2回目なのにある所でずっと躓いていた。
- 反省点 必ずしもdp[i][k]+dp[k][j]= dp[i][j]ではないということ。
- これを意識すればチョロかった。
AOJ 1619 Making Lunch Boxes
#include<bits/stdc++.h> using namespace std; int dp[2][(1<<24)]; string s[501]; int n,m; bool a[501][501]; int main(){ while(cin>>n>>m,n){ for(int i=0;i<n;i++){ cin>>s[i]; for(int j=0;j<m;j++){ a[i][j]=(s[i][j]=='1'); } } if(n<=m){ int ans=0; for(int i=0;i<(1<<n);i++){ if(ans>=__builtin_popcount(i))continue; bool ok=1; for(int j=0;j<m;j++){ int cont=0; for(int k=0;k<n;k++){ if(a[k][j] && i&(1<<k))cont++; } if(cont&1){ok=0;break;} } if(ok)ans=max(ans,__builtin_popcount(i)); } cout<<ans<<endl; }else{ int list[501]; fill(list,list+n,0); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]){ list[i]=list[i]|(1<<j); } } } for(int i=0;i<2;i++)for(int j=0;j<(1<<m);j++)dp[i][j]=-1; dp[0][0]=0; for(int i=0;i<n;i++){ for(int j=0;j<(1<<m);j++)dp[(i+1)&1][j]=-1; for(int j=0;j<(1<<m);j++){ if(dp[i&1][j]==-1)continue; dp[(i+1)&1][j^list[i]]=max(dp[(i+1)&1][j^list[i]],dp[i&1][j]+1); dp[(i+1)&1][j]=max(dp[(i+1)&1][j],dp[i&1][j]); } } cout<<dp[n&1][0]<<endl; } } }
- 基本的には審判長講評に書いてあることをそのまま実装.
- n<=mなら「どのメニューを作るか」の組合せで全探索.
- n>mならbitDP.
- 漸化式はdp[(今、選ぶかどうか考えているメニューの番号:i)%2][1つ余っている素材の集合を表すbit列:j]:=この状況になるようなメニューの組合せのうち最大のメニュー数
- よって、dp[(i+1)%2][j^list[i]]=max(dp[(i+1)%2][j^list[i]],dp[i%2][j])
- もうひとつは、dp[(i+1)%2][j]=max(dp[(i+1)%2][j],dp[i%2][j])
- ここで、list[i]はi番目のメニューで使われる素材の集合を表すbit列です.
- 最後はひとつも素材を余らせてはいけないのでdp[n%2][0]を出力します.
- のりで配列の再利用をしたけど、しなくてもいけるのかな?
- あ、あと__builtin_popcount(i)はiを二進数で表した時に1になっている桁の個数です.
- 例)__builtin_popcount(7)=3,__builtin_popcount(8)=1,__builtin_popcount(9)=2
- 初期化をミスして2時間無駄にしたのはココだけの話.
AOJ 2608 Minus One
#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 int inf=(int)1e9; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; int n,m,h,w; int s,t; //Shortest_Path //グラフの最短距離を求めるアルゴリズムを3種類持っているクラスです class shortest_path{ public: //dijkstra法とBellman_Ford法を使うときは、このコンストラクタを使ってください explicit shortest_path(int n):vertex(n),INF((ll)1e14){ v1.resize(static_cast<unsigned long>(vertex)); } //Warshall_Floyd法を使うときは、こちらのコンストラクタを使ってください shortest_path(int n,ll inf):vertex(n),INF(inf){ v2.resize(static_cast<unsigned long>(vertex)); for(int i=0;i<vertex;i++)v2[i].resize(static_cast<unsigned long>(vertex)); for(int i=0;i<vertex;i++){ for(int j=0;j<vertex;j++){ v2[i][j]=INF; } } for(int i=0;i<vertex;i++)v2[i][i]=0; } //dijkstra法とBellman_Ford法専用のadd_edge(int from,int to,ll cost)です //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost) void add_edge(int from,int to,ll cost){ v1[from].push_back({to,cost}); } //Warshall_Floyd法専用のadd_edge(int from,int to,ll cost)です //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost) void add_edge_(int from,int to,ll cost){//warshall_floyd v2[from][to]=cost; } //Dijkstra法です //各頂点への距離が格納されたvector<ll>が求まります //負のコストの辺がある場合は使えません //start地点の頂点番号を引数に入れてください vector<ll> dijkstra(unsigned int start){ vector<ll> d(static_cast<unsigned long>(vertex),INF); priority_queue<pair<ll,int> > q; d[start]=0; q.push({0,start}); while(!q.empty()){ int now=q.top().se; ll now_cost=-q.top().fi; q.pop(); if(d[now]<now_cost)continue; for (auto &i : v1[now]) { if(d[i.fi]>now_cost+ i.se){ d[i.fi]=now_cost+ i.se; q.push({-d[i.fi], i.fi}); } } } return d; } //Warshall_Floyd法です //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます //閉路があるとき、返り値はtrueです tuple<vector<vector<ll> >,bool> warshall_floyd(){ for(int k=0;k<vertex;k++){ for(int i=0;i<vertex;i++){ if(v2[i][k]==INF)continue; for(int j=0;j<vertex;j++){ if(v2[k][j]==INF)continue; v2[i][j]=min(v2[i][j],v2[i][k]+v2[k][j]); } } } bool is_negative_cycle=false; for(int i=0;i<vertex;i++){ if(v2[i][i]<0)is_negative_cycle=true; } return make_tuple(v2,is_negative_cycle); } //Bellman_Ford法です //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます //閉路があるとき、返り値はtrueです //start地点の頂点番号を引数に入れてください tuple<vector<ll>,bool> bellman_ford(int start){ vector<ll> d(static_cast<unsigned long>(vertex),INF); d[start]=0; bool is_negative_cycle=false; for(int i=0;i<vertex;i++){ bool update= false; for(int j=0;j<vertex;j++){ if(d[j]==INF)continue; for(int k=0;k<(int)v1[j].size();k++){ if(d[v1[j][k].fi]>d[j]+v1[j][k].se){ d[v1[j][k].fi]=d[j]+v1[j][k].se; update= true; } } } if(i==vertex-1 && update)is_negative_cycle=true; else if(!update)break; } return make_tuple(d,is_negative_cycle); } private: ll INF; int vertex; vector<vector<pair<int,ll> > > v1; vector<vector<ll> > v2; }; //tuple tp<int,int,int> -> int a=get<0>(tp),b=get<1>(tp),c=get<2>(tp) 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>>m>>s>>t; s--;t--; shortest_path sp(n); for(int i=0;i<m;i++){ int a,b;cin>>a>>b; a--;b--; sp.add_edge(a,b,1); sp.add_edge(b,a,1); } vector<ll> d=sp.dijkstra(s); vector<ll> d2=sp.dijkstra(t); int st=d[t]; if(st==1){ cout<<0<<endl; }else{ int tmp=st-2; sort(d2.begin(),d2.end()); sort(d.begin(),d.end()); ll ans=0; for(int i=0;i<=tmp;i++){ ll a=upper_bound(d2.begin(),d2.end(),tmp-i)-lower_bound(d2.begin(),d2.end(),tmp-i); ll b=upper_bound(d.begin(),d.end(),i)-lower_bound(d.begin(),d.end(),i); ans+=a*b; //cout<<ans<<endl; } cout<<ans<<endl; } #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
sからある頂点pまでの最短距離をx、ある頂点qからtまでの最短距離をyとする。
また、sからtまでの最短距離をs_tとすると、求めるものはx+y=s_t-2のものの個数。
これはsが始点のdijkstra、tが始点のdijkstraをやっておいて、各頂点までの距離が昇順になるようソートした後、xの値で全探索する。
そうするとy=s_t-2-xとなるyの個数を二分探索で求められる。
また、sからxが最短距離となるような頂点の数も二分探索で求められるので、それぞれの個数を掛けたものの和が答えになります。
(わかりにくいですね)(説明が下手)
AOJ 2426 Treasure Hunt
#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; vector<int> x,y,xx,yy; int imos[5011][5011]; 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>>m; for(int i=0;i<n;i++){ int a,b;cin>>a>>b; xx.push_back(a); x.push_back(a); yy.push_back(b); y.push_back(b); } x.push_back(-1000000001); y.push_back(-1000000001); x.push_back(1000000001); y.push_back(1000000001); sort(x.begin(),x.end()); sort(y.begin(),y.end()); x.erase(unique(x.begin(),x.end()),x.end()); y.erase(unique(y.begin(),y.end()),y.end()); for(int i=0;i<n;i++){ xx[i]=lower_bound(x.begin(),x.end(),xx[i])-x.begin(); yy[i]=lower_bound(y.begin(),y.end(),yy[i])-y.begin(); } h=(int)y.size(); w=(int)x.size(); for(int i=0;i<n;i++){ imos[yy[i]][xx[i]]++; } for(int i=0;i<h;i++)for(int j=1;j<w;j++)imos[i][j]+=imos[i][j-1]; for(int i=1;i<h;i++)for(int j=0;j<w;j++)imos[i][j]+=imos[i-1][j]; for(int i=0;i<m;i++){ int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2; auto xa=lower_bound(x.begin(),x.end(),x1); if(*xa>=x1)xa--; auto xb=lower_bound(x.begin(),x.end(),x2); if(*xb>x2)xb--; auto ya=lower_bound(y.begin(),y.end(),y1); if(*ya>=y1)ya--; auto yb=lower_bound(y.begin(),y.end(),y2); if(*yb>y2)yb--; x1=xa-x.begin();x2=xb-x.begin();y1=ya-y.begin();y2=yb-y.begin(); cout<<imos[y2][x2]-imos[y2][x1]-imos[y1][x2]+imos[y1][x1]<<endl; } #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- 座標圧縮を初めてやった気がしたぉ。
- 面白いなこれ。
AOJ 2607 Invest Master
#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[11][11]; int dp[11][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>>w>>h>>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<100001;j++)dp[i][j]=-1; dp[0][0]=n; for(int i=0;i<h-1;i++){ for(int j=0;j<100001;j++){ if(dp[i][j]==-1)continue; for(int k=0;k<w;k++){ int cont=1; while(dp[i][j]-cont*a[i][k]>=0){ dp[i][j+cont*a[i+1][k]]=max(dp[i][j]-cont*a[i][k],dp[i][j+cont*a[i+1][k]]); dp[i+1][0]=max(dp[i+1][0],dp[i][j]-cont*a[i][k]+cont*a[i+1][k]); cont++; } } dp[i+1][0]=max(dp[i][j]+j,dp[i+1][0]); } } cout<<dp[h-1][0]<<endl; #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
dp[何日目か][その次の日得られる利益の合計]=今日中に使える残りの金額
みたいな漸化式でやったらたまたま出来ました。
嬉しい。
AOJ 2629 Manhattan
#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}; double d; double check(double mid){ double x=mid; double y=sqrt(d*d-x*x); return x+y; } 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>>d; cout<<max<double>(d*sqrt(2),(double)((int)d+1))<<endl; #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
うーん、なんか勘違いしていて解けなかった。
反省
AOJ 2610 Fast Division
#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 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; if(n==0)cout<<1<<endl; else if(n==1)cout<<2<<endl; else if(n==2)cout<<1<<endl; else cout<<0<<endl; #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
AOJ 2610 Fast Division - ヘクトのメモ
- この記事がとてもわかりやすくて助かった。