AOJ0129
問題:Hide-and-Seek Supporting System
円と2点の間の線分の当たり判定。ただし2点が両方共円の中にある場合は無視する。
#include<iostream> #include<vector> #include<complex> using namespace std; int main() { int n,m; while(cin >> n,n) { vector<complex<double> > wallp; vector<double> wallr; for(int i=0;i<n; ++i) { int x,y,r; cin >> x >> y >> r; wallp.push_back(complex<double>(x,y)); wallr.push_back(double(r)); } cin >> m; for(int k=0;k<m; ++k) { int x,y; cin >> x >> y; complex<double> t(x,y); cin >> x >> y; complex<double> o(x,y); bool safe = false; for(int i=0;i<n; ++i) { if( abs(wallp[i]-t) < wallr[i] && abs(wallp[i]-o) < wallr[i] ) continue; complex<double> a = wallp[i]-t; complex<double> b = wallp[i]-o; complex<double> t = b-a; double mlen = min(abs(a),abs(b)); double ub = 1; double lb = 0; while(ub-lb>=1e-10) { double ubl = abs(a + t*ub); double lbl = abs(a + t*lb); double k = (ub+lb)/2; double mbl = abs(a + t*k); mlen = min(mlen, mbl); if(ubl > lbl) ub = k; else lb = k; } if(mlen <= wallr[i]) { safe = true; } } cout << (safe ? "Safe" : "Danger") << endl; } } return 0; }
AOJ0120
問題:Patisserie
DP難しい。
DPわけわからん。
#include<iostream> #include<string> #include<sstream> #include<vector> #include<cmath> using namespace std; int main() { string s; while(getline(cin,s), !s.empty()) { stringstream ss(s); int W; ss >> W; vector<int> R; int r; while(ss >> r) R.push_back(r); int N = R.size(); vector<vector<double> > dp(1<<N, vector<double>(N,10000000)); for(int i=0;i<N; ++i) dp[1<<i][i] = double(R[i]); for(int v=0; v<(1<<N); ++v) for(int i=0; i<N; ++i) for(int j=0; j<N; ++j) { if(v&(1<<j))continue; dp[v|(1<<j)][j] = min(dp[v|(1<<j)][j], dp[v][i] + sqrt(4*R[i]*R[j])); } double m_len = 10000000; for(int i=0; i<N; ++i) m_len = min(m_len, dp[(1<<N)-1][i] + double(R[i])); cout << ((m_len <= W) ? "OK" : "NA") << endl; } return 0; }
2013/02/03追加
メモ化再帰でも解いた。
#include<iostream> #include<cmath> #include<vector> #include<cstring> #include<sstream> using namespace std; vector<int> R; int N; double memo[1<<12][12]; double dfs(int v, int k) { if(memo[v][k] > 0)return memo[v][k]; if(v == (1<<N)-1) return R[k]; double mlen = 1<<20; for(int i=0;i<N;++i) { if(v&(1<<i))continue; if(v) mlen = min(mlen, dfs(v|(1<<i),i) + sqrt(4*R[i]*R[k])); else mlen = min(mlen, dfs(1<<i,i) + R[i]); } return memo[v][k] = mlen; } int main() { string s; while(getline(cin,s), !s.empty()) { memset(memo,-1,sizeof(memo)); stringstream ss(s); int W; ss >> W; int r; R.clear(); while(ss >> r) R.push_back(r); N = R.size(); if(dfs(0,0) <= W) cout << "OK" << endl; else cout << "NA" << endl; } }
SRM556Div2
Medium:
グラフと、各頂点の値が渡されるので、スタート地点からグラフを移動し、値をXORしていった時に得られる最大値を求める問題。
同じノードを複数回訪れる事も可能。
無向グラフなら
a->b->c->b->a という風に来た道を戻れば任意の値を使えるので、到達できる頂点の値をXORしたときの最大値だと思って解いた。
#include <cstdlib> #include <cmath> #include <map> #include <utility> #include <set> #include <iostream> #include <string> #include <vector> #include <algorithm> #include <sstream> #include <complex> #include <stack> #include <queue> #define REP(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) REP(i,0,n) using namespace std; class XorTravelingSalesman { public: int maxProfit(vector <int> cityValues, vector <string> roads) { int result=0; set<int> enableValues; queue<int> q; q.push(0); enableValues.insert(cityValues[0]); while(!q.empty()) { int n=q.front();q.pop(); rep(i,roads.size()) { if( roads[n][i]=='Y' ) { enableValues.insert(cityValues[i]); q.push( i ); roads[n][i]='N'; } } } q.push(0); set<int> visited; visited.insert(0); while( !q.empty() ) { int n = q.front();q.pop(); for( set<int>::iterator it = enableValues.begin(); it!=enableValues.end(); ++it ) { if( visited.find(n^(*it)) == visited.end() ) { visited.insert(n^(*it)); q.push( n^(*it)); result = max( result , n^(*it)); } } } return result; }
AOJ0176
問題:What Color?
16進数で入力してやるだけ。
#include<iostream> #include<cstdio> #include<string> #include<map> #include<cmath> using namespace std; double d( int a, int b ) { double dr = (a&0xff0000) - (b&0xff0000); double dg = (a&0x00ff00) - (b&0x00ff00); double db = (a&0x0000ff) - (b&0x0000ff); double dk = sqrt( dr*dr + dg*dg + db*db ); return dk; } int main() { map< int , string > color; color[ 0x000000 ] = "black"; color[ 0x0000ff ] = "blue"; color[ 0x00ff00 ] = "lime"; color[ 0x00ffff ] = "aqua"; color[ 0xff0000 ] = "red"; color[ 0xff00ff ] = "fuchsia"; color[ 0xffff00 ] = "yellow"; color[ 0xffffff ] = "white"; int in; while( scanf("#%x\n",&in ) == 1 ) { int m = 0xffffff; for( map<int,string>::iterator it = color.begin(); it!=color.end(); ++it ) { if( d( m,in ) > d( it->first ,in ) )m=it->first; } cout << color[m] << endl; } return 0; }
AOJ0122
問題:Summer of Phyonkichi
時間差で動作するスプリンクラーの下をカエルのぴょん吉が渡る問題。
生死が掛かっているにも関わらず、ジャンプすることを強いられている。
#include<vector> #include<map> #include<iostream> #include<algorithm> using namespace std; #define debug(a) cout << #a << ":" << a << endl; #define rep(i,n) for( int i=0;i<n;++i ) typedef vector< pair< int,int > > vp; bool valid( pair<int,int> a ) { return( a.first >= 0 && a.second >= 0 && a.first <= 9 && a.second <= 9 ); } int main() { int x,y,n; while( cin >> x >> y, x|y) { cin >> n; vp sp(n); rep(i,n)cin >> sp[i].first >> sp[i].second; vp a,b; a.push_back( make_pair(x,y) ); rep(i,n) { b=a; a.clear(); vp sps; x = sp[i].first; y = sp[i].second; for( int dx = -1; dx <= 1; ++ dx ) for( int dy = -1; dy <= 1; ++ dy ) { if( valid( make_pair( x+dx , y+dy ) ) ) sps.push_back( make_pair( x+dx , y+dy ) ); } vp ks; rep(j,b.size()) { x = b[j].first; y = b[j].second; vp buf; // buf.push_back( make_pair( x,y ) ); 強いられています for( int dx = -2; dx <= 2; dx+=4 ) for( int dy = -1; dy <= 1; ++ dy ) { buf.push_back( make_pair( x+dx , y+dy ) ); buf.push_back( make_pair( x+dy , y+dx ) ); } rep(k,buf.size()) { if( valid( buf[k] ) ) ks.push_back( buf[k] ); } } sort(ks.begin(),ks.end()); sort(sps.begin(),sps.end()); set_intersection( ks.begin(),ks.end(), sps.begin(),sps.end() ,inserter( a,a.begin() ) ); } cout<< ( a.empty() ? "NA" : "OK" ) << endl; } }
AOJ0121
問題:Seven Puzzle
スライドパズルの最短スワップ回数を求める。
幅優先した。
#include<iostream> #include<vector> #include<map> #include<algorithm> #include<queue> #include<cstdio> using namespace std; #define rep(i,n) for( int i=0; i<n; ++i ) #define INF 1<<21 int main() { map< vector<int> , int > memo; vector<int> in(8); rep(i,8)in[i]=i; do{ memo[ in ] = INF; }while(next_permutation(in.begin(),in.end())); sort(in.begin(),in.end()); queue<vector<int> > q; q.push(in); memo[in]=0; while( !q.empty() ) { in = q.front();q.pop(); int n = memo[in]; int i = 0; rep(o,8)if(in[o]==0)i=o; int l = i-1; int r = i+1; int u = i-4; int d = i+4; if( l >= 0 && l <= 7 && l !=3 ) { swap(in[i],in[l]); if( memo[in] == INF ) { memo[in] = n+1; q.push(in); } swap(in[i],in[l]); } if( r >= 0 && r <= 7 && r !=4 ) { swap(in[i],in[r]); if( memo[in] == INF ) { memo[in] = n+1; q.push(in); } swap(in[i],in[r]); } if( u >= 0 && u <= 7) { swap(in[i],in[u]); if( memo[in] == INF ) { memo[in] = n+1; q.push(in); } swap(in[i],in[u]); } if( d >= 0 && d <= 7 ) { swap(in[i],in[d]); if( memo[in] == INF ) { memo[in] = n+1; q.push(in); } swap(in[i],in[d]); } } while( 8 == scanf("%d %d %d %d %d %d %d %d", &in[0],&in[1],&in[2],&in[3],&in[4],&in[5],&in[6],&in[7]) ) { cout << memo[ in ] << endl; } }
AOJ0118
問題:Property Distribution
やるだけ問題。
再帰苦手なので再帰で書いた。
入力がw,hの順じゃなくてh,wの順でWAした。
#include<iostream> using namespace std; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; int dfs( char f[110][110] ,char c, int x , int y ) { if( f[y][x] == c ) { f[y][x] = 0; for( int i=0;i<4; ++i )dfs( f , c , x+dx[i] , y+dy[i] ); return 1; } else return 0; } int main() { int w,h; while( cin >> h >> w , w|h ) { char f[110][110] = {0}; int cnt = 0; for( int i=1;i<=h; ++i )for( int j=1; j<=w; ++j )cin >> f[i][j]; for( int i=1;i<=h; ++i )for( int j=1; j<=w; ++j ) if( f[i][j] )cnt+=dfs(f,f[i][j],j,i); cout << cnt << endl; } }