| 
http://rose.u-aizu.ac.jp/onlinejudge/cvolume.jsp?contestID=UAPC2010
5時間11問。10問正解で4位でした。問題文日本語+問題易しめという好条件ではありますが。
こういうのはAが一番簡単と相場が決まっているのでAから。
数字を前からなめるだけ…と思いきや途中でお腹が痛くなる。
#include <iostream> #include <vector> using namespace std; int main() { for (int n; cin>>n, !(n==0); ){ vector<int> v(n); for (int i=0; i<n; i++) cin>>v[i]; bool fst=true; for (int i=0; i<n; i++){ int e=i; for (int j=i+1; j<n; j++){ if (v[j-1]+1==v[j]) e=j; else break; } if (fst) fst=false; else cout<<" "; if (i==e) cout<<v[i]; else cout<<v[i]<<"-"<<v[e]; i=e; } cout<<endl; } return 0; }
ええと、どうやるんだ？サイズが微妙に小さいが全探索が通るサイズではない。いやいや、橋の容量が小さいところからとるのが最適に決まっているじゃないか。ソートしてなめるだけ。n*2^nなDPでも通ったりするのだろうか？
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { for (int n; cin>>n, !(n==0); ){ vector<pair<int, int> > v; for (int i=0; i<n; i++){ int a, b; cin>>a>>b; v.push_back(make_pair(b, a)); } sort(v.begin(), v.end()); int acc=0; for (int i=0; i<n; i++){ acc+=v[i].second; if (acc>v[i].first){ cout<<"No"<<endl; goto _exit; } } cout<<"Yes"<<endl; _exit:; } return 0; }
レールガンってそういう仕組だったのかー。角度が外れてたら二度と当たらないということに気づかなかったので、愚直に実装。反射の式がとても怪しくて全く自信がなかったが一発アクセプト。多少間違っていたとしても通りそうですね。
#include <iostream> #include <iomanip> #include <vector> #include <complex> using namespace std; typedef complex<double> pt; pair<double,double> cross_circle_and_line(pt a, pt u ,pt c ,double r) { double b=real(u*conj(a-c)); double d=b*b-norm(u)*(norm(a-c)-r*r); d=max(d, 0.0); return make_pair((-b+sqrt(d))/norm(u), (-b-sqrt(d))/norm(u)); } pt tani(const pt &p) { return p/abs(p); } int main() { cout<<setiosflags(ios::fixed)<<setprecision(10); for (double d; cin>>d, !(d==0); ){ double px, py; cin>>px>>py; pt p(px, py); double vx, vy; cin>>vx>>vy; pt v(vx, vy); double total_dist=0; for (;;){ pt vv=-p/v; if (abs(vv.imag())<1e-9 && vv.real()>0){ total_dist+=abs(p); break; } pair<double, double> ss=cross_circle_and_line(p, v, pt(0, 0), 1); //cout<<"+++ "<<ss.first<<" "<<ss.second<<endl; double s=max(ss.first, ss.second); total_dist+=abs(v*s); pt np=p+s*v; pt tt=v/tani(np); pt nv=v-tani(np)*tt.real()*2.0; p=np; v=nv; //cout<<total_dist<<": "<<s<<", "<<p<<", "<<v<<", "<<abs(v)<<endl; if (total_dist>d) break; } //cout<<"==="<<endl; if (total_dist>d) cout<<"impossible"<<endl; else cout<<total_dist<<endl; } return 0; }
シミュレーションするだけで、仕様も割とシンプルなのですぐにできたが、配列の添字を一箇所間違えて一回REをもらう。
#include <iostream> #include <vector> #include <map> #include <string> using namespace std; struct link_dat{ link_dat(){} link_dat(int l, int u, int r, int d, const string &p) :l(l), u(u), r(r), d(d), p(p) {} bool in(int x, int y){ return (x>=l && x<=r && y>=u && y<=d); } int l, u, r, d; string p; }; int main() { for (int n; cin>>n, !(n==0); ){ int w, h; cin>>w>>h; map<string, vector<link_dat> > page; string home; for (int i=0; i<n; i++){ string name; cin>>name; int m; cin>>m; if (i==0) home=name; vector<link_dat> links; for (int j=0; j<m; j++){ int l, u, r, d; cin>>l>>u>>r>>d; string p; cin>>p; links.push_back(link_dat(l, u, r, d, p)); } page[name]=links; } vector<string> hist; hist.push_back(home); int cursor=0; int m; cin>>m; for (int i=0; i<m; i++){ string cmd; cin>>cmd; if (cmd=="show"){ cout<<hist[cursor]<<endl; } else if (cmd=="forward"){ cursor++; cursor=min(cursor, (int)(hist.size()-1)); } else if (cmd=="back"){ cursor--; cursor=max(0, cursor); } else if (cmd=="click"){ int x, y; cin>>x>>y; vector<link_dat> &links=page[hist[cursor]]; for (int i=0; i<links.size(); i++){ if (links[i].in(x, y)){ hist.resize(cursor+1); hist.push_back(links[i].p); cursor++; break; } } } } } return 0; }
最小全域木の個数？わからん…。
Eが分からないので解いてる人が多かったJに移る。素因数分解するだけのように見える。a<=bなものというのでちょっとギョッとするが、a==bなのは両方Lの時だけだから、適当に計算して、後で補正できるだろう。適当に計算して提出。
#include <iostream> #include <vector> using namespace std; int main() { int limit=1000000; vector<int> primes; vector<bool> flg(limit, true); for (int i=2; i<limit; i++){ if (flg[i]){ primes.push_back(i); for (int j=i+i; j<limit; j+=i) flg[j]=false; } } for (long long l; cin>>l, !(l==0); ){ vector<pair<long long,int> > ps; long long n=l; for (int i=0; i<primes.size(); i++){ long long p=primes[i]; if (p*p>n) break; int cnt=0; while(n%p==0){ n/=p; cnt++; } if (cnt>0){ ps.push_back(make_pair(p, cnt)); } } if (n>1) ps.push_back(make_pair(n, 1)); long long ans=1; for (int i=0; i<ps.size(); i++){ ans*=(ps[i].second+1)*2-1; } cout<<(ans+1)/2<<endl; } return 0; }
J解きながらEを考えていたところによると、辺の数が2個のみというのは制約が強すぎるので、簡単な解き方があるだろうということ。サンプルを紙に書いてみると、ループになっていた。そうか。次数2だとループにしかならない。ループの中で最小要素の個数を数えて掛け合わせるだけだ。そうと分かれば簡単に実装。サブミット。
#include <iostream> #include <vector> #include <cstdio> using namespace std; int main() { for (int n; scanf("%d", &n), !(n==0); ){ vector<pair<pair<int,int>, pair<int,int> > > g; vector<bool> f(n, false); for (int i=0; i<n; i++){ int a, b, c, d; scanf("%d%d%d%d", &a,&b,&c,&d); g.push_back(make_pair(make_pair(a, b), make_pair(c, d))); } long long ans=1; for (int i=0; i<n; i++){ if (f[i]) continue; f[i]=true; int maxp=g[i].first.second; int maxc=1; for (int b=i, c=g[i].first.first; ; ){ if (f[c]) break; f[c]=true; int n=0; int p=0; if (g[c].first.first!=b){ n=g[c].first.first; p=g[c].first.second; } else{ n=g[c].second.first; p=g[c].second.second; } if (p>maxp) maxp=p, maxc=1; else if (p==maxp) maxc++; b=c; c=n; } ans=(ans*maxc)%10007; } cout<<ans<<endl; } return 0; }
普通にDPするとO(n^2)掛かりそう。ところでなぜ狼なんだろう、という疑問をこらえて、もっと重要な違和感の意味を考える。なぜ精度要求が10^-2までなんだ？そうか、これは一回成功するごとに指数的に確率が下がっていくから、精度がこの程度でいいなら、n*10程度のDPでも十分だ。誤差も指数的に減るので、蓄積はない。というわけで適当に書いてアクセプト。
#include <iostream> #include <iomanip> #include <vector> #include <cmath> using namespace std; int main() { int limit=100001; vector<vector<double> > tbl(10, vector<double>(limit, 0)); for (int i=1; i<limit; i++){ for (int l=0; l<10; l++){ double p=pow(0.5, l); tbl[l][i]=(1-p)*tbl[0][i-1]; if (l!=9) tbl[l][i]+=p*(1+tbl[l+1][i-1]); } } cout<<setiosflags(ios::fixed)<<setprecision(10); for (int n; cin>>n, !(n==0); ){ cout<<tbl[0][n]<<endl; } return 0; }
問題文がきな臭い…。これは問題サイズが小さいから単なるめんどいダイクストラのようだ。ノードは位置とサイコロの状態の組みで、サイコロの状態は三面の目のタプルで表した。意外とすんなりアクセプト。
#include <iostream> #include <vector> #include <map> #include <set> using namespace std; struct dice{ dice(int u, int s, int e): up(u), south(s), east(e) {} dice rotate(int dir){ if (dir==0) return dice(south, 7-up, east); if (dir==1) return dice(7-east, south, up); if (dir==2) return dice(7-south, up, east); if (dir==3) return dice(east, south, 7-up); } bool operator==(const dice &r) const{ return up==r.up && south==r.south && east==r.east; } bool operator<(const dice &r) const{ if (up!=r.up) return up<r.up; if (south!=r.south) return south<r.south; return east<r.east; } int up; int south; int east; }; int main() { for (int h, w; cin>>h>>w, !(h==0&&w==0); ){ vector<vector<int> > bd(h, vector<int>(w, 0)); for (int y=0; y<h; y++){ for (int x=0; x<w; x++){ cin>>bd[y][x]; } } int sy, sx; cin>>sy>>sx; int gy, gx; cin>>gy>>gx; multimap<int, pair<dice, pair<int, int> > > mm; set<pair<dice, pair<int, int> > > close; mm.insert(make_pair(0, make_pair(dice(1, 2, 3), make_pair(sx, sy)))); while (!mm.empty()){ int dist=mm.begin()->first; dice d=mm.begin()->second.first; int cx=mm.begin()->second.second.first; int cy=mm.begin()->second.second.second; mm.erase(mm.begin()); if (cx==gx && cy==gy){ cout<<dist<<endl; break; } //cout<<cx<<", "<<cy<<endl; if (close.count(make_pair(d, make_pair(cx, cy)))) continue; close.insert(make_pair(d, make_pair(cx, cy))); static const int vect[8]={ 0,-1,1,0,0,1,-1,0 }; for (int v=0; v<4; v++){ int nx=cx+vect[v*2+0]; int ny=cy+vect[v*2+1]; if (nx>=0 && ny>=0 && nx<w && ny<h){ dice nd=d.rotate(v); int ndist=dist+bd[ny][nx]*(7-nd.up); if (!close.count(make_pair(nd, make_pair(nx, ny)))) mm.insert(make_pair(ndist, make_pair(nd, make_pair(nx, ny)))); } } } } return 0; }
特定の頂点を通る最短路の個数…？うーむ、どうやるんだろう。ウォーシャルフロイド回しながら個数も計算できるのだろうか。適当に実装してみる。全然だめだ。最短路の長さ計算してから個数を計算できないか？よく考えると、任意の最短路からなるグラフはDAGだ。ループはない。よし、適当にDPで求まる。特定の頂点を通る最短路の個数は、始点→その点の最短路の個数*その点→終点の最短路の個数ぽい。これを全体の個数で割れば良さそう。実装する。WA。だめぽ。
Hが全然通らないので、Iに移動。問題サイズが不自然に小さい。これは探索か。盤面の情報が最大で25ビットしかないので、これをIntで持ちつつ2^25ノード25^4*2^25辺のグラフでダイクストラか？まあ書いてみるか。書き書き。幅優先で十分じゃないか。書き直し。サブミット。TLE。まあそんなもんか。TLEが8秒なのに対して10秒で切られているので、小手先の高速化でどうにかなるのか分からない。ピコーン。そうだ。同じ場所は2回以上反転する領域の左上とはならない。という事は、左上から見ていって、最初に現れた1を左上とする領域で反転すれば大幅に枝刈りされる+大幅に探索が高速化される。サブミット。0.4秒ぐらいで通った。
#include <iostream> #include <vector> #include <map> #include <queue> using namespace std; int upb(int n) { int ret=0; while(n>0) ret++, n/=2; return ret; } int main() { for (int n; cin>>n, !(n==0); ){ vector<int> pat; for (int i=0; i<n; i++){ for (int j=0; j<n; j++){ for (int k=i; k<n; k++){ for (int l=j; l<n; l++){ vector<vector<int> > tmp(n, vector<int>(n, 0)); for (int a=i; a<=k; a++){ for (int b=j; b<=l; b++){ tmp[a][b]=1; } } int bd=0; for (int a=0; a<n; a++){ for (int b=0; b<n; b++){ bd=(bd<<1)|tmp[a][b]; } } pat.push_back(bd); } } } } vector<vector<int> > pats(n*n+1); for (int i=0; i<pat.size(); i++){ pats[upb(pat[i])].push_back(pat[i]); } int bd=0; for (int i=0; i<n; i++){ for (int j=0; j<n; j++){ int t; cin>>t; bd=(bd<<1)|t; } } queue<pair<int, int> > mm; vector<bool> close(1<<(n*n), false); mm.push(make_pair(0, bd)); close[bd]=true; while(!mm.empty()){ int dep=mm.front().first; int cbd=mm.front().second; mm.pop(); //cout<<cbd<<endl; int ub=upb(cbd); for (int i=0; i<pats[ub].size(); i++){ int nbd=cbd^pats[ub][i]; if (nbd==0){ for (int i=0; i<=dep; i++) cout<<"myon"; cout<<endl; goto _exit; } //cout<<"*** "<<nbd<<endl; if (close[nbd]) continue; close[nbd]=true; mm.push(make_pair(dep+1, nbd)); } } _exit:; } return 0; }
残り一時間ほど。これを通してすっきり終わるか。しかし、なぜ通らないのか全く分からない。枝の重みが距離であるという記述がないので、最短経路の定義からして怪しくなってくる。なんだか枝の重みが大きいほど通りやすいから短いと言えるのか？ならば、重みの和を最大にするのか。しかし、どうやる？うーむ。わからない。そんな埼玉コンテスト的問題の解釈違いを疑いつつ、入力の仕様読み違いがないことを確認するためにassert入れてサブミットしまくる。どうやら思い違いはなかったようだ。そうこうしているうちに、同じ頂点への最短路の扱いがおかしいことに気づく。なんのことはない。単なるバグであった。
#include <iostream> #include <iomanip> #include <vector> #include <map> #include <cassert> using namespace std; double ways(int c, int e, int r, vector<vector<int> > &g, vector<vector<int> > &h, vector<double> &tbl ) { if (c==e && r==0) return 1; if (c==e) return 0; if (g[c][e]>r) return 0; assert(g[c][e]==r); int n=g.size(); double &ret=tbl[c]; if (ret>=0) return ret; ret=0; for (int i=0; i<n; i++){ if (h[c][i]==0) continue; ret+=ways(i, e, r-h[c][i], g, h, tbl); } return ret; } int main() { cout<<setiosflags(ios::fixed)<<setprecision(10); for (int n, m, q; cin>>n>>m>>q, !(n==0); ){ vector<vector<int> > g(n, vector<int>(n, 0)); for (int i=0; i<m; i++){ int f, t, c; cin>>f>>t>>c; assert(g[f][t]==0); assert(g[t][f]==0); assert(f!=t); g[f][t]=c; g[t][f]=c; } vector<vector<int> > p=g; for (int k=0; k<n; k++){ for (int i=0; i<n; i++){ for (int j=0; j<n; j++){ if (p[i][k]==0 || p[k][j]==0) continue; int d=p[i][k]+p[k][j]; if (p[i][j]==0 || d<p[i][j]) p[i][j]=d; } } } vector<double> tbl(n, -1); double tot_way=ways(0, n-1, p[0][n-1], p, g, tbl); assert(tot_way>0); /* for (int i=0; i<n; i++){ for (int j=0; j<n; j++) { vector<double> tbl(n, -1); double w=ways(i, j, p[i][j], p, g, tbl); cout<<p[i][j]<<","<<w<<" "; } cout<<endl; } */ for (int i=0; i<q; i++){ int c; cin>>c; if (c==0 || c==n-1){ cout<<1.0<<endl; continue; } assert(p[0][c]+p[c][n-1]>=p[0][n-1]); if (p[0][c]==0 || p[c][n-1]==0 || p[0][c]+p[c][n-1]>p[0][n-1]){ cout<<0.0<<endl; continue; } double bef_way, aft_way; { vector<double> tbl(n, -1); bef_way=ways(0, c, p[0][c], p, g, tbl); } { vector<double> tbl(n, -1); aft_way=ways(c, n-1, p[c][n-1], p, g, tbl); } assert(bef_way>0); assert(aft_way>0); cout<<(bef_way*aft_way/tot_way)<<endl; } cout<<endl; } return 0; }
思い出サブミット！
積み残しがなかったのですっきり満足。いつもこれぐらいできればいいんだがなあ。