AOJ1625 折り紙(Origami, or the art of folding paper)
#include<bits/stdc++.h> using namespace std; int main() { int hh, w, t, p; while (cin >> w >> hh >> t >> p, w) { int res[40][40]; for (int i = 0; i < 40; i++) for (int j = 0; j < 40; j++) res[i][j] = 0; for (int i = 0; i < hh; i++) for (int j = 0; j < w; j++) res[i][j] = 1; for (int ii = 0; ii < t; ii++) { int d, c; cin >> d >> c; int tmp[40][40]; for (int i = 0; i < 40; i++) for (int j = 0; j < 40; j++) tmp[i][j] = 0; if (d == 1) { // d == 1 for (int i = 0; i < 40; i++) { for (int j = c; j < 40; j++) { tmp[i][j - c] += res[i][j]; } } for (int i = 0; i < 40; i++) { for (int j = c - 1; j >= 0; j--) { tmp[i][c - 1 - j] += res[i][j]; } } } else { // d == 2 int h = 0; for (int i = 0; i < 40; i++) { if (res[i][0] != 0) h++; } if (c >= h - c) { for (int i = h - 1; i >= h - c; i--) { for (int j = 0; j < 40; j++) { tmp[h - 1 - i][j] += res[i][j]; } } for (int i = 0; i < h - c; i++) { for (int j = 0; j < 40; j++) { tmp[i + 2 * c - h][j] += res[i][j]; } } } else { for (int i = 0; i < h - c; i++) { for (int j = 0; j < 40; j++) { tmp[i][j] += res[i][j]; } } int now = c; for (int i = h - 1; i >= h - c; i--) { for (int j = 0; j < 40; j++) { tmp[i - 2 * now + 1][j] += res[i][j]; } now--; } } } //tmp -> res for (int i = 0; i < 40; i++) { for (int j = 0; j < 40; j++) { res[i][j] = tmp[i][j]; } } int hlen = 0; for (int i = 0; i < 40; i++) { if (res[i][0] != 0) hlen++; } for (int i = 0; i < p; i++) { int x, y; cin >> x >> y; cout << res[hlen - 1 - y][x] << endl; } } }
- 何かいうとしたら、「ただただ面倒くさいことをする」に尽きるかと思います。
- 難しいことはやっていないんですけど、バグると時間を食う系の問題というか、どれだけ集中して実装できるかみたいなのが重要なのかなーと。
- 考察の段階で要所の紙コーディングまでして完全に詰めきってから実装しました。
AOJ 2237 The Castle
#include<bits/stdc++.h> using namespace std; int n,m; double dp[(1<<16)][17]; double a[20][20]; double memo(int state,int enemy){ if(enemy==m)return 1; if(state==(1<<n)-1)return 0; if(dp[state][enemy]>=0)return dp[state][enemy]; double &res=dp[state][enemy]; res=0; for(int i=0;i<n;i++){ if(state&(1<<i))continue; double now=1,sum=0; for(int j=enemy;j<m;j++){ sum+=now*(1-a[i][j])*memo((state|(1<<i)),j); now*=a[i][j]; } sum+=now; res=max(res,sum); } return dp[state][enemy]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>a[i][j]; } } for(int i=0;i<(1<<16);i++) for(int j=0;j<17;j++) dp[i][j]=-1; cout<<memo(0,0)<<endl; return 0; }
- ループでdpやって答えが合わなかったから、メモ化再帰でやりました。
- stateは死んだら1、生きてたら0です。
- 最適に行動したいので、どの猫がいつ死んで次にどの猫を戦わせれば良いかを知っておく必要がある。
- んー、難しいですね。
- 下のリンクは公式解説スライドです。
AOJ 2585 1 Day Passport
#include<bits/stdc++.h> using namespace std; /* http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2014/Practice/模擬国内予選/講評&openfile=D.pdf */ const int inf=1e9; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m,h,k; while(cin>>n>>m>>h>>k,n){ vector<tuple<int,int,int,int> > v[101]; for(int i=0;i<m;i++){ int a,b,c,d,e;cin>>a>>b>>c>>d>>e; a--;b--;e--; v[a].push_back(make_tuple(b,c,d,e)); v[b].push_back(make_tuple(a,c,d,e)); } int s,t;cin>>s>>t; s--;t--; int p;cin>>p; int a[500],b[500]; for(int i=0;i<p;i++){ int l,d;cin>>l>>d; int now=0; for(int j=0;j<l;j++){ int tmp;cin>>tmp; tmp--; now|=(1<<tmp); } a[i]=d; b[i]=now; } int dp[300][300]; for(int i=0;i<300;i++)for(int j=0;j<300;j++)dp[i][j]=inf; dp[0][0]=0; for(int i=0;i<p;i++){ for(int j=0;j<(1<<k);j++){ dp[i+1][j|b[i]]=min(dp[i+1][j|b[i]],dp[i][j]+a[i]); dp[i+1][j]=min(dp[i+1][j],dp[i][j]); } } int ans=inf; for(int i=0;i<(1<<k);i++){ if(dp[p][i]==inf)continue; int d[101][25]; for(int j=0;j<n;j++)for(int k=0;k<=h;k++)d[j][k]=inf; d[s][0]=0; priority_queue<tuple<int,int,int> > q; q.push(make_tuple(0,s,0)); while(!q.empty()){ int now=get<1>(q.top()); int nowcost=-get<0>(q.top()); int nowh=get<2>(q.top()); q.pop(); if(nowcost>d[now][nowh])continue; for(int j=0;j<(int)v[now].size();j++){ int next=get<0>(v[now][j]); int next_h=get<2>(v[now][j]); int next_cost=get<1>(v[now][j]); int cop=get<3>(v[now][j]); if(i&(1<<cop))next_cost=0; if(nowh+next_h<=h && d[next][nowh+next_h]>d[now][nowh]+next_cost){ d[next][nowh+next_h]=d[now][nowh]+next_cost; q.push(make_tuple(-d[next][nowh+next_h],next,nowh+next_h)); } } } int res=inf; for(int j=0;j<=h;j++)res=min(res,d[t][j]); ans=min(res+dp[p][i],ans); } if(ans==inf)cout<<-1<<endl; else cout<<ans<<endl; } }
- これ、簡単だと思ってやったら1週間どハマりした(最悪)(でも良い経験になった)
- どこでハマったかというと、dijkstraのところで、最初は各頂点への最短距離を持っておくd[N]を使って実装していて、提出してはWAをしていた。
- これだと、時間と関係なくその頂点の最短距離を保存してしまうからダメ。
- ダメな理由は、例えば1日がH時間だとして、ある頂点Vに行く行き方が「H-1時間でコスト100」と「H-3時間でコスト200」の2通りあったとする。そしてVから目的地Tまでは「2時間でコスト100」の一本だけがあったとしよう。
- 前者の方法だとH-1時間でコスト100の内容しかd[V]に保存されず、これではTまで行くには最低H＋1時間かかり答えは-1と出力されてしまう。
- これは明らかに間違っていて、本来出力されるべき答えは300である。H-3時間でコスト200から2時間でTまで行き到着である。
- このように、必ずしもコストが最小のものでゴールできるとは限らないのでd[頂点][かかった時間]としてdijkstraをしてあげるべきである。
AOJ 2334 Roads on Towns
#include<bits/stdc++.h> #define fi first #define se second typedef long long ll; using namespace std; //幾何ライブラリ //ほぼ、https://ei1333.github.io/algorithm/geometry_new.html からパクりました using Real=double;//問題によってはlong double に変更してください const Real EPS=1e-8;//問題によって値を変更してください const Real PI=acos(-1.0);//3.141592653589793238... inline bool eq(Real a,Real b){return fabs(b-a)<EPS;}//誤差を考慮した等価判定 static const int COUNTER_CLOCKWISE=1; static const int CLOCKWISE=-1; static const int ONLINE_BACK=2; static const int ONLINE_FRONT=-2; static const int ON_SEGMENT=0; typedef complex<Real> Point;//点 //直線 struct Line{ Point p1,p2; Line()= default; Line(Point a,Point b):p1(a),p2(b){}; }; //線分 struct Segment:Line{ Segment()= default; Segment(Point a,Point b):Line(a,b){} }; //点同士の大小比較 namespace std { bool operator<(const Point &a, const Point &b) { return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag(); } } //外積 Real cross(const Point& a,const Point& b){ return a.real()*b.imag()-a.imag()*b.real(); } //内積 Real dot(const Point& a,const Point& b){ return a.real()*b.real()+a.imag()*b.imag(); } int ccw(Point a,Point b,Point c){ b=b-a;c=c-a; if(cross(b,c)>EPS)return COUNTER_CLOCKWISE;//1 if(cross(b,c)<-EPS)return CLOCKWISE;//-1 if(dot(b,c)<0)return ONLINE_BACK;//2 if(norm(b)<norm(c))return ONLINE_FRONT;//-2 return ON_SEGMENT;//0 } bool intersect(const Segment& s,const Segment& t){ return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2)<=0 && ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2)<=0; } //Shortest_Path //グラフの最短距離を求めるアルゴリズムを3種類持っているクラスです class shortest_path{ public: //dijkstra法とBellman_Ford法を使うときは、このコンストラクタを使ってください explicit shortest_path(int n):vertex(n),INF((double)1e9){ v1.resize(static_cast<unsigned long>(vertex)); } //Warshall_Floyd法を使うときは、こちらのコンストラクタを使ってください shortest_path(int n,double 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,double 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<double> dijkstra(unsigned int start){ vector<double> d(static_cast<unsigned long>(vertex),INF); priority_queue<pair<double,int> > q; d[start]=0; q.push({0,start}); while(!q.empty()){ int now=q.top().se; double 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: double INF; int vertex; vector<vector<pair<int,double> > > v1; vector<vector<ll> > v2; }; int na,nb; double xa[1001],ya[1001],xb[1001],yb[1001]; int main(){ int na,nb; cin>>na>>nb; for(int i=0;i<na;i++){ cin>>xa[i]>>ya[i]; } for(int i=0;i<nb;i++){ cin>>xb[i]>>yb[i]; } Point tmp(xb[0],yb[0]); Point tmp2(xb[1],yb[1]); Segment s1(tmp,tmp2); shortest_path sp1(na); //cout<<1<<endl; for(int i=0;i<na;i++){ for(int j=i+1;j<na;j++){ Point a(xa[i],ya[i]); Point b(xa[j],ya[j]); Segment aa(a,b); //cout<<aa.p1<<" "<<aa.p2<<endl; if(!intersect(s1,aa)){ //cout<<i<<"--"<<j<<endl; sp1.add_edge(i,j,sqrt((xa[i]-xa[j])*(xa[i]-xa[j])+(ya[i]-ya[j])*(ya[i]-ya[j]))); sp1.add_edge(j,i,sqrt((xa[i]-xa[j])*(xa[i]-xa[j])+(ya[i]-ya[j])*(ya[i]-ya[j]))); } } } vector<double> di1=sp1.dijkstra(0); double ans; if(di1[1]!=1e9){ ans=di1[1]+getDistance(tmp,tmp2); }else{ ans=inf; } Point tmp3(xa[0],ya[0]); Point tmp4(xa[1],ya[1]); Segment s2(tmp3,tmp4); shortest_path sp2(nb); //cout<<2<<endl; for(int i=0;i<nb;i++){ for(int j=i+1;j<nb;j++){ Point a(xb[i],yb[i]); Point b(xb[j],yb[j]); Segment aa(a,b); if(!intersect(s2,aa)){ //cout<<i<<"--"<<j<<endl; sp2.add_edge(i,j,sqrt((xb[i]-xb[j])*(xb[i]-xb[j])+(yb[i]-yb[j])*(yb[i]-yb[j]))); sp2.add_edge(j,i,sqrt((xb[i]-xb[j])*(xb[i]-xb[j])+(yb[i]-yb[j])*(yb[i]-yb[j]))); } } } vector<double> di2=sp2.dijkstra(0); if(di2[1]!=inf){ ans=min(ans,di2[1]+getDistance(tmp3,tmp4)); }else{ ans=min(ans,inf); } if(ans!=inf){ printf("%.12f\n",ans); }else{ cout<<-1<<endl; } return 0; }
- 街の数が1000くらいだからO(n^2)解があるだろうなんて考えたら簡単に思いついた。
- 交差判定して交差してなかったら変を追加。
- 変を追加したら0から1への最短距離求めるためにdijkstraやるだけ。
AOJ 2511 Sinking islands
#include<bits/stdc++.h> #define fi first #define se second typedef long long ll; using namespace std; //union_find //_n mast be unsigned int //BEGIN CUT HERE class union_find{ public: explicit union_find(int _n):n(_n){ par.resize(static_cast<unsigned long>(_n)); rank.resize(static_cast<unsigned long>(_n)); sizes.resize(static_cast<unsigned long>(_n)); for(int i=0;i<_n;i++){ par[i]=i; rank[i]=0; sizes[i]=1; } } //親ノードを見つけます int find(int a){ if(par[a]==a)return a; return par[a]=find(par[a]); } //aとbが同じグループかの判定 bool same(int a,int b){ return find(a)==find(b); } //aとbを同じグループにします void unite(int a,int b){ link(find(a),find(b)); } //aが属するグループの要素数を求めます int size(int a){ return sizes[find(a)]; } //全体がどのグループに属しているかがわかります void view(){ for(int i=0;i<n;i++){ cout<<" par"<<"["<<i<<"]="<<par[i]<<((i==n-1)?"\n":","); } for(int i=0;i<n;i++){ cout<<"size"<<"["<<i<<"]="<<sizes[i]<<((i==n-1)?"\n":","); } cout<<endl; } void init(){ for(int i=0;i<n;i++){ par[i]=i; rank[i]=0; sizes[i]=1; } } private: void link(int a,int b){ if(same(a,b))return; if(rank[a]>rank[b]){ par[b]=a; sizes[a]+=sizes[b]; sizes[b]=0; }else{ par[a]=b; if(rank[a]==rank[b])rank[b]++; sizes[b]+=sizes[a]; sizes[a]=0; } } int n; vector<int> par; vector<int> rank; vector<int> sizes; }; int main(){ int n,m; while(cin>>n>>m,n){ vector<pair<int,int> > h; for(int i=0;i<n;i++){ int a;cin>>a; h.push_back({a,i}); } union_find tmp(n); vector<pair<pair<int,int>,int> > v; for(int i=0;i<m;i++){ int a,b,c;cin>>a>>b>>c; a--;b--; tmp.unite(a,b); v.push_back(make_pair(make_pair(c,a),b)); } if(tmp.size(0)!=n){ cout<<0<<endl; continue; } sort(h.begin(),h.end()); reverse(h.begin(),h.end()); sort(v.begin(),v.end()); union_find uf(n); ll ans=0; bool ok[201]; int cont=0; for(int i=0;i<n;i++)ok[i]=0; for(int i=0;i<n;i++){ ok[h[i].se]=1; if(i==n-1 || h[i].fi!=h[i+1].fi){ for(int j=0;j<m;j++){ int nowa=v[j].fi.se; int nowb=v[j].se; if(ok[nowa] && ok[nowb] && !uf.same(nowa,nowb)){ ans+=v[j].fi.fi; cont++; uf.unite(nowa,nowb); } } if(cont!=i){ uf.init(); cont=0; ans=0; } } } cout<<ans<<endl; } return 0; }
- 日本語が難しかった。。
- こういう問題に当たりたくないなぁ。。
AOJ 2510 Twin book report
#include<bits/stdc++.h> #define fi first #define se second typedef long long ll; using namespace std; bool dp[1001][1001]; int main(){ int n; while(cin>>n,n){ vector<pair<int,int> > v; int sum=0,maxe=0; int sumw=0; int maxw=0; vector<int> vv; for(int i=0;i<n;i++){ int a,b;cin>>a>>b; v.push_back({a,b}); vv.push_back(b); sum+=a; if(maxe<a){ maxe=a; maxw=i; } sumw+=b; } if(maxe<=sum-maxe){ cout<<sum+sumw<<endl; }else{ int ans=maxe*2+v[maxw].se; int nokori=maxe-(sum-maxe); vv.erase(vv.begin()+maxw); sort(vv.begin(),vv.end()); int vvsum=0; for(int i=0;i<(int)vv.size();i++)vvsum+=vv[i]; for(int i=0;i<=(int)vv.size();i++)for(int j=0;j<=nokori;j++)dp[i][j]=0; dp[0][0]=1; for(int i=0;i<(int)vv.size();i++){ for(int j=0;j<=nokori;j++){ if(dp[i][j]==0)continue; if(j+vv[i]<=nokori){ dp[i+1][j+vv[i]]=1; } dp[i+1][j]=1; } } for(int i=nokori;i>=0;i--){ if(dp[vv.size()][i]){ cout<<ans+vvsum-i<<endl; break; } } } } return 0; }
- とりあえず本を早く全部読み終わりたい。
- 本当は待たずに全部の本読みたいけど、一つだけめちゃめちゃ読むのに時間がかかる本があるとそうはいかない。
- そんな場合は待ち時間に感想文書けば良い。
- 待ち時間をどんなふうに使うのが一番かはdpしてあげるのが一番簡単。
AOJ 2333 My friends are small
#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=(ll)1e9; //const ll inf=(ll)1e14; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; int n,w; int a[211]; int sum[202]; 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; for(int i=0;i<n;i++){ cin>>a[i]; } a[n]=inf; n++; sort(a,a+n); ll ans=0; for(int i=0;i<n+1;i++){ int sum=0; for(int j=0;j<i;j++){ sum+=a[j]; } int nokori=w-sum; if(nokori<0)continue; //show(nokori); int minw=a[i]; //show(minw); ll dp[2][10001]; for(int j=0;j<2;j++)for(int k=0;k<=w;k++)dp[j][k]=0; dp[(i+1)&1][0]=1; for(int j=i+1;j<n;j++){ for(int k=0;k<=w;k++){ dp[(j+1)&1][k]=0; } for(int k=0;k<=w;k++){ if(dp[j&1][k]==0)continue; if(k+a[j]<=nokori){ dp[(j+1)&1][k+a[j]]=(dp[(j+1)&1][k+a[j]]+dp[j&1][k])%MOD; } dp[(j+1)&1][k]=(dp[(j+1)&1][k]+dp[j&1][k])%MOD; } /*for(int k=0;k<=w;k++){ cout<<dp[j&1][k]<<" "; } cout<<endl;*/ } for(int j=0;j<=nokori;j++){ if(nokori-j<minw)ans=(ans+dp[n&1][j])%MOD; } } cout<<ans<<endl; #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- 数え上げはもれなくダブりなくを意識したい。
- 今回はソートして初めて鞄に入れられなかった小人で場合分けをする。これはもれなくダブりのない場合わけである。
- ソートをする理由は、ソートをせずにナップザックのようなことをすると、もう鞄の中にどんな小人も入る事ができないかどうかの判定ができないからである。
