SRM374Div2
部内でやりました。楽しくなかったです。
Easy
二次元座標がn個くらい与えられて、それらの点のうち、陸上のトラックみたいなフィールドの中に含まれる点の個数を答える問題です。
まず真ん中の長方形に含まれているかチェックします。これは、X<=x<=X+widthかつY<=y<=Y+heightかどうかをチェックすればいいです。
真ん中の長方形に含まれていなかったら、次に左右の円に含まれているか確認します。これは、R=height/2として、点(X,Y+R)と点(x,y)の距離、点(X+width,Y+R)と点(x,y)の距離のどちらかがR以下であればokです。誤差がやばいので、D<=Rとはせず、EPS=1e-9としてD< R+EPSとかするといいです。
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() typedef vector<int>vint; typedef pair<int,int>pint; const double EPS=1e-9; class HockeyFault{ public: int numPlayers(int W,int H,int X,int Y,vint px,vint py){ int cnt=0; double r=1.0*H/2; rep(i,px.size()){ int x=px[i],y=py[i]; if(x>=X&&x<=W+X&&y>=Y&&y<=H+Y){ cnt++; continue; } if(hypot(x-X,y-Y-r)<r+EPS){ cnt++; continue; } if(hypot(x-X-W,y-Y-r)<r+EPS){ cnt++; continue; } } return cnt; } };
Med
実装を頑張る問題でとてもつらいですね。しかも落ちました。悲しい。(decomposeしてsortしたものが一致していたら、decomposeしてsortしていないもので比較するというのを忘れていた)
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() typedef vector<int>vint; typedef pair<int,int>pint; class SyllableSorting{ public: vector<string>word; bool isBoin(char c){ return c=='a'||c=='i'||c=='u'||c=='e'||c=='o'; } vector<string>decompose(string s){ int cur=0; int n=s.size(); vector<string>ret; while(cur<n){ int next=cur; while(next<n&&!isBoin(s[next]))next++; while(next<n&&isBoin(s[next]))next++; ret.pb(s.substr(cur,next-cur)); cur=next; } return ret; } bool C(int x,int y){ vector<string>xx=decompose(word[x]);sort(all(xx)); vector<string>yy=decompose(word[y]);sort(all(yy)); int n=min(xx.size(),yy.size()); T:; rep(i,n){ if(xx[i]!=yy[i])return xx[i]>yy[i]; } if(xx.size()!=yy.size())return xx.size()>yy.size(); if(word[x]==word[y])return false; xx=decompose(word[x]); yy=decompose(word[y]); goto T; } vector<string> sortWords(vector<string>_){ word=_; int n=word.size(); rep(i,n)for(int j=i+1;j<n;j++){ if(C(i,j)){ swap(word[i],word[j]); } } return word; } };
Hard
読解が難しい。難易度はABCのC問題くらい。幅優先探索やって、各集合についてそれを覆う最小の長方形の中点を求めればいいっぽい。
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() typedef vector<int>vint; typedef pair<int,int>pint; class PlayerExtraction{ public: int fld[50][50],H,W; int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1}; bool used[50][50]; vector<string>extractPlayers(vector<string>LATTE,int K,int T){ H=LATTE.size();W=LATTE[0].size(); rep(i,H)rep(j,W){ if(LATTE[i][j]-'0'==K)fld[i][j]=1; else fld[i][j]=0; } vector<string>ret; vector<pint>latte; rep(i,H)rep(j,W){ if(used[i][j])continue; if(!fld[i][j])continue; vector<pint>vec;vec.pb(pint(i,j)); queue<pint>que;que.push(pint(i,j)); used[i][j]=true; while(que.size()){ pint p=que.front();que.pop(); int y=p.first,x=p.second; rep(d,4){ int ny=y+dy[d],nx=x+dx[d]; if(ny<0||ny>=H||nx<0||nx>=W||!fld[ny][nx]||used[ny][nx])continue; used[ny][nx]=true; vec.pb(pint(ny,nx)); que.push(pint(ny,nx)); } } if(vec.size()*4<T)continue; int mi=114514,ma=-114514; int X,Y; rep(k,vec.size()){ mi=min(mi,vec[k].second*2); ma=max(ma,vec[k].second*2+2); } X=(ma+mi)/2; mi=114514,ma=-114514; rep(k,vec.size()){ mi=min(mi,vec[k].first*2); ma=max(ma,vec[k].first*2+2); } Y=(ma+mi)/2; latte.pb(pint(X,Y)); } sort(all(latte)); rep(i,latte.size()){ stringstream ss; ss<<latte[i].first<<" "<<latte[i].second; ret.pb(ss.str()); } rep(i,ret.size())cout<<ret[i]<<endl; return ret; } };
