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;
	}
}