ラベル AOJ の投稿を表示しています。 すべての投稿を表示
ラベル AOJ の投稿を表示しています。 すべての投稿を表示

2014年3月23日日曜日

AOJ1508 RMQ

解法


Treap木を本とかを大分参考にしながら実装してみた。
割と実装楽しい。

ソース


#include<bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
struct Treap {
  struct node{
    int value; // 値
    node *left, *right; // *左, *右:
    int priority; // 優先度
    int cnt; // 部分木のサイズ
    //  int sum; // 部分木の和
    int small; //部分木の最小値
    node( int v) : value(v), priority(rand()), cnt(1), /*sum(v),*/ small(v){
      left = right = NULL;
    }
  };
  
  node *root;
  Treap():root(NULL){}
  
  int count( node *t){ return !t ? 0 : t->cnt; }
  //int sum( node *t)  { return !t ? 0 : t->sum; }
  int mini( node *t) { return !t ? INF : t->small; }
  
  node* update( node* t) {
    t -> cnt = count( t -> left) + count( t -> right) + 1;
    // t -> sum = sum( t -> left) + sum( t -> right) + t -> value;
    t -> small = min( min( mini( t -> left), mini( t -> right)), t -> value);
    return t;
  }
  node* merge( node* l, node* r){
    if(!l || !r) return l? l : r;
    if(l -> priority > r -> priority) {
      l -> right = merge( l -> right, r);
      return update(l);
    } else {
      r -> left = merge( l, r -> left);
      return update(r);
    }
  }
  pair< node*, node* > split( node* t, int k){ // [0,k),[k,n)
    if(!t) return make_pair((node*)NULL,(node*)NULL);
    if(k <= count( t -> left)){
      pair< node*, node* > s = split( t -> left, k);
      t -> left = s.second;
      return make_pair( s.first, update(t));
    }else{
      pair< node*, node* > s = split( t -> right, k - count( t -> left) - 1);
      t -> right = s.first;
      return make_pair( update(t), s.second);
    }
  }
  
  node* insert( node* t, int k, int val){
    pair< node*, node* > s = split( t, k);
    t = merge( s.first, new node( val));
    return update(merge( t, s.second));
  }
  
  node* erase( node* t, int k){
    pair< node*, node* > s1, s2;
    s1 = split( t, k + 1);
    s2 = split( s1.first, k);
    t = merge( s2.first, s1.second);
    return update(t);
  }
  
  node* find( node* t, int k){
    int c = count(t -> left);
    if(k < c)       return find( t -> left, k);
    else if(k > c)  return find( t -> right, k - c - 1);
    else return t;
  }
  void insert( int k, int v){ root = insert( root, k, v);}
  void erase( int k) { root = erase( root, k);}
  node* find( int k) { return find( root, k); }
};
  
int main(){
  int n, q;
  Treap tree;
  
  scanf("%d %d", &n, &q);
  for(int i = 0, a ; i < n ; i++ ){
    scanf("%d", &a);
    tree.insert( i, a);
  }
  while(q--){
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    if(x == 0){
      z++;
      pair< Treap::node*, Treap::node* > a, b, c;
      c = tree.split( tree.root, z);     // [0,z] [z + 1,n)
      b = tree.split( c.first , z - 1);  // [0,z) [z]
      a = tree.split( b.first , y);     //  [0,y) [y,z)
  
      tree.root = tree.merge( a.first, b.second); // [0,y) + [z]
      tree.root = tree.merge( tree.root, a.second); // root + [y,z)
      tree.root = tree.merge( tree.root, c.second); // root + [z+1,n)
  
      //ふええふえぇふぇぇ(むずかしいね
    } else if(x == 1){
      z++;
 
      pair< Treap::node*, Treap::node* > p, q;
      p = tree.split( tree.root, y);
      q = tree.split( p.second, z - y);
      printf("%d\n", tree.mini(q.first));
      tree.root = tree.merge( p.first, tree.merge( q.first, q.second));
    } else {
      tree.erase(y);
      tree.insert( y, z);
    }
  }
}

AOJ2402 天の川

解法


星の変な入力を頑張って5辺にしてDijkstra。

ソース


typedef pair< double , int > Pi;
bool used[100];
double info[100][100];
int n, m, l;
L stars[100][5];
 
void add( int x, int y, int a, int r, const int z){
  G hosi(5);
  for(int i = 0 ; i < 5 ; i++ ){
    double theta = Degree_to_Radian(a + 72 * i);
    double nx = r * sin( theta ), ny = r * cos( theta );
    hosi[i] = P( x - nx, y + ny);
  }
  for(int i = 0 ; i < 5 ; i++ ){
    stars[z][i] = L( hosi[i * 2 % 5], hosi[(i + 1) * 2 % 5]);
  }
}
double dist( LLL a, LLL b){
  double ret = INF;
  for(int i = 0 ; i < a.size() ; i++ ){
    for(int j = 0 ; j < b.size() ; j++ ){
      ret = min( ret, distancion( a[i], b[i]));
    }
  }
  return ret;
}
double Dijkstra(){
  priority_queue< Pi , vector< Pi > , greater< Pi > > que;
  fill_n( used, 100, false);
  que.push( Pi( 0.0, m));
  while(!que.empty()){
    Pi p = que.top(); que.pop();
    if(p.sc == l) return p.fr;
    if(used[p.sc]++) continue;
    for(int i = 0 ; i < n ; i++ )
      que.push( Pi( info[p.sc][i] + p.fr, i));
  }
}
  
int main(){
  while(cin >> n >> m >> l, l){
    m--, l--;
    for(int i = 0 ; i < n ; i++ ){
      int x, y, a, r;
      cin >> x >> y >> a >> r;
      add( x, y, a, r, i);
    }
  
    for(int i = 0 ; i < n ; i++ ){
      for(int j = i + 1 ; j < n ; j++ ){
        double dist = INF;
        for(int a = 0 ; a < 5 ; a++ ){
          for(int b = 0 ; b < 5 ; b++ ){
            dist = min( dist, distancion( stars[i][a], stars[j][b]));
          }
        }
        info[i][j] = info[j][i] = dist;
      }
    }
    cout << fixed << setprecision(10) << Dijkstra() << endl;
  }
}

AOJ2545 ライオン

解法


全探する。考えられる組み合わせをすべて挙げればいい感じにできる。
できるだけライオンを檻の中に多く入れたいので、あんな感じ(以下ソース参照)に檻に入れられる最大値からループを回す。

ソース


#include<iostream>
using namespace std;
 
int n, x, m, l[10], r[10], s[10];
int ret[6];
 
bool rec( int now, int sum){
  if(now == n){
 
    int sum[6] = {};
    for(int i = 0 ; i < n ; i++){
      sum[i + 1] = sum[i] + ret[i];
    }
    for(int i = 0 ; i < m ; i++ ){
      if(sum[r[i]] - sum[l[i] - 1] != s[i]) return false;
    }
    for(int i = 0 ; i < n ; i++ ){
      cout << (i  ? " " : "") << ret[i];
    }
    cout << endl;
    return true;
 
  }
  for(int i = x ; i >= 0 ; i--){
    ret[now] = i;
    if(rec( now + 1, sum - i)) return true;
  }
  return false;
}
 
int main(){
  cin >> n >> x >> m;
  for(int i = 0; i < m; i++){
    cin >> l[i] >> r[i] >> s[i];
  }
  if(!rec(0,m)) cout << "-1\n";
}

AOJ1175 そして,いくつになった?

解法


ふぇぇって考えてるとbitDPに帰着すると思う。
前処理で円と円の交差判定が必要で,
円Oと円O'間の距離が Oの半径 + O'の半径未満だったら交差してないと判定する。
距離はsqrtとらずに整数でやると誤差らずに出来て良かった。

ソース


#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair < int , int > Pt;
bool dp[1 << 24];
Pt pts[24];
int n, r[24], c[24];
int hoge[24];
const int INF = 1 << 28;
bool intersect( Pt a, Pt b, int r1, int r2){
  return pow( a.first - b.first, 2) + pow( a.second - b.second, 2) < pow( r1 + r2, 2);
}
 
int rec( int bit){
  if(dp[bit]++) return -INF;
  int ret = 0;
 
  for(int i = 0 ; i < n ; i++ ){
    if((bit >> i) & 1){
      for(int j = i + 1 ; j < n ; j++ ){
        if( (bit >> j) & 1 && c[i] == c[j] && !(bit & hoge[i]) && !(bit & hoge[j])){
          ret = max( ret, rec( bit & ~(1 << i) & ~(1 << j)) + 2);
        }
      }
    }
  }
  return ret;
}
int main()
{
  while(cin >> n, n){
    fill_n( dp, 1 << 24 , false);
    fill_n( hoge, 24 , 0);
 
    for(int i = 0 ; i < n ; i++ ){
      cin >> pts[i].first >> pts[i].second >> r[i] >> c[i];
      for(int j = 0 ; j < i ; j++ ){
        if(intersect(pts[i],pts[j],r[i],r[j])) hoge[i] |= 1 << j;
      }
    }
    cout << rec((1 << n) - 1) << endl;
  }
}

2014年2月15日土曜日

AOJ0187 Stoning Fortune

解法


どれか二線の交点がなかったら凶。
あったら、3つの交点を求めてヘロンの公式S=√s(s-a)(s-b)(s-c)で面積を求めてはっぴー

ソース


int main(){
  L ls[3];
  int x1[3], y1[3], x2[3], y2[3];
  while( cin >> x1[0] >> y1[0] >> x2[0] >> y2[0], x1[0]|y1[0]|x2[0]|y2[0] ){
    for(int i = 1 ; i < 3 ; i++ ){
      cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
    }
    for(int i = 0 ; i < 3 ; i++ ){
      ls[i] = L( P( x1[i], y1[i]), P( x2[i], y2[i]));
    }
 
    G triangle(3);
    bool flag = true;
    for(int i = 0 ; i < 3 ; i++ ){
      const int NEXT = ( i + 1 ) % 3;
      if(!intersect( ls[i], ls[NEXT])){
        flag = false;
        break;
      }else{
        triangle[i] = crosspoint( ls[i], ls[NEXT]);
      }
    }
 
    double s = (abs(triangle[0]-triangle[1])+abs(triangle[1]-triangle[2])+abs(triangle[2]-triangle[0])) / 2;
    double area = sqrt(s * ( s - abs(triangle[0] - triangle[1])) * ( s - abs(triangle[1] - triangle[2])) * ( s - abs(triangle[2] - triangle[0])));
    if(!flag || area < EPS) cout << "kyo" << endl;
    else if(area < 100000) cout << "syo-kichi" << endl;
    else if(area < 1000000) cout << "kichi" << endl;
    else if(area < 1900000) cout << "chu-kichi" << endl;
    else cout << "dai-kichi" << endl;
  }
}

AOJ0091 Blur

解法


BFS。左上から見ていって、滴数 < 0か垂らしても残った時に枝刈りした。
これでVolume0全完。

ソース


#include<bits/stdc++.h>
using namespace std;

int q, mas[10][10];
int draw[][5][5] = {
  /*Small*/
  {{ 0, 0, 1, 0, 0},
   { 0, 1, 1, 1, 0},
   { 0, 0, 1, 0, 0}},
  //*midium*/
  {{ 0, 0, 1, 1, 1},
   { 0, 0, 1, 1, 1},
   { 0, 0, 1, 1, 1}},
  /*large*/
  {{ 0, 0, 1, 0, 0},
   { 0, 1, 1, 1, 0},
   { 1, 1, 1, 1, 1},
   { 0, 1, 1, 1, 0},
   { 0, 0, 1, 0, 0}},
};

bool check( int y, int x, int w){
  for(int i = 0 ; i < 5 ; i++ ){
    for(int j = 0 ; j < 5 ; j++ ){
      if(mas[y + i][x + j - 2] - draw[w][i][j] < 0) return false;
    }
  }
  return true;
}

void paint( int y, int x, int w){
  for(int i = 0 ; i < 5 ; i++ ){
    for(int j = 0 ; j < 5 ; j++ ){
      mas[y + i][x + j - 2] -= draw[w][i][j];
    }
  }
}

void repaint( int y, int x, int w){
  for(int i = 0 ; i < 5 ; i++ ){
    for(int j = 0 ; j < 5 ; j++ ){
      mas[y + i][x + j - 2] += draw[w][i][j];
    }
  }
}

bool rec( int y, int x, int n){
  if( n < 0 ) return false;
  if( y == 10 ) return n == 0;
  if( mas[y][x] == 0 ) return rec( y + (x == 9), (x + 1) % 10, n);
  for(int i = 0 ; i < 3 ; i++ ){
    if(!check( y, x, i)) continue;
    paint( y, x, i);
    if(rec( y, x, n - 1)){
      cout << x + (i == 1) << " " << y + 1 + (i == 2) << " " << i + 1 << endl;
      return true;
    }
    repaint( y, x, i);
  }
  return false;
}

int main(){
  cin >> q;
  for(int i = 0 ; i < 10 ; i++ ){
    for(int j = 0 ; j < 10 ; j++ ){
      cin >> mas[i][j];
    }
  }
  rec( 0, 0, q);
 }

2014年2月8日土曜日

AOJ0560 惑星探査

解法


二次元累積和を実装していい感じにやる

ソース


#include<iostream>  
#include<vector>  
#include<algorithm>  
#include<string>  
   
using namespace std;  
int mas[1001][1001][3];  
int main(){  
   
  int M, N, K;  
  string tmp = "JOI";  
   
  cin >> M >> N;  
  cin >> K;  
  for(int i = 1 ; i <= M ; i++ ){  
    for(int j = 1 ; j <= N ; j++ ){  
      char c;  
      cin >> c;  
      for(int k = 0 ; k < 3 ; k++ ){  
        mas[i][j][k] = mas[i-1][j][k] + mas[i][j-1][k] - mas[i-1][j-1][k];  
      }  
      mas[i][j][tmp.find(c)]++;  
    }  
  }  
  for(int i = 0 ; i < K ; i++ ){  
    int a, b, c, d;  
    cin >> a >> b >> c >> d;  
    for(int j = 0 ; j < 3 ; j++ ){  
      cout << (j?" ":"") << mas[c][d][j] + mas[a-1][b-1][j] - mas[a-1][d][j] - mas[c][b-1][j];  
    }  
    cout << endl;  
  }  
}  

AOJ1183 鎖中経路

解法


2つの円の交点を通る線分に交わっているか確かめながら、Dijkstraした。


ソース


#include<complex>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<iostream>
#include<queue>
using namespace std;
#define fr first
#define sc second
 
struct line: public vector< complex<double> >{
  line(){};
  line( const complex<double>& a, const complex<double>& b){
    push_back(a);
    push_back(b);
  }
};
struct circle {
  complex<double> p; double r;
  circle():p(0,0),r(0){};
  circle(const complex<double> &p, double r) : p(p),r(r){}
};
 
typedef complex < double > P;
typedef line               L;
typedef pair < P, P >      Ls;
typedef vector< P >        G;
typedef vector< P >        Ps;
typedef vector< L >        LLL;
typedef circle             C;
const double EPS = 1e-9;
const double INF = 1e8;
 
bool   eq(P,P); //点:点 一緒か
double cross(P,P); //外積
double dot(P,P); //内積
int    ccw(P,P,P); //3点の位置関係
bool   parallel(L,L); // 直線//直線
bool   orthogonal(L,L); //直線⊥直線
bool   intersect(L,L); //線分:線分交差
bool   intersect(L,P); //線分:点交差
bool   intersect(Ls,Ls); //直線:直線交差
bool   intersect(Ls,L); //直線:線分交差
bool   intersect(Ls,P); //直線:点交差
int    intersect(C,L); //円:線分交点数
double distance(L,L); //線分:線分の距離
double distance(L,P); //線分:点の距離
double distance(P,P); //点:点の距離
double distance(Ls,P); //直線:点距離
double distance(Ls,Ls); //直線:直線距離
double distance(Ls,L); //直線:線分距離
P      crosspoint(L,L); //線分:線分交点計算
L      crosspoint(C,Ls); //円:直線交点計算
L      crosspoint(C,L); //円:線分交点計算
Ps     crosspoint(C,C); //円:円交点計算
int    contains(G,P); //GがPが包容か
double area2(G); //Gの面積
bool   isconvex(G); //凸性判定
Ps     convex(G); //凸包
 
 
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
L llcomb(Ls a){
  L line( a.fr, a.sc);
  return line;
}
Ls llrcomb(L a){
  Ls line( a[0], a[1]);
  return line;
}
bool eq( P a, P b){
  return abs( a - b) < EPS;
}
double cross( P a, P b){
  return imag( conj(a) * b);
}
double dot( P a, P b){
  return real( conj(a) * b);
}
P projection( L l, P p) {
  double t = dot( p - l[0], l[0] - l[1]) / norm( l[0] - l[1]);
  return l[0] + t * ( l[0] - l[1]);
}
 
int ccw( P a, P b, P c){
  b -= a, c -= a;
  if(cross(b,c) > EPS)    return 1;  // a → b で 時計方向におれて c
  if(cross(b,c) < -EPS)    return -1; // a → b で 反時計方向におれて c
  if(dot(b,c) < -EPS)      return 2;  // c -- a -- b
  if(norm(b) < norm(c) - EPS) return -2; // a -- b -- c
                        return 0;  // a -- c -- b
}
bool intersect( L a, L b){
  return ccw( a[0], a[1], b[0]) * ccw( a[0], a[1], b[1]) <= 0 &&
    ccw( b[0], b[1], a[0]) * ccw( b[0], b[1], a[1]) <= 0;
}
bool intersect( L a, P p){
   return abs( a[0] - p) + abs( a[1] - p) - abs( a[1] - a[0]) < EPS;
}
bool intersect( Ls l, Ls m) {
  return abs(cross(l.sc-l.fr, m.sc-m.fr)) > EPS ||
         abs(cross(l.sc-l.fr, m.fr-l.fr)) < EPS;
}
bool intersect(Ls l, L s) {
  return cross( l.sc - l.fr, s[0] - l.fr) *      // s[0] is left of l
         cross( l.sc - l.fr, s[1] - l.fr) < EPS; // s[1] is right of l
}
bool intersect(Ls l, P p) {
  return abs( cross( l.sc - p, l.fr - p)) < EPS;
}
int intersect( C c, L l){
  if( norm( projection( l, c.p) - c.p) - c.r * c.r > EPS) return 0;
  const double d1 = abs( c.p - l[0]), d2 = abs( c.p - l[1]);
  if( d1 < c.r + EPS && d2 < c.r + EPS) return 0;
  if( d1 < c.r - EPS && d2 > c.r + EPS
      || d1 > c.r + EPS && d2 < c.r - EPS ) return 1;
  const P h = projection(l, c.p);
  if( dot( l[0] - h, l[1] - h) < 0) return 2;
  return 0;
}
double distance( L s, P p){
  P r = projection(s, p);
 
  if ( intersect( s, r)) return abs( r - p);
  return min( abs( s[0] - p), abs( s[1] - p));
}
double distance( L a, L b){
  if(intersect( a, b)) return 0;
  return min( min( distance( a, b[0]), distance( a, b[1])),
              min( distance( b, a[0]), distance( b, a[1])));
}
double distance( Ls l, P p) {
  return abs(p - projection( llcomb(l), p));
}
double distance( Ls l, Ls m) {
  return intersect(llcomb(l), llcomb(m)) ? 0 : distance(llcomb(l), m.fr);
}
double distance( Ls l, L s) {
  if (intersect(l, s)) return 0;
  return min(distance(l, s[0]), distance(l, s[1]));
}
double distance( P a, P b){
  return abs( a - b);
}
bool parallel( L a, L b){
  return abs( cross( a[1] - a[0], b[1] - b[0])) < EPS;
}
bool orthogonal( L a, L b){
  return dot( a[0] - a[1], b[0] - b[1]) < EPS;
}
#define curr(P,i) P[i]
#define next(P,i) P[(i+1)%P.size()]
#define prev(P, i) P[(i+P.size()-1) % P.size()]
enum { OUT, ON, IN };
int conteins(G Q, P p){
  bool in = false;
  for(int i = 0 ; i < Q.size() ; i++ ){
    P a = curr(Q,i) - p, b = next(Q,i) - p;
    if(imag(a) > imag(b)) swap(a,b);
    if(imag(a) <= 0 && 0 < imag(b) && cross(a,b) < 0) in = !in;
    if(cross(a,b) == 0 && dot(a,b) <= 0) return ON;
  }
  return in ? IN : OUT;
}
double area2(G p){
  double A = 0;
  for (int i = 0; i < p.size(); ++i){
    A += cross(curr(p, i), next(p, i));
  }
  return A;
}
bool isconvex(G p) {
  for (int i = 0; i < p.size(); ++i){
    if (ccw(prev(p, i), curr(p, i), next(p, i)) > 0) return false;
  }
  return true;
}
Ps convex(Ps ps) { //n>=3
  int k = 0;
  sort(ps.begin(), ps.end());
  Ps ch(2 * ps.size());
  for (int i = 0; i < ps.size(); ch[k++] = ps[i++]){
    while (k >= 2 and ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  }
  for (int i = ps.size()-2, t = k+1; i >= 0; ch[k++] = ps[i--]){
    while (k >= t and ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  }
  ch.resize(k-1);
  return ch;
}
P crosspoint(L l, L m) {
  double A = cross(l[1] - l[0], m[1] - m[0]);
  double B = cross(l[1] - l[0], l[1] - m[0]);
  if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
  return m[0] + B / A * (m[1] - m[0]);
}
L crosspoint( C c, Ls l) {
  const P hp = projection( llcomb(l), c.p), h =  hp - c.p;
  const double d2 = norm(h);
  P v = sqrt( c.r * c.r - d2) * ( l.sc - l.fr) / abs( l.sc - l.fr);
  return L(hp - v, hp + v);
}
L crosspoint( C c, L l) {
  if(intersect(c, l) == 2) return crosspoint(c, llrcomb(l));
  L ret = crosspoint(c, llrcomb(l));
  if(dot(l[0] - ret[0], l[1] - ret[0]) < 0) ret[1] = ret[0];
  else ret[0] = ret[1];
  return ret;
}
Ps crosspoint(C c1, C c2){
  double d = abs(c1.p - c2.p);
  double s = (c1.r + c2.r + d) / 2;
  double S = sqrt( s * ( s - c1.r) * ( s - c2.r) * ( s - d));
  double h = 2 * S / d;
  P v = ( c2.p - c1.p) / ( abs( c2.p - c1.p));
  double m = sqrt( c1.r * c1.r - h * h);
  Ps ret;
  ret.push_back( c1.p + m * v + h * v * P(0,1));
  ret.push_back( c1.p + m * v - h * v * P(0,1));
  return ret;
}
struct dC{
  double cost;
  P pos;
  int nowi,nowj;
  bool operator < (const dC &left) const {
    return cost > left.cost;
  }
};
L make_2_cross(C c1, C c2){
  Ps a(crosspoint( c1, c2));
  return L( a[0], a[1]);
}
 
int main(){
  C prev, now;
  int n;
 
  while(cin >> n , n){
    LLL ls;
 
    cin >> prev.p.real() >> prev.p.imag() >> prev.r;
    ls.push_back( L( prev.p, prev.p));
 
    for(int i = 1 ; i < n ; i++ ){
      cin >> now.p.real() >> now.p.imag() >> now.r;
      ls.push_back( make_2_cross( prev, now));
      prev = now;
    }
    ls.push_back( L( prev.p, prev.p)); // G
 
    priority_queue< dC > que;
    que.push((dC){ 0, ls[0][0], 0, 0});
    bool used[101][2] = {{}};
    double ret = INF;
    while(!que.empty()){
      dC p = que.top();
      que.pop();
      if(p.nowj == n){
        ret = p.cost;
        break;
      }
      if(used[p.nowj][p.nowi]++) continue;
      for(int i = 0 ; i < 2 ; i++ ){
        for(int j = p.nowj + 1 ; j <= n ; j++ ){
          L l = L( p.pos, ls[j][i]);
 
          bool flag = true;
          for(int k = j - 1 ; k > p.nowj ; k-- ){
            if(!intersect( l, ls[k])){
              flag = false;
              break;
            }
          }
          if(flag) que.push( (dC){ abs( l[0] - l[1]) + p.cost, l[1], i, j});
        }
      }
    }
    cout << fixed << setprecision(7) << ret << endl;
  }
}

AOJ1182 鉄道乗り継ぎ

解法


ワーシャった(小並感)
最初はワーシャって会社別に各駅までの最短距離を求める。
その次は、与えられたグラフを20000くらい(距離≦200 * 駅数≦100 より)までシュミレートして愚直に運賃を求める。
で、それを最初のグラフと照らし合わせながら、最短距離を運賃に変えたグラフにする。ついでに会社もまとめる。
最後にもう一回ワーシャって最安運賃を求める。

ソース


#include<iostream>
#include<queue>
#include<map>
 
using namespace std;
 
typedef pair < int , int > Pi;
const int INFTY = ( 1 << 28 );
 
int main(){
  int n, m, c, s, g;
  int station[21][101][101];
  int COST[21][20001];
 
  while(cin >> n >> m >> c >> s >> g, n){
    fill_n(**station, 21*101*101, INFTY);
    fill_n(*COST, 21 * 20001, 0);
    for(int i = 0 ; i < 21 ; i++ ){
      for(int j = 0 ; j < 101 ; j++ ) station[i][j][j] = 0;
    }
    for(int i = 0 ; i < m ; i++ ){
      int x, y, d, c;
      cin >> x >> y >> d >> c;
      station[c][x][y] = station[c][y][x] = min( station[c][x][y], d);
    }
 
    //わーしゃる
    for(int i = 1 ; i <= c ; i++ ){
      for(int j = 1 ; j <= n ; j++ ){
        for(int k = 1 ; k <= n ; k++ ){
          for(int l = 1 ; l <= n ; l++ ){
            station[i][k][l] = min( station[i][k][l], station[i][k][j] + station[i][j][l]);
          }
        }
      }
    }
    int p[21];
    for(int i = 1 ; i <= c ; i++ ){
      cin >> p[i];
    }
    int cost[52], dist[52];
    for(int i = 1 ; i <= c ; i++ ){
      fill_n( dist, 52, 0);
      fill_n( cost, 52, 0);
      for(int j = 1 ; j < p[i] ; j++ ){
        cin >> dist[j];
      }
      for(int j = 1 ; j <= p[i] ; j++ ){
        cin >> cost[j];
      }
      int diff = cost[1];
      int pos = 1;
      for(int j = 1 ; j < 20001 ; j++ ){
        if( pos < p[i] && dist[pos] < j) pos++;
        COST[i][j]= COST[i][j-1] + cost[pos];
      }
    }
    int ret[101][101];
    fill_n( *ret, 101 * 101, INFTY);
    for(int i = 1 ; i <= c ; i++ ){
      for(int j = 1 ; j <= n ; j++ ){
        for(int k = 1 ; k <= n ; k++ ){
          if(station[i][j][k] != INFTY) ret[j][k] = min( ret[j][k], COST[i][station[i][j][k]]);
        }
      }
    }
    for(int i = 1 ; i <= n ; i++ ){
      for(int j = 1 ; j <= n ; j++ ){
        for(int k = 1 ; k <= n ; k++ ){
          ret[j][k] = min( ret[j][k], ret[j][i] + ret[i][k]);
        }
      }
    }
 
    if(ret[s][g] == INFTY) cout << -1 << endl;
    else cout << ret[s][g] << endl;
  }
    return(0);
 
}

AOJ0204 UFO Shooting Down Operation

解法


当たり判定を間違えててWA連発してしまった。
レーザーの威力が出ない範囲内で当たるという
こんなケースがあったのが気づかなかった。気づけなかった。

ソース


#include<complex>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<iostream>
#include<queue>
using namespace std;
#define fr first
#define sc second

struct line: public vector< complex<double> >{
  line(){};
  line( const complex<double>& a, const complex<double>& b){
    push_back(a);
    push_back(b);
  }
};
struct circle {
  complex<double> p; double r;
  circle():p(0,0),r(0){};
  circle(const complex<double> &p, double r) : p(p),r(r){}
};

typedef complex < double > P;
typedef line               L;
typedef pair < P, P >      Ls;
typedef vector< P >        G;
typedef vector< P >        Ps;
typedef vector< L >        LLL;
typedef circle             C;
const double EPS = 1e-9;
const double INF = 1e8;

bool   eq(P,P); //点:点 同一判定
double cross(P,P); //外積
double dot(P,P); //内積
int    ccw(P,P,P); //3点の位置関係
bool   parallel(L,L); // 直線//直線
bool   orthogonal(L,L); //直線⊥直線
bool   intersect(L,L); //線分:線分交差
bool   intersect(L,P); //線分:点交差
bool   intersect(Ls,Ls); //直線:直線交差
bool   intersect(Ls,L); //直線:線分交差
bool   intersect(Ls,P); //直線:点交差
int    intersect(C,L); //円:線分交点数
bool   intersect(C,Ls); //円:直線交差
bool   intersect(C,C); //円:円交差
bool   intersect(C,P); //円:点交差
double distance(L,L); //線分:線分の距離
double distance(L,P); //線分:点の距離
double distance(P,P); //点:点の距離
double distance(Ls,P); //直線:点距離
double distance(Ls,Ls); //直線:直線距離
double distance(Ls,L); //直線:線分距離
P      crosspoint(L,L); //線分:線分交点計算
L      crosspoint(C,Ls); //円:直線交点計算
L      crosspoint(C,L); //円:線分交点計算
L      crosspoint(C,C); //円:円交点計算
int    contains(G,P); //図形:点内包判定
double area2(G); //面積
bool   isconvex(G); //凸性判定
Ps     convex(G); //凸包

namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
L llcomb(Ls a){
  L line( a.fr, a.sc);
  return line;
}
Ls llrcomb(L a){
  Ls line( a[0], a[1]);
  return line;
}
bool eq( P a, P b){ //OK
  return abs( a - b) < EPS;
}
double cross( P a,  P b){ //OK
  return imag( conj(a) * b);
}
double dot( P a, P b){ //OK
  return real( conj(a) * b);
}
P projection( L l, P p) { //OK
  double t = dot( p - l[0], l[0] - l[1]) / norm( l[0] - l[1]);
  return l[0] + t * ( l[0] - l[1]);
}
int ccw( P a, P b, P c){  //OK
  b -= a, c -= a;
  if(cross(b,c) > 0)    return +1;  // a → b で 反時計方向におれて c
  if(cross(b,c) < 0)    return -1; // a → b で 時計方向におれて c
  if(dot(b,c) < 0)      return +2;  // c -- a -- b
  if(norm(b) < norm(c)) return -2; // a -- b -- c
                        return 0;  // a -- c -- b
}
bool intersect( L a, L b){ //OK
  return ccw( a[0], a[1], b[0]) * ccw( a[0], a[1], b[1]) <= 0 &&
    ccw( b[0], b[1], a[0]) * ccw( b[0], b[1], a[1]) <= 0;
}
bool intersect( L a, P p){ //OK
   return abs( a[0] - p) + abs( a[1] - p) - abs( a[1] - a[0]) < EPS;
}
bool intersect( Ls l, Ls m) { //OK
  return abs(cross(l.sc-l.fr, m.sc-m.fr)) > EPS ||
         abs(cross(l.sc-l.fr, m.fr-l.fr)) < EPS;
}
bool intersect(Ls l, L s) { //OK
  return cross( l.sc - l.fr, s[0] - l.fr) *
         cross( l.sc - l.fr, s[1] - l.fr) < EPS;
}
bool intersect(Ls l, P p) { //OK
  return abs( cross( l.sc - p, l.fr - p)) < EPS;
}
bool intersect( C c, Ls s){ //OK
  return distance( s, c.p) <= c.r + EPS;
}
bool intersect( C a, C b){ //OK
  return ( norm( a.p - b.p) - ( a.r + b.r) * ( a.r + b.r) < EPS) &&
    ( norm( a.p - b.p) - ( a.r - b.r) * ( a.r - b.r) > -EPS);
}
int intersect( C c, L l){ //OK
  if( norm( projection( l, c.p) - c.p) - c.r * c.r > EPS) return 0;
  const double d1 = abs( c.p - l[0]), d2 = abs( c.p - l[1]);
  if( d1 < c.r + EPS && d2 < c.r + EPS) return 0;
  if( d1 < c.r - EPS && d2 > c.r + EPS
      || d1 > c.r + EPS && d2 < c.r - EPS ) return 1;
  const P h = projection( l, c.p);
  if( dot( l[0] - h, l[1] - h) < 0) return 2;
  return 0;
}
bool intersect( C c, P p){ //OK
  return abs( abs( p - c.p) - c.r ) < EPS;
}
double distance( L s, P p){ //OK
  P r = projection(s, p);
  if ( intersect( s, r)) return abs( r - p);
  return min( abs( s[0] - p), abs( s[1] - p));
}
double distance( L a, L b){ //OK
  if(intersect( a, b)) return 0;
  return min( min( distance( a, b[0]), distance( a, b[1])),
              min( distance( b, a[0]), distance( b, a[1])));
}
double distance( Ls l, P p) { //OK
  return abs(p - projection( llcomb(l), p));
}
double distance( Ls l, Ls m) { //OK
  return intersect( l, m) ? 0 : distance( l, m.fr);
}
double distance( Ls l, L s) { //OK
  if (intersect(l, s)) return 0;
  return min(distance(l, s[0]), distance(l, s[1]));
}
double distance( P a, P b){ //OK
  return abs( a - b);
}
bool parallel( L a, L b){
  return abs( cross( a[1] - a[0], b[1] - b[0])) < EPS;
}
bool orthogonal( L a, L b){
  return dot( a[0] - a[1], b[0] - b[1]) < EPS;
}
#define curr(P,i) P[i]
#define next(P,i) P[(i+1)%P.size()]
#define prev(P, i) P[(i+P.size()-1) % P.size()]
enum { OUT, ON, IN };
int conteins(G Q, P p){ //OK
  bool in = false;
  for(int i = 0 ; i < Q.size() ; i++ ){
    P a = curr(Q,i) - p, b = next(Q,i) - p;
    if(imag(a) > imag(b)) swap(a,b);
    if(imag(a) <= 0 && 0 < imag(b) && cross(a,b) < 0) in = !in;
    if(cross(a,b) == 0 && dot(a,b) <= 0) return ON;
  }
  return in ? IN : OUT;
}
double area2(G p){ //OK
  double A = 0;
  for (int i = 0; i < p.size(); ++i){
    A += cross(curr(p, i), next(p, i));
  }
  return A;
}
bool isconvex(G p) { // OK
  for (int i = 0; i < p.size(); ++i){
    if (ccw(prev(p, i), curr(p, i), next(p, i)) > 0) return false;
  }
  return true;
}
Ps convex(Ps ps) { //n>=3 OK
  int k = 0;
  sort(ps.begin(), ps.end());
  Ps ch(2 * ps.size());
  for (int i = 0; i < ps.size(); ch[k++] = ps[i++]){
    while (k >= 2 and ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  }
  for (int i = ps.size()-2, t = k+1; i >= 0; ch[k++] = ps[i--]){
    while (k >= t and ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  }
  ch.resize(k-1);
  return ch;
}
P crosspoint(L l, L m) { //OK
  double A = cross(l[1] - l[0], m[1] - m[0]);
  double B = cross(l[1] - l[0], l[1] - m[0]);
  if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
  return m[0] + B / A * (m[1] - m[0]);
}
L crosspoint( C c, Ls l) { //OK
  const P hp = projection( llcomb(l), c.p), h =  hp - c.p;
  const double d2 = norm(h);
  P v = sqrt( c.r * c.r - d2) * ( l.sc - l.fr) / abs( l.sc - l.fr);
  return L(hp - v, hp + v);
}
L crosspoint( C c, L l) { //OK
  if(intersect(c, l) == 2) return crosspoint(c, llrcomb(l));
  L ret = crosspoint(c, llrcomb(l));
  if(dot(l[0] - ret[0], l[1] - ret[0]) < 0) ret[1] = ret[0];
  else ret[0] = ret[1];
  return ret;
}
L crosspoint(C c1, C c2){ //OK
  double d = abs(c1.p - c2.p);
  double s = (c1.r + c2.r + d) / 2;
  double S = sqrt( s * ( s - c1.r) * ( s - c2.r) * ( s - d));
  double h = 2 * S / d;
  P v = ( c2.p - c1.p) / ( abs( c2.p - c1.p));
  double m = sqrt( c1.r * c1.r - h * h);
  return L( c1.p + m * v + h * v * P(0,1), c1.p + m * v - h * v * P(0,1));
}

typedef pair< C, double > Cv;

int main(){

  int n;
  C c;
  c.p = P(0,0);

  while(cin >> c.r >> n, n){
    vector< Cv > ufo(n);
    for(int i = 0 ; i < n ; i++ ){
      double x, y, r, v;
      cin >> x >> y >> r >> v;
      ufo[i] = Cv( C( P( x, y), r), v);
    }

    int cnt = 0;
    while(!ufo.empty()){

      vector<Cv>::iterator mpos;
      double mini = INF;
      for(vector<Cv>::iterator it = ufo.begin() ; it != ufo.end() ; it++){
        double t =  abs((*it).fr.p) / (*it).sc;
        if( t >= 1.0 ) (*it).fr.p -= (*it).fr.p/abs((*it).fr.p) * (*it).sc;
        else (*it).fr.p = P(0,0);
        if(abs((*it).fr.p) <= c.r){
          cnt++;
          ufo.erase(it--);
        } else if( mini > abs((*it).fr.p) ){
          mini = abs((*it).fr.p);
          mpos = it;
        }
      }
      if(ufo.empty()) break;

      L l = L( c.p,(*mpos).fr.p * 2000.0);
      for(vector<Cv>::iterator it = ufo.begin() ; it != ufo.end() ; it++ ){
        if(intersect((*it).fr, l)){
          L p = crosspoint((*it).fr, l);
          if(abs(p[0]) > c.r || abs(p[1]) > c.r){ //あらら
            ufo.erase(it--);
          }
        }
      }
    }
    cout << cnt << endl;
  }
}


2014年1月21日火曜日

AOJ0562 JOI 国の買い物事情

解法


Dijkstraしてそれぞれの街のショッピングモールまでの最短距離を求めて、
なんといえばいいか、その…
例えば「A街」と「B街」がありました。
「A街」からショッピングモールまでの最短ルートが10でした。
「B街」から(ry の最短ルートは15でした。
これでA街とB街までの道の長さが10だったら、困るじゃん。
で多分これを計算で求める。
ルート = A + ( B - A ) + ( A~B - ( B - A ) ) / 2
なんか図を書いてみたらこうなった。
あとは切り上げ。
nで割るとしたら ( もとの数 + n - 1 ) / n で良い感じに切り上げできる。

ソース


#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef pair < int , int > Pi;
#define fr first
#define sc second
#define INF ( 1 << 30 )
struct edge{
  int to, cost;
};
vector < edge > info[3001];
int main() {
  int N, M, K;
 
  cin >> N >> M >> K;
  for(int i = 0 ; i < M ; i++ ){
    int a, b, c;
    cin >> a >> b >> c;
    info[a].push_back((edge){ b, c});
    info[b].push_back((edge){ a, c});
  }
 
  int used[3001];
  fill_n( used, 3001, INF);
  priority_queue< Pi , vector< Pi >,greater< Pi > > que;
  for(int i = 0 ; i < K ; i++ ){
    int a;
    cin >> a;
 
    que.push(Pi( 0, a));
    used[a] = 0;
 
    while(!que.empty()){
      Pi p = que.top();
      que.pop();
      for(int j = 0 ; j < info[p.sc].size() ; j++ ){
        edge e = info[p.sc][j];
        if( used[e.to] > p.fr + e.cost ){
          used[e.to] = p.fr + e.cost;
          que.push( Pi( used[e.to], e.to));
        }
      }
    }
  }
 
 
  int ret = 0;
  for(int i = 1 ; i <= N ; i++ ){
    for(int j = 0 ; j < info[i].size() ; j++ ){
      if( used[i] <= used[info[i][j].to]){
        const int java = used[info[i][j].to] - used[i];
        ret = max( ret, used[i] + java + (info[i][j].cost - java + 1) / 2);
      }
    }
  }
  cout << ret << endl;
}

AOJ2219 THE BYDOLM@STER

解法


個数無限のナップザック×3。
名前は見た感じ不要。入力がめんどくさかった。

ソース


#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
 
int main() {
  int N, M, cost[300], exp[300][3], dp[301];
  while(cin >> N >> M){
    for(int i = 0 ; i < N ; i++ ){
      string s;
      getline(cin, s), getline(cin, s);
      cin >> cost[i] >> exp[i][0] >> exp[i][1] >> exp[i][2];
    }
    int ret = 0;
    for(int i = 0 ; i < 3 ; i++ ){
      fill_n( dp, 301, 0);
      for(int j = 0 ; j < N ; j++ ){
        for(int k = 0 ; k <= M ; k++ ){
          if(k - cost[j] >= 0 ){
            dp[k] = max( dp[k], dp[k-cost[j]] + exp[j][i]);
            ret = max( ret, dp[k]);
          }
        }
      }
    }
    cout << ret << endl;
  }
}

2014年1月13日月曜日

AOJ0283 勉強会

解法


2分探索使ってほげると良い。
multisetとかmapとか色々使ったけどやっぱりvectorが実行時間が短かった。

ソース


#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
using namespace std;
 
#define INF ( 1 << 30 )
typedef pair < int , int > Pi;
 
int main()
{
  int N, Q;
  int stmp[1000000], comp[1000000], a;
  char buff[1024];
  scanf( "%d %d", &N, &Q);
  for(int i = 0 ; i < N ; i++ ){
    scanf( "%d", &stmp[i]);
    comp[i] = stmp[i];
  }
  sort( comp, comp + N);
 
  vector< int > sym;
  while(Q--){
    scanf("%s %d", buff, &a);
    if(*buff == 'A'){ //ADD
 
      sym.push_back(stmp[a - 1]);
      sort( sym.begin(), sym.end());
 
    } else if(*buff == 'R'){ //REMOVE
 
      sym.erase( lower_bound( sym.begin(), sym.end(), stmp[a - 1]));
 
    } else { //CHECK
 
      int left = 0, right = INF;
      while(left != right){
        int center = ( left + right ) / 2;
        int pre = 0, BAN = 0;
        for(int i = 0 ; i < sym.size() ; i++ ){
          int p = distance( comp,lower_bound( comp, comp + N, sym[i] - center));
          BAN += max( p - pre, 0);
          pre = distance( comp, upper_bound( comp, comp + N, sym[i]));
        }
        BAN += max( N - pre, 0);
        if(BAN <= a) right = center;
        else left = center + 1;
      }
      if( left != INF) printf("%d\n", left);
      else puts("NA");
 
    }
  }
  return false;
}

AOJ0041: Expression

問題概要


10パズル

解法


括弧とか括弧とかが面倒なので面倒くさいけど場合分けで書いた。
((a.b).(c.d))
(((a.b).c).d)
((a.(b.c)).d)
多分この3通りだと思う。

ソース


#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<sstream>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; i++ )
int d[4];
bool flg = false;
string s = "+-*";
int calc( int a, int op, int b){
  if( op == 0) return a + b;
  if( op == 1) return a - b;
  return a * b;
}
bool solve(int a, int b, int c){
  flg++;
  if(calc( calc( calc( d[0], a, d[1]), b, d[2]), c, d[3]) == 10){
    return printf("(((%d %c %d) %c %d) %c %d)\n", d[0], s[a], d[1], s[b], d[2], s[c], d[3]);
  }
  if(calc( calc( d[0], a, d[1]), b, calc( d[2], c, d[3])) == 10){
    return printf("((%d %c %d) %c (%d %c %d))\n", d[0], s[a], d[1], s[b], d[2], s[c], d[3]);
  }
  if(calc( calc( d[0], a, calc( d[1], b, d[2])), c, d[3]) == 10){
    return printf("((%d %c (%d %c %d)) %c %d)\n", d[0], s[a], d[1], s[b], d[2], s[c], d[3]);
  }
  return flg = false;
}
 
bool judge(){
  rep(i,3) rep(j,3) rep(k,3) if(solve( i, j, k)) return true;
}
int main(){
  while(flg = true){
    rep(i,4) cin >> d[i];
    if(!d[0] && !d[1] && !d[2] && !d[3]) break;
    sort(d, d + 4);
    do if(judge()) break; while(next_permutation(d,d+4));
    if(!flg) puts("0");
  }
}

2014年1月1日水曜日

AOJ0070 Combination of Number Sequences

解法


書いていて気持ちが良くなるメモ化再帰。
書いていて気持ちが良い(再掲)

ソース


#include<iostream>
#include<algorithm>
using namespace std;
int dp[10][1<<10][331], n; //nの制約は自明だけど sはどれくら(ry ← 331か
int rec( int now, int used,int sum){
  if( sum < 0 ) return 0;
  if( now == n ) return sum == 0;
  if(~dp[now][used][sum]) return dp[now][used][sum];
  int ret = 0;
  for(int i = 0 ; i < 10 ; i++ ){
    if((used >> i) & 1)
      ret += rec( now + 1, used&~(1 << i), sum - i * (now + 1));
  }
  return dp[now][used][sum] = ret;
}
int main(){
  int s;
  while(cin >> n >> s){
    fill_n( **dp, 10 * (1 << 10) * 331, -1);
    cout << rec( 0, (1 << 10) - 1, s) << endl;
  }
}

2013年12月31日火曜日

AOJ0214 秋のイルミネーション

解法


四角形の交差判定が出来れば勝ち。
あとはUnionFind使っただけ。

四角形の交差判定は、
1.aがbの中にある
2.bがaの中にある
3.aの各辺がbの各辺でどれか交差する
こんな感じでやった。

ライブラリ作ったのでやってみたけど、ライブラリあるといい(小並感)

ソース


#include<iostream>
#include<complex>
#include<vector>
using namespace std;
typedef complex < double > P;
typedef vector< P > G;
vector< G > g;
const double EPS = 1e-8;
const double INF = 1e12;
double cross(const P& a,const P& b){ //外積
  return imag(conj(a) * b);
}
double dot(const P& a,const P& b){ // 内積
  return real(conj(a) * b);
}
struct L: vector < P >{
  L(const P& a,const P& b){
    push_back(a);
    push_back(b);
  }
};
int ccw(P a,P b,P c){
  b -= a; c -= a;
  if(cross(b,c) > 0) return 1;
  if(cross(b,c) < 0) return -1;
  if(dot(b,c) < 0) return 2; // c--a--b
  if(norm(b) < norm(c)) return -2; // a--b--c
  return 0; // a--c--b
}
bool intersectSS(const L& s,const L& t){ //交差判定 線分:線分
  return ccw(s[0],s[1],t[0]) * ccw(s[0],s[1],t[1]) <= 0 &&
    ccw(t[0],t[1],s[0]) * ccw(t[0],t[1],s[1]) <= 0;
}
#define curr(P,i) P[i]
#define next(P,i) P[(i+1)%P.size()]
bool conteins(const G& Q, const P& p){
  bool in = false;
  for(int i = 0 ; i < Q.size() ; i++ ){
    P a = curr(Q,i) - p, b = next(Q,i) - p;
    if(imag(a) > imag(b)) swap(a,b);
    if(imag(a) <= 0 && 0 < imag(b) && cross(a,b) < 0) in = !in;
    if(cross(a,b) == 0 && dot(a,b) <= 0) return true;
  }
  return in;
}
bool intersect( int x, int y){ //交差判定 g[x] == g[y]
  // g[x] or g[y] が包容
  for(int i = 0 ; i < 4 ; i++ ){
    if(conteins(g[y],g[x][i]) || conteins(g[x],g[y][i])) return true;
  }
  // g[x] と g[y]の辺が交差
  for(int i = 0 ; i < 4 ; i++ ){
    for(int j = 0 ; j < 4 ; j++ ){
      if(intersectSS(L(curr(g[x],i),next(g[x],i)),L(curr(g[y],j),next(g[y],j)))) return true;
    }
  }
  return false;
}
//UnionFind
vector< int > rank, p;
void link(int x,int y){
  if(rank[x] > rank[y]) p[y] = x;
  else{
    p[x] = y;
    if(rank[x] == rank[y]) rank[y]++;
  }
}
void init(int size){
  rank.resize(size);
  p.resize(size);
  for(int i = 0 ; i < size ; i++ ){
    p[i] = i, rank[i] = 0;
  }
}
int findSet(int x){
  if(x != p[x]) p[x] = findSet(p[x]);
  return p[x];
}
void Union(int x,int y){
  link(findSet(x),findSet(y));
}
bool isSame(int x,int y){
  return findSet(x) == findSet(y);
}

int main(){
  int N, M;
  while(cin >> N , N){
    for(int i = 0 ; i < N ; i++ ){
      cin >> M;
      g.resize(M);
      init(M);
      for(int j = 0 ; j < M ; j++ ){
        for(int k = 0 ; k < 4 ; k++ ){
          P buff;
          cin >> buff.real() >> buff.imag();
          g[j].push_back(buff);
        }
      }
      for(int j = 0 ; j < M ; j++ ){
        for(int k = 0 ; k < j ; k++ ){
          if(!isSame( j, k) && intersect( j, k)) Union( j, k);
        }
      }
      int ret = 0;
      for(int j = 0 ; j < M ; j++ ){
        if(findSet(j) == j) ret++;
      }
      cout << ret << endl;
      g.clear();
    }
  }
}

2013年12月26日木曜日

AOJ0213 土地分割

たぶん2013年最後の更新。

解法


DFSにパターン数を足したような再帰すると良い。
枝狩りは、『面積 % 高さ != 0』のときと『すでに誰かの土地がある』とこらへん。
なんかうまく全探できなかったので修行が必要かも。あんまり変数をグローバル化しすぎると良くないね(確信)
計算量が怪しかったが普通に良かった。

ソース


#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;
#define fr first
#define sc second
typedef pair < int , int > Pi;
typedef pair < int , Pi > Pii;
  
int h, w, n, ans[10][10];
vector< Pii > memo;
  
int wy, wx;
void plus_n( int y, int x, int nt){
  wy = y;
  wx = ( x + nt ) % w;
  if(!wx) wy++;
  return ;
}
 
int dfs( const int mas[][10], const int used, const int y, const int x){
  if( y == h){ //exit
    memcpy( ans, mas, sizeof(int)*100);
    return 1;
  }
  int ret = 0;
  if( mas[y][x] != 0){
    plus_n( y, x, 1);
    ret += dfs( mas, used, wy, wx);
  }else{
    for(int bit = 0 ; bit < n ; bit++ ){
      if( (used >> bit) & 1 ) continue; // もうやってある
  
      for(int i = 1 ; i <= memo[bit].fr ; i++ ){ //高さ決定
        if( memo[bit].fr % i != 0 ) continue; // 長方形無理
        int height = i, width = memo[bit].fr / i;
  
        if( y <= memo[bit].sc.fr && y > memo[bit].sc.fr - height &&
            x <= memo[bit].sc.sc && x > memo[bit].sc.sc - width &&
            y + height - 1 < h && x + width - 1 < w){
          int java[10][10];
          bool ok = true;
          memcpy( java, mas, sizeof(int)*100);
          for(int j = 0 ; j < height ; j++ ){
            for(int k = 0 ; k < width ; k++ ){
              if(java[j + y][k + x]) ok = false;
              java[j + y][k + x] = bit + 1;
            }
          }
          if(ok){
            plus_n( y, x, width);
            ret += dfs( java, used|(1<<bit), wy, wx);
          }
        }
      }
    }
  }
  return ret;
}
int main(){
  while(cin >> w >> h >> n , w){
    memo.resize( n);
    for(int i = 0, bf ; i < n ; i++ ){
      cin >> bf;
      cin >> memo[bf - 1].fr;
    }
    for(int i = 0, c ; i < h ; i++ ){
      for(int j = 0 ; j < w ; j++ ){
        cin >> c;
        if(c)memo[c - 1].sc = Pi( i, j);
      }
    }
    int mas[10][10] = {{}};
    if(dfs( mas, 0, 0, 0) == 1){
      for(int i = 0 ; i < h ; i++ ){
        for(int j = 0 ; j < w ; j++ ){
          cout << ( j ? " " : "" ) << ans[i][j];
        }
        cout << endl;
      }
    }else cout << "NA" << endl;
  }
}

2013年12月22日日曜日

AOJ0191 Baby Tree

解法


自明なDP。
1回目に与えた肥料だけでは、苗木の大きさが変わりません。
2回目以降は、その回に与えた肥料と、その直前に与えた肥料との組み合わせによって苗木に 影響を与えます。良い影響を与えると苗木が伸び、悪い影響を与えると苗木が縮んでしまうこともあります。
ここからすべてを察した。

ソース


#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
double dp[100][100],g[100][100];
int main(){
  int n, m;
  while(cin >> n >> m , n){
    for(int i = 0 ; i < n ; i++ )
      for(int j = 0 ; j < n ; j++ ) cin >> g[i][j];
    fill_n( dp[0], n, 1.0);
    fill_n( dp[1], 9900, 0.0);
    for(int i = 1 ; i < m ; i++ ) //回
      for(int prev = 0 ; prev < n ; prev++ ) // prev
        for(int now = 0 ; now < n ; now++ ) // now
          dp[i][now] = max( dp[i][now], dp[i - 1][prev] * g[prev][now]);
 
    cout << fixed << setprecision(2) << *max_element( dp[m - 1], dp[m - 1] + n ) << endl;
  }
}

2013年12月18日水曜日

AOJ0210 ザ・スクエアーズ

解法


誤読していた。向きを変えるので1秒、動こうとするので1秒とかやって訳の分からないことをしていた。
向きを変えるステップは自明なので簡単だが、移動するステップが面倒。
最初人視点でやっていたので詰んでしまったが、マス視点でやってあとは頑張った。
dxとかdyとかdmとか4次元配列になってるけど、これはただ求める計算式に至らなかっただけ。
良い感じにシュミレーションすれば勝てる。

ソース


#include<iostream>
#include<vector>
#include<map>
#include<string>
using namespace std;
typedef pair < int , int > Pi;
typedef pair < int , Pi > Pii;
#define fr first
#define sc second
const int dy[][4] = {{1,0,-1,0},{0,-1,0,1},{-1,0,1,0},{0,1,0,-1}};
const int dx[][4] = {{0,1,0,-1},{1,0,-1,0},{0,-1,0,1},{-1,0,1,0}};
const int dm[][4] = {{3,0,1,2},{0,1,2,3},{1,2,3,0},{2,3,0,1}};
const int my[] = { 0, -1, 0, 1}, mx[] = { 1, 0, -1, 0};
const int md[] = { 2, 3, 0, 1};
int w, h;
char mas[30][30];
vector< Pii > vc;
string tmp = "ENWS";
int search( int y , int x){
  for(int i = 0 ; i < vc.size() ; i++ ){
    if(Pi(y,x) == vc[i].sc){
      return i;
    }
  }
  return -1;
}
vector< Pii >  solve(){
  vector< Pii > java;
  for(int i = 0 ; i < vc.size() ; i++ ){
    //change
    for(int j = 0 ; j < 4 ; j++ ){
      int yy = vc[i].sc.fr + dy[vc[i].fr][j];
      int xx = vc[i].sc.sc + dx[vc[i].fr][j];
      if(mas[yy][xx] != '#' && search(yy,xx) == -1){
        vc[i].fr = dm[vc[i].fr][j];
        break;
      }
    }
  }
  //push
  bool list[1000] = {};
  for(int i = 0 ; i < h ; i++ ){
    for(int j = 0 ; j < w ; j++ ){
      if(mas[i][j] == '#' || search(i,j) != -1) continue;
      for(int k = 0 ; k < 4 ; k++ ){
        int ny = i + my[k], nx = j + mx[k], iti;
        if((iti = search(ny,nx)) == -1) continue;
        if(vc[iti].fr == md[k]){
          if(mas[i][j] != 'X') java.push_back(Pii(vc[iti].fr,Pi(i,j)));
          list[iti] = true;
          break;
        }
      }
    }
  }
  for(int i = 0 ; i < vc.size() ; i++ ){
    if(!list[i]) java.push_back(vc[i]);
  }
  return java;
}
int main(){
  while(cin >> w >> h , w){
    for(int i = 0 ; i < h ; i++ ){
      for(int j = 0 ; j < w ; j++ ){
        cin >> mas[i][j];
        if(tmp.find(mas[i][j]) != string::npos){
          vc.push_back(Pii( tmp.find(mas[i][j]), Pi( i, j)));
        }
      }
    }
    int ret = 0;
    while(ret <= 180 && !vc.empty()){
      vc = solve();
      ret++;
    }
    if(ret == 181) cout << "NA" << endl;
    else cout << ret << endl;
    vc.clear();
  }
}

AOJ1155 如何に汝を満足せしめむ? いざ数え上げむ…

解法


最近構文解析にハマるワタクシ。
AOJ1244 Molecular FormulaとかAOJ2401 恒等式とか以前ブログに取り上げたと思う。
三値論理の式が与えられてホゲってしまう。
なんか論理積とか論理和とか否定とか考えれば出来そうだけど、面倒臭かったのでテーブル作った。

ソース


#include<iostream>
#include<string>
#include<cctype>
#include<algorithm>
using namespace std;
typedef string::const_iterator Cursol;
int P, Q, R;
int tmp1[3] = { 2, 1, 0}, tmp2[3][3] = {{0,0,0},{0,1,1},{0,1,2}};
int tmp3[3][3] = {{0,1,2},{1,1,2},{2,2,2}};
 
int formula(Cursol &c){
  int ret ;
  if(*c == 'P') ret = P;
  else if(*c == 'Q') ret = Q;
  else if(*c == 'R') ret = R;
  else if(isdigit(*c)) ret = *c - '0';
  else if(*c == '-') return tmp1[formula(++c)];
  else if(*c == '('){
    ret = formula(++c);
    if(*c == '*') ret = tmp2[ret][formula(++c)];
    else if(*c == '+') ret = tmp3[ret][formula(++c)];
  }
  c++;
  return ret;
}
int main(){
 
  string s;
  Cursol c;
 
  while( cin >> s, s != "."){
    int ret = 0;
    for(P = 0 ; P < 3 ; P++ ){
      for(Q = 0 ; Q < 3 ; Q++ ){
        for(R = 0 ; R < 3 ; R++ ){
          c = s.begin();
          if( 2 == formula(c)) ret++;
        }
      }
    }
    cout << ret << endl;
  }
}